Skip to content
Effect Days 2026 Get your ticket

Trie

Stores string-keyed values in an immutable prefix tree.

A Trie<Value> is similar to a map whose keys are strings, but it is built for looking up keys by prefix. It is useful for autocomplete, route tables, dictionaries, and command lookup. Updates return new tries, and the module includes exact lookup, prefix lookup, longest-prefix lookup, iteration, mapping, filtering, reducing, and traversal helpers.

29 exports Added in v2.0.0 Source

Constructors

empty

Added in v2.0.0 Source

Creates an empty Trie.

Signature

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

Example

(Creating an empty trie)

import { Trie } from "effect"


const trie = Trie.empty<string>()


Trie.size(trie) // => 0
Array.from(trie) // => []

fromIterable

Added in v2.0.0 Source

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

(Creating a trie from entries)

import { Trie } 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
Array.from(trie) // => [["call", 0], ["me", 1], ["mid", 3], ["mind", 2]]
trie // => Trie.make(["call", 0], ["me", 1], ["mind", 2], ["mid", 3])

make

Added in v2.0.0 Source

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

(Constructing a trie from entries)

import { Trie } from "effect"


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


Array.from(trie) // => [["ca", 0], ["me", 1]]
trie // => Trie.fromIterable([["ca", 0], ["me", 1]])

Filtering

compact

Added in v2.0.0 Source

Filters out None values from a Trie of Optionss.

Signature

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

Example

(Compacting optional values)

import { Option, Trie } 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))
)


Trie.compact(trie) // => Trie.make(["shells", 0], ["she", 2])

filter

Added in v2.0.0 Source

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

(Filtering entries)

import { Trie } from "effect"


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


Trie.filter(trie, (v) => v > 1) // => Trie.make(["she", 2])
Trie.filter(trie, (_, k) => k.length > 3) // => Trie.make(["shells", 0], ["sells", 1])

filterMap

Added in v2.0.0 Source

Maps over the entries of the Trie using the specified filter and keeps only successful results.

Signature

declare const filterMap: {
  <A, B, X>(f: (input: A, key: string) => Result<B, X>): (self: Trie<A>) => Trie<B>;
  <A, B, X>(self: Trie<A>, f: (input: A, key: string) => Result<B, X>): Trie<B>;
}

Example

(Filtering and mapping entries)

import { Result, Trie } from "effect"


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


Trie.filterMap(trie, (v) => v > 1 ? Result.succeed(v) : Result.failVoid) // => Trie.make(["she", 2])
Trie.filterMap(
  trie,
  (v, k) => k.length > 3 ? Result.succeed(v) : Result.failVoid
) // => Trie.make(["shells", 0], ["sells", 1])

Folding

map

Added in v2.0.0 Source

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

(Mapping entries)

import { Trie } from "effect"


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


Trie.map(trie, (v) => v + 1) // => Trie.make(["shells", 1], ["sells", 2], ["she", 3])
Trie.map(trie, (_, k) => k.length) // => Trie.make(["shells", 6], ["sells", 5], ["she", 3])

reduce

Added in v2.0.0 Source

Reduces 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

(Reducing entries)

import { Trie } from "effect"


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


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

Getters

entries

Added in v2.0.0 Source

Returns an IterableIterator of the entries within the Trie.

Details

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

(Reading entries in alphabetical order)

import { Trie } from "effect"


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


Array.from(Trie.entries(trie)) // => [["call", 0], ["me", 1]]

entriesWithPrefix

Added in v2.0.0 Source

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

(Finding entries with a prefix)

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


Array.from(Trie.entriesWithPrefix(trie, "she")) // => [["she", 0], ["shells", 1]]

get

Added in v2.0.0 Source

Looks up the value for the specified key in the Trie safely.

Signature

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

Example

(Looking up values safely)

import { Option, 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)
)


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

keys

Added in v2.0.0 Source

Returns an IterableIterator of the keys within the Trie.

Details

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

Signature

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

Example

(Reading keys in alphabetical order)

import { Trie } from "effect"


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


Array.from(Trie.keys(trie)) // => ["abc", "bca", "cab"]

keysWithPrefix

Added in v2.0.0 Source

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

(Finding keys with a prefix)

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


Array.from(Trie.keysWithPrefix(trie, "she")) // => ["she", "shells"]

longestPrefixOf

Added in v2.0.0 Source

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

(Finding the longest prefix)

import { Option, Trie } from "effect"


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


Trie.longestPrefixOf(trie, "sell") // => Option.none()
Trie.longestPrefixOf(trie, "sells") // => Option.some(["sells", 1])

size

Added in v2.0.0 Source

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

Signature

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

Example

(Getting the size)

