Trie 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.
Added in v2.0.0
Table of contents
constructors
empty
Creates an empty Trie
.
Signature
export declare const empty: <V = never>() => Trie<V>
Example
import { Trie, Equal } from "effect"
const trie = Trie.empty<string>()
assert.equal(Trie.size(trie), 0)
assert.deepStrictEqual(Array.from(trie), [])
Added in v2.0.0
fromIterable
Creates a new Trie
from an iterable collection of key/value pairs (e.g. Array<[string, V]>
).
Signature
export declare const fromIterable: <V>(entries: Iterable<readonly [string, V]>) => Trie<V>
Example
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)
Added in v2.0.0
make
Constructs a new Trie
from the specified entries ([string, V]
).
Signature
export declare const make: <Entries extends Array<readonly [string, any]>>(
...entries: Entries
) => Trie<Entries[number] extends readonly [any, infer V] ? V : never>
Example
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
)
Added in v2.0.0
elements
get
Safely lookup the value for the specified key in the Trie
.
Signature
export declare const get: { (key: string): <V>(self: Trie<V>) => Option<V>; <V>(self: Trie<V>, key: string): Option<V> }
Example
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())
Added in v2.0.0
has
Check if the given key exists in the Trie
.
Signature
export declare const has: { (key: string): <V>(self: Trie<V>) => boolean; <V>(self: Trie<V>, key: string): boolean }
Example
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)
Added in v2.0.0
isEmpty
Checks if the Trie
contains any entries.
Signature
export declare const isEmpty: <V>(self: Trie<V>) => boolean
Example
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)
Added in v2.0.0
filtering
compact
Filters out None
values from a Trie
of Options
s.
Signature
export declare const compact: <A>(self: Trie<Option<A>>) => Trie<A>
Example
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)
Added in v2.0.0
filter
Filters entries out of a Trie
using the specified predicate.
Signature
export 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>
}
Example
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
)
Added in v2.0.0
filterMap
Maps over the entries of the Trie
using the specified partial function and filters out None
values.
Signature
export 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>
}
Example
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
)
Added in v2.0.0
folding
map
Maps over the entries of the Trie
using the specified function.
Signature
export 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>
}
Example
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
)
Added in v2.0.0
reduce
Reduce a state over the entries of the Trie
.
Signature
export 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
}
Example
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")
Added in 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.
Signature
export declare const entries: <V>(self: Trie<V>) => IterableIterator<[string, V]>
Example
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]
])
Added in v2.0.0
entriesWithPrefix
Returns an IterableIterator
of the entries within the Trie
that have prefix
as prefix (prefix
included if it exists).
Signature
export declare const entriesWithPrefix: {
(prefix: string): <V>(self: Trie<V>) => IterableIterator<[string, V]>
<V>(self: Trie<V>, prefix: string): IterableIterator<[string, V]>
}
Example
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]
])
Added in v2.0.0
keys
Returns an IterableIterator
of the keys within the Trie
.
The keys are returned in alphabetical order, regardless of insertion order.
Signature
export declare const keys: <V>(self: Trie<V>) => IterableIterator<string>
Example
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"])
Added in v2.0.0
keysWithPrefix
Returns an IterableIterator
of the keys within the Trie
that have prefix
as prefix (prefix
included if it exists).
Signature
export declare const keysWithPrefix: {
(prefix: string): <V>(self: Trie<V>) => IterableIterator<string>
<V>(self: Trie<V>, prefix: string): IterableIterator<string>
}
Example
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"])
Added in v2.0.0
longestPrefixOf
Returns the longest key/value in the Trie
that is a prefix of that key
if it exists, None
otherwise.
Signature
export declare const longestPrefixOf: {
(key: string): <V>(self: Trie<V>) => Option<[string, V]>
<V>(self: Trie<V>, key: string): Option<[string, V]>
}
Example
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]))
Added in v2.0.0
size
Returns the size of the Trie
(number of entries in the Trie
).
Signature
export declare const size: <V>(self: Trie<V>) => number
Example
import { Trie } from "effect"
const trie = Trie.empty<number>().pipe(Trie.insert("a", 0), Trie.insert("b", 1))
assert.equal(Trie.size(trie), 2)
Added in v2.0.0
toEntries
Returns an Array<[K, V]>
of the entries within the Trie
.
Equivalent to Array.from(Trie.entries(trie))
.
Signature
export declare const toEntries: <V>(self: Trie<V>) => Array<[string, V]>
Example
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]
])
Added in v2.0.0
toEntriesWithPrefix
Returns Array<[K, V]>
of the entries within the Trie
that have prefix
as prefix (prefix
included if it exists).
Signature
export declare const toEntriesWithPrefix: {
(prefix: string): <V>(self: Trie<V>) => Array<[string, V]>
<V>(self: Trie<V>, prefix: string): Array<[string, V]>
}
Example
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]
])
Added in 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.
Signature
export declare const values: <V>(self: Trie<V>) => IterableIterator<V>
Example
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])
Added in v2.0.0
valuesWithPrefix
Returns an IterableIterator
of the values within the Trie
that have prefix
as prefix (prefix
included if it exists).
Signature
export declare const valuesWithPrefix: {
(prefix: string): <V>(self: Trie<V>) => IterableIterator<V>
<V>(self: Trie<V>, prefix: string): IterableIterator<V>
}
Example
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])
Added in 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>
}
}
Added in v2.0.0
mutations
insert
Insert a new entry in the Trie
.
Signature
export 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>
}
Example
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]
])
Added in v2.0.0
insertMany
Insert multiple entries in the Trie
at once.
Signature
export 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>
}
Example
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)
Added in v2.0.0
modify
Updates the value of the specified key within the Trie
if it exists.
Signature
export 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>
}
Example
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)
Added in v2.0.0
remove
Remove the entry for the specified key in the Trie
.
Signature
export declare const remove: { (key: string): <V>(self: Trie<V>) => Trie<V>; <V>(self: Trie<V>, key: string): Trie<V> }
Example
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())
Added in v2.0.0
removeMany
Removes all entries in the Trie
which have the specified keys.
Signature
export declare const removeMany: {
(keys: Iterable<string>): <V>(self: Trie<V>) => Trie<V>
<V>(self: Trie<V>, keys: Iterable<string>): Trie<V>
}
Example
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
)
Added in v2.0.0
symbol
TypeId (type alias)
Signature
export type TypeId = typeof TypeId
Added in v2.0.0
traversing
forEach
Applies the specified function to the entries of the Trie
.
Signature
export 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
}
Example
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)
Added in 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
.
Signature
export declare const unsafeGet: { (key: string): <V>(self: Trie<V>) => V; <V>(self: Trie<V>, key: string): V }
Example
import { Trie } from "effect"
const trie = Trie.empty<number>().pipe(Trie.insert("call", 0), Trie.insert("me", 1))
assert.throws(() => Trie.unsafeGet(trie, "mae"))
Added in v2.0.0