Trie.ts overview

A Trie is used for locating specific string keys from within a set.

It works similar to HashMap, but with keys required to be string. This constraint unlocks some performance optimizations and new methods to get string prefixes (e.g. keysWithPrefix, longestPrefixOf).

Prefix search is also the main feature that makes a Trie more suited than HashMap for certain usecases.

A Trie is often used to store a dictionary (list of words) that can be searched in a manner that allows for efficient generation of completion lists (e.g. predict the rest of a word a user is typing).

A Trie has O(n) lookup time where n is the size of the key, or even less than n on search misses.

Since v2.0.0

Exports Grouped by Category

constructors
- empty
- fromIterable
- make
elements
- get
- has
- isEmpty
filtering
- compact
- filter
- filterMap
folding
- map
- reduce
getters
models
- Trie (interface)
mutations
- insert
- insertMany
- modify
- remove
- removeMany
symbol
- TypeId (type alias)
traversing
- forEach
unsafe
- unsafeGet

constructors

empty

Creates an empty Trie.

Example

import * as assert from "node:assert"
import { Trie, Equal } from "effect"

const trie = Trie.empty<string>()

assert.equal(Trie.size(trie), 0)
assert.deepStrictEqual(Array.from(trie), [])

Signature

declare const empty: <V = never>() => Trie<V>

Since v2.0.0

fromIterable

Creates a new Trie from an iterable collection of key/value pairs (e.g. Array<[string, V]>).

Example

import * as assert from "node:assert"
import { Trie, Equal } from "effect"

const iterable: Array<readonly [string, number]> = [
  ["call", 0],
  ["me", 1],
  ["mind", 2],
  ["mid", 3]
]
const trie = Trie.fromIterable(iterable)

// The entries in the `Trie` are extracted in alphabetical order, regardless of the insertion order
assert.deepStrictEqual(Array.from(trie), [
  ["call", 0],
  ["me", 1],
  ["mid", 3],
  ["mind", 2]
])
assert.equal(Equal.equals(Trie.make(["call", 0], ["me", 1], ["mind", 2], ["mid", 3]), trie), true)

Signature

declare const fromIterable: <V>(entries: Iterable<readonly [string, V]>) => Trie<V>

Since v2.0.0

make

Constructs a new Trie from the specified entries ([string, V]).

Example

import * as assert from "node:assert"
import { Trie, Equal } from "effect"

const trie = Trie.make(["ca", 0], ["me", 1])

assert.deepStrictEqual(Array.from(trie), [
  ["ca", 0],
  ["me", 1]
])
assert.equal(
  Equal.equals(
    Trie.fromIterable([
      ["ca", 0],
      ["me", 1]
    ]),
    trie
  ),
  true
)

Signature

declare const make: <Entries extends Array<readonly [string, any]>>(
  ...entries: Entries
) => Trie<Entries[number] extends readonly [any, infer V] ? V : never>

Since v2.0.0

elements

get

Safely lookup the value for the specified key in the Trie.

Example

import * as assert from "node:assert"
import { Trie, Option } from "effect"

const trie = Trie.empty<number>().pipe(
  Trie.insert("call", 0),
  Trie.insert("me", 1),
  Trie.insert("mind", 2),
  Trie.insert("mid", 3)
)

assert.deepStrictEqual(Trie.get(trie, "call"), Option.some(0))
assert.deepStrictEqual(Trie.get(trie, "me"), Option.some(1))
assert.deepStrictEqual(Trie.get(trie, "mind"), Option.some(2))
assert.deepStrictEqual(Trie.get(trie, "mid"), Option.some(3))
assert.deepStrictEqual(Trie.get(trie, "cale"), Option.none())
assert.deepStrictEqual(Trie.get(trie, "ma"), Option.none())
assert.deepStrictEqual(Trie.get(trie, "midn"), Option.none())
assert.deepStrictEqual(Trie.get(trie, "mea"), Option.none())

Signature

declare const get: { (key: string): <V>(self: Trie<V>) => Option<V>; <V>(self: Trie<V>, key: string): Option<V> }

Since v2.0.0

has

Check if the given key exists in the Trie.

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(
  Trie.insert("call", 0),
  Trie.insert("me", 1),
  Trie.insert("mind", 2),
  Trie.insert("mid", 3)
)

assert.equal(Trie.has(trie, "call"), true)
assert.equal(Trie.has(trie, "me"), true)
assert.equal(Trie.has(trie, "mind"), true)
assert.equal(Trie.has(trie, "mid"), true)
assert.equal(Trie.has(trie, "cale"), false)
assert.equal(Trie.has(trie, "ma"), false)
assert.equal(Trie.has(trie, "midn"), false)
assert.equal(Trie.has(trie, "mea"), false)

Signature

declare const has: { (key: string): <V>(self: Trie<V>) => boolean; <V>(self: Trie<V>, key: string): boolean }

Since v2.0.0

isEmpty

Checks if the Trie contains any entries.

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>()
const trie1 = trie.pipe(Trie.insert("ma", 0))

assert.equal(Trie.isEmpty(trie), true)
assert.equal(Trie.isEmpty(trie1), false)

Signature

declare const isEmpty: <V>(self: Trie<V>) => boolean

Since v2.0.0

filtering

compact

Filters out None values from a Trie of Optionss.

Example

import * as assert from "node:assert"
import { Trie, Equal, Option } from "effect"

const trie = Trie.empty<Option.Option<number>>().pipe(
  Trie.insert("shells", Option.some(0)),
  Trie.insert("sells", Option.none()),
  Trie.insert("she", Option.some(2))
)

const trieMapV = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("she", 2))

assert.equal(Equal.equals(Trie.compact(trie), trieMapV), true)

Signature

declare const compact: <A>(self: Trie<Option<A>>) => Trie<A>

Since v2.0.0

filter

Filters entries out of a Trie using the specified predicate.

Example

import * as assert from "node:assert"
import { Trie, Equal } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1), Trie.insert("she", 2))

const trieMapV = Trie.empty<number>().pipe(Trie.insert("she", 2))

const trieMapK = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1))

assert.equal(
  Equal.equals(
    Trie.filter(trie, (v) => v > 1),
    trieMapV
  ),
  true
)
assert.equal(
  Equal.equals(
    Trie.filter(trie, (_, k) => k.length > 3),
    trieMapK
  ),
  true
)

Signature

declare const filter: {
  <A, B extends A>(f: (a: NoInfer<A>, k: string) => a is B): (self: Trie<A>) => Trie<B>
  <A>(f: (a: NoInfer<A>, k: string) => boolean): (self: Trie<A>) => Trie<A>
  <A, B extends A>(self: Trie<A>, f: (a: A, k: string) => a is B): Trie<B>
  <A>(self: Trie<A>, f: (a: A, k: string) => boolean): Trie<A>
}

Since v2.0.0

filterMap

Maps over the entries of the Trie using the specified partial function and filters out None values.

Example

import * as assert from "node:assert"
import { Trie, Equal, Option } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1), Trie.insert("she", 2))

const trieMapV = Trie.empty<number>().pipe(Trie.insert("she", 2))

const trieMapK = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1))

assert.equal(
  Equal.equals(
    Trie.filterMap(trie, (v) => (v > 1 ? Option.some(v) : Option.none())),
    trieMapV
  ),
  true
)
assert.equal(
  Equal.equals(
    Trie.filterMap(trie, (v, k) => (k.length > 3 ? Option.some(v) : Option.none())),
    trieMapK
  ),
  true
)

Signature

declare const filterMap: {
  <A, B>(f: (value: A, key: string) => Option<B>): (self: Trie<A>) => Trie<B>
  <A, B>(self: Trie<A>, f: (value: A, key: string) => Option<B>): Trie<B>
}

Since v2.0.0

folding

map

Maps over the entries of the Trie using the specified function.

Example

import * as assert from "node:assert"
import { Trie, Equal } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1), Trie.insert("she", 2))

const trieMapV = Trie.empty<number>().pipe(Trie.insert("shells", 1), Trie.insert("sells", 2), Trie.insert("she", 3))

const trieMapK = Trie.empty<number>().pipe(Trie.insert("shells", 6), Trie.insert("sells", 5), Trie.insert("she", 3))

assert.equal(
  Equal.equals(
    Trie.map(trie, (v) => v + 1),
    trieMapV
  ),
  true
)
assert.equal(
  Equal.equals(
    Trie.map(trie, (_, k) => k.length),
    trieMapK
  ),
  true
)

Signature

declare const map: {
  <A, V>(f: (value: V, key: string) => A): (self: Trie<V>) => Trie<A>
  <V, A>(self: Trie<V>, f: (value: V, key: string) => A): Trie<A>
}

Since v2.0.0

reduce

Reduce a state over the entries of the Trie.

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1), Trie.insert("she", 2))

assert.equal(trie.pipe(Trie.reduce(0, (acc, n) => acc + n)), 3)
assert.equal(trie.pipe(Trie.reduce(10, (acc, n) => acc + n)), 13)
assert.equal(trie.pipe(Trie.reduce("", (acc, _, key) => acc + key)), "sellssheshells")

Signature

declare const reduce: {
  <Z, V>(zero: Z, f: (accumulator: Z, value: V, key: string) => Z): (self: Trie<V>) => Z
  <Z, V>(self: Trie<V>, zero: Z, f: (accumulator: Z, value: V, key: string) => Z): Z
}

Since v2.0.0

getters

entries

Returns an IterableIterator of the entries within the Trie.

The entries are returned by keys in alphabetical order, regardless of insertion order.

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("call", 0), Trie.insert("me", 1))

const result = Array.from(Trie.entries(trie))
assert.deepStrictEqual(result, [
  ["call", 0],
  ["me", 1]
])

Signature

declare const entries: <V>(self: Trie<V>) => IterableIterator<[string, V]>

Since v2.0.0

entriesWithPrefix

Returns an IterableIterator of the entries within the Trie that have prefix as prefix (prefix included if it exists).

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(
  Trie.insert("she", 0),
  Trie.insert("shells", 1),
  Trie.insert("sea", 2),
  Trie.insert("shore", 3)
)

const result = Array.from(Trie.entriesWithPrefix(trie, "she"))
assert.deepStrictEqual(result, [
  ["she", 0],
  ["shells", 1]
])

Signature

declare const entriesWithPrefix: {
  (prefix: string): <V>(self: Trie<V>) => IterableIterator<[string, V]>
  <V>(self: Trie<V>, prefix: string): IterableIterator<[string, V]>
}

Since v2.0.0

keys

Returns an IterableIterator of the keys within the Trie.

The keys are returned in alphabetical order, regardless of insertion order.

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("cab", 0), Trie.insert("abc", 1), Trie.insert("bca", 2))

const result = Array.from(Trie.keys(trie))
assert.deepStrictEqual(result, ["abc", "bca", "cab"])

Signature

declare const keys: <V>(self: Trie<V>) => IterableIterator<string>

Since v2.0.0

keysWithPrefix

Returns an IterableIterator of the keys within the Trie that have prefix as prefix (prefix included if it exists).

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(
  Trie.insert("she", 0),
  Trie.insert("shells", 1),
  Trie.insert("sea", 2),
  Trie.insert("shore", 3)
)

const result = Array.from(Trie.keysWithPrefix(trie, "she"))
assert.deepStrictEqual(result, ["she", "shells"])

Signature

declare const keysWithPrefix: {
  (prefix: string): <V>(self: Trie<V>) => IterableIterator<string>
  <V>(self: Trie<V>, prefix: string): IterableIterator<string>
}

Since v2.0.0

longestPrefixOf

Returns the longest key/value in the Trie that is a prefix of that key if it exists, None otherwise.

Example

import * as assert from "node:assert"
import { Trie, Option } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1), Trie.insert("she", 2))

assert.deepStrictEqual(Trie.longestPrefixOf(trie, "sell"), Option.none())
assert.deepStrictEqual(Trie.longestPrefixOf(trie, "sells"), Option.some(["sells", 1]))
assert.deepStrictEqual(Trie.longestPrefixOf(trie, "shell"), Option.some(["she", 2]))
assert.deepStrictEqual(Trie.longestPrefixOf(trie, "shellsort"), Option.some(["shells", 0]))