import { Trie } from "effect"


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


Trie.size(trie) // => 2

toEntries

Added in v2.0.0 Source

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

Details

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

Signature

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

Example

(Converting entries to an array)

import { Trie } from "effect"


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

toEntriesWithPrefix

Added in v2.0.0 Source

Returns an Array<[string, V]> of the entries within the Trie whose keys start with prefix, including the entry for prefix itself when 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

(Converting prefixed entries to an array)

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


Trie.toEntriesWithPrefix(trie, "she") // => [["she", 3], ["shells", 0]]

values

Added in v2.0.0 Source

Returns an IterableIterator of the values within the Trie.

Details

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

(Reading values by key order)

import { Trie } from "effect"


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


Array.from(Trie.values(trie)) // => [2, 0, 1]

valuesWithPrefix

Added in v2.0.0 Source

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

(Finding values with a prefix)

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


Array.from(Trie.valuesWithPrefix(trie, "she")) // => [0, 1]

Models

Trie interface

Added in v2.0.0 Source

An immutable string-keyed map optimized for prefix lookup. Iteration yields [key, value] pairs in key order, and update operations such as insert and remove return new Trie values.

Signature

interface Trie<in out Value> extends Iterable<[string, Value]>, Equal, Pipeable, Inspectable {
  readonly "~effect/collections/Trie": {
    readonly _Value: Covariant<Value>;
  };
}

Example

(Using a trie for prefix search)

import { Option, Trie } from "effect"


// Create a trie with string-to-number mappings
const trie: Trie.Trie<number> = Trie.make(
  ["apple", 1],
  ["app", 2],
  ["application", 3],
  ["banana", 4]
)


// Get values by exact key
Trie.get(trie, "apple") // => Option.some(1)
Trie.get(trie, "grape") // => Option.none()


// Find all keys with a prefix
Array.from(Trie.keysWithPrefix(trie, "app")) // => ["app", "apple", "application"]


// Iterate over all entries (sorted alphabetically)
Array.from(trie) // => [["app", 2], ["apple", 1], ["application", 3], ["banana", 4]]


// Check if key exists
Trie.has(trie, "app") // => true


// Get size
Trie.size(trie) // => 4

Mutations

insert

Added in v2.0.0 Source

Inserts a new entry in the Trie.

Signature

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

Example

(Inserting entries)

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


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

insertMany

Added in v2.0.0 Source

Inserts multiple entries in the Trie at once.

Signature

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

Example

(Inserting multiple entries)

import { Trie } from "effect"


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


trie.pipe(
  Trie.insertMany([["sells", 1], ["she", 2]])
) // => Trie.make(["shells", 0], ["sells", 1], ["she", 2])

modify

Added in v2.0.0 Source

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

Signature

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

Example

(Modifying an existing value)

import { Option, Trie } from "effect"


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


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

remove

Added in v2.0.0 Source

Removes 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

(Removing entries)

import { Option, 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)
)


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


Trie.get(trie, "call") // => Option.some(0)
Trie.get(trie1, "call") // => Option.none()
Trie.get(trie2, "call") // => Option.none()

removeMany

Added in v2.0.0 Source

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

(Removing multiple entries)

import { Trie } from "effect"


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


trie.pipe(Trie.removeMany(["she", "sells"])) // => Trie.make(["shells", 0])

Predicates

has

Added in v2.0.0 Source

Checks whether 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

(Checking key membership)

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


Trie.has(trie, "call") // => true
Trie.has(trie, "me") // => true
Trie.has(trie, "mind") // => true
Trie.has(trie, "mid") // => true
Trie.has(trie, "cale") // => false
Trie.has(trie, "ma") // => false
Trie.has(trie, "midn") // => false
Trie.has(trie, "mea") // => false

isEmpty

Added in v2.0.0 Source

Returns true when the Trie contains no entries.

Signature

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

Example

(Checking whether a trie is empty)

import { Trie } from "effect"


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


Trie.isEmpty(trie) // => true
Trie.isEmpty(trie1) // => false

Traversing

forEach

Added in v2.0.0 Source

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

(Iterating over entries)

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


value // => 17

Unsafe

getUnsafe

Added in v4.0.0 Source

Looks up the value for the specified key in the Trie unsafely.

When to use

Use when the trie key is known to exist and a missing key should be treated as a programming error.

Gotchas

getUnsafe throws if the key is not found. Use get instead to safely get a value from the Trie.

Signature

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

Example

(Looking up values unsafely)

import { Result, Trie } from "effect"


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


Result.try({
  try: () => Trie.getUnsafe(trie, "mae"),
  catch: (error) => (error as Error).message
}) // => Result.fail("Expected trie to contain key")