Skip to content
Effect 4.0 is here. One ecosystem. Zero dependencies.

Trie

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.

30 exports Since v2.0.0 Source

Constructors

empty

Since v2.0.0

Creates an empty Trie.

Signature

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

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), [])

fromIterable

Since v2.0.0

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

Signature

declare const fromIterable: <V>(entries: Iterable<readonly [string, V]>) => Trie<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)

make

Since v2.0.0

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

Signature

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

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)

Elements

get

Since v2.0.0

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

Signature

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

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())

has

Since v2.0.0

Check if the given key exists in the Trie.

Signature

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

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)

isEmpty

Since v2.0.0

Checks if the Trie contains any entries.

Signature

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

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)

Filtering

compact

Since v2.0.0

Filters out None values from a Trie of Optionss.

Signature

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

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)

filter

Since v2.0.0

Filters entries out of a Trie using the specified predicate.

Signature

declare const filter: {
  <A, B>(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>(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 * 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)

filterMap

Since v2.0.0

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

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>;
}

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
)

Folding

map

Since v2.0.0

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

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>;
}

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)

reduce

Since v2.0.0

Reduce a state over the entries of the Trie.

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;
}

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"
)

Getters

entries

Since v2.0.0

Returns an IterableIterator of the entries within the Trie.

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

Signature

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

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]])

entriesWithPrefix

Since v2.0.0

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

Signature

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

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]])

keys

Since v2.0.0

Returns an IterableIterator of the keys within the Trie.

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

Signature

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

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"])

keysWithPrefix

Since v2.0.0

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

Signature

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

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"])

longestPrefixOf

Since v2.0.0

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

Signature

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

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]))

size

Since v2.0.0

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

Signature

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

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)

toEntries

Since v2.0.0

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

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

Signature

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

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]])

toEntriesWithPrefix

Since v2.0.0

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

Signature

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

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]])

values

Since v2.0.0

Returns an IterableIterator of the values within the Trie.

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

Signature

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

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])

valuesWithPrefix

Since v2.0.0

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

Signature

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

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])

Models

Trie

interface
Since v2.0.0

Signature

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

Mutations

insert

Since v2.0.0

Insert a new entry in the Trie.

Signature

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

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]])

insertMany

Since v2.0.0

Insert multiple entries in the Trie at once.

Signature

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

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
)

modify

Since v2.0.0

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

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<V1 | V>;
}

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)

remove

Since v2.0.0

Remove the entry for the specified key in the Trie.

Signature

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

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())

removeMany

Since v2.0.0

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

Signature

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

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
)

Symbol

TypeId

type
Since v2.0.0

Signature

type TypeId = typeof TypeId

Traversing

forEach

Since v2.0.0

Applies the specified function to the entries of the Trie.

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;
}

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)

Unsafe

unsafeGet

Since v2.0.0

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

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

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"))