Signature

declare const longestPrefixOf: {
  (key: string): <V>(self: Trie<V>) => Option<[string, V]>
  <V>(self: Trie<V>, key: string): Option<[string, V]>
}

Since v2.0.0

size

Returns the size of the Trie (number of entries in the Trie).

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("a", 0), Trie.insert("b", 1))

assert.equal(Trie.size(trie), 2)

Signature

declare const size: <V>(self: Trie<V>) => number

Since v2.0.0

toEntries

Returns an Array<[K, V]> of the entries within the Trie.

Equivalent to Array.from(Trie.entries(trie)).

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("call", 0), Trie.insert("me", 1))
const result = Trie.toEntries(trie)

assert.deepStrictEqual(result, [
  ["call", 0],
  ["me", 1]
])

Signature

declare const toEntries: <V>(self: Trie<V>) => Array<[string, V]>

Since v2.0.0

toEntriesWithPrefix

Returns Array<[K, V]> of the entries within the Trie that have prefix as prefix (prefix included if it exists).

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(
  Trie.insert("shells", 0),
  Trie.insert("sells", 1),
  Trie.insert("sea", 2),
  Trie.insert("she", 3)
)

const result = Trie.toEntriesWithPrefix(trie, "she")
assert.deepStrictEqual(result, [
  ["she", 3],
  ["shells", 0]
])

Signature

declare const toEntriesWithPrefix: {
  (prefix: string): <V>(self: Trie<V>) => Array<[string, V]>
  <V>(self: Trie<V>, prefix: string): Array<[string, V]>
}

Since v2.0.0

values

Returns an IterableIterator of the values within the Trie.

Values are ordered based on their key in alphabetical order, regardless of insertion order.

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("call", 0), Trie.insert("me", 1), Trie.insert("and", 2))

const result = Array.from(Trie.values(trie))
assert.deepStrictEqual(result, [2, 0, 1])

Signature

declare const values: <V>(self: Trie<V>) => IterableIterator<V>

Since v2.0.0

valuesWithPrefix

Returns an IterableIterator of the values within the Trie that have prefix as prefix (prefix included if it exists).

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(
  Trie.insert("she", 0),
  Trie.insert("shells", 1),
  Trie.insert("sea", 2),
  Trie.insert("shore", 3)
)

const result = Array.from(Trie.valuesWithPrefix(trie, "she"))

// 0: "she", 1: "shells"
assert.deepStrictEqual(result, [0, 1])

Signature

declare const valuesWithPrefix: {
  (prefix: string): <V>(self: Trie<V>) => IterableIterator<V>
  <V>(self: Trie<V>, prefix: string): IterableIterator<V>
}

Since v2.0.0

models

Trie (interface)

Signature

export interface Trie<out Value> extends Iterable<[string, Value]>, Equal, Pipeable, Inspectable {
  readonly [TypeId]: {
    readonly _Value: Covariant<Value>
  }
}

Since v2.0.0

mutations

insert

Insert a new entry in the Trie.

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie1 = Trie.empty<number>().pipe(Trie.insert("call", 0))
const trie2 = trie1.pipe(Trie.insert("me", 1))
const trie3 = trie2.pipe(Trie.insert("mind", 2))
const trie4 = trie3.pipe(Trie.insert("mid", 3))

assert.deepStrictEqual(Array.from(trie1), [["call", 0]])
assert.deepStrictEqual(Array.from(trie2), [
  ["call", 0],
  ["me", 1]
])
assert.deepStrictEqual(Array.from(trie3), [
  ["call", 0],
  ["me", 1],
  ["mind", 2]
])
assert.deepStrictEqual(Array.from(trie4), [
  ["call", 0],
  ["me", 1],
  ["mid", 3],
  ["mind", 2]
])

Signature

declare const insert: {
  <V1>(key: string, value: V1): <V>(self: Trie<V>) => Trie<V | V1>
  <V1, V>(self: Trie<V>, key: string, value: V1): Trie<V | V1>
}

Since v2.0.0

insertMany

Insert multiple entries in the Trie at once.

Example

import * as assert from "node:assert"
import { Trie, Equal } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1), Trie.insert("she", 2))

const trieInsert = Trie.empty<number>().pipe(
  Trie.insert("shells", 0),
  Trie.insertMany([
    ["sells", 1],
    ["she", 2]
  ])
)

assert.equal(Equal.equals(trie, trieInsert), true)

Signature

declare const insertMany: {
  <V1>(iter: Iterable<[string, V1]>): <V>(self: Trie<V>) => Trie<V | V1>
  <V1, V>(self: Trie<V>, iter: Iterable<[string, V1]>): Trie<V | V1>
}

Since v2.0.0

modify

Updates the value of the specified key within the Trie if it exists.

Example

import * as assert from "node:assert"
import { Trie, Equal, Option } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1), Trie.insert("she", 2))

assert.deepStrictEqual(
  trie.pipe(
    Trie.modify("she", (v) => v + 10),
    Trie.get("she")
  ),
  Option.some(12)
)

assert.equal(Equal.equals(trie.pipe(Trie.modify("me", (v) => v)), trie), true)

Signature

declare const modify: {
  <V1, V>(key: string, f: (v: V) => V1): (self: Trie<V>) => Trie<V1 | V>
  <V1, V>(self: Trie<V>, key: string, f: (v: V) => V1): Trie<V | V1>
}

Since v2.0.0

remove

Remove the entry for the specified key in the Trie.

Example

import * as assert from "node:assert"
import { Trie, Option } from "effect"

const trie = Trie.empty<number>().pipe(
  Trie.insert("call", 0),
  Trie.insert("me", 1),
  Trie.insert("mind", 2),
  Trie.insert("mid", 3)
)

const trie1 = trie.pipe(Trie.remove("call"))
const trie2 = trie1.pipe(Trie.remove("mea"))

assert.deepStrictEqual(Trie.get(trie, "call"), Option.some(0))
assert.deepStrictEqual(Trie.get(trie1, "call"), Option.none())
assert.deepStrictEqual(Trie.get(trie2, "call"), Option.none())

Signature

declare const remove: { (key: string): <V>(self: Trie<V>) => Trie<V>; <V>(self: Trie<V>, key: string): Trie<V> }

Since v2.0.0

removeMany

Removes all entries in the Trie which have the specified keys.

Example

import * as assert from "node:assert"
import { Trie, Equal } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("shells", 0), Trie.insert("sells", 1), Trie.insert("she", 2))

assert.equal(
  Equal.equals(trie.pipe(Trie.removeMany(["she", "sells"])), Trie.empty<number>().pipe(Trie.insert("shells", 0))),
  true
)

Signature

declare const removeMany: {
  (keys: Iterable<string>): <V>(self: Trie<V>) => Trie<V>
  <V>(self: Trie<V>, keys: Iterable<string>): Trie<V>
}

Since v2.0.0

symbol

TypeId (type alias)

Signature

type TypeId = typeof TypeId

Since v2.0.0

traversing

forEach

Applies the specified function to the entries of the Trie.

Example

import * as assert from "node:assert"
import { Trie } from "effect"

let value = 0

Trie.empty<number>().pipe(
  Trie.insert("shells", 0),
  Trie.insert("sells", 1),
  Trie.insert("she", 2),
  Trie.forEach((n, key) => {
    value += n + key.length
  })
)

assert.equal(value, 17)

Signature

declare const forEach: {
  <V>(f: (value: V, key: string) => void): (self: Trie<V>) => void
  <V>(self: Trie<V>, f: (value: V, key: string) => void): void
}

Since v2.0.0

unsafe

unsafeGet

Unsafely lookup the value for the specified key in the Trie.

unsafeGet will throw if the key is not found. Use get instead to safely get a value from the Trie.

Example

import * as assert from "node:assert"
import { Trie } from "effect"

const trie = Trie.empty<number>().pipe(Trie.insert("call", 0), Trie.insert("me", 1))

assert.throws(() => Trie.unsafeGet(trie, "mae"))

Signature

declare const unsafeGet: { (key: string): <V>(self: Trie<V>) => V; <V>(self: Trie<V>, key: string): V }

Since v2.0.0