Skip to content

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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;

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

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

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

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

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

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

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

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

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

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

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

isEmpty

Added in v2.0.0 Source

Returns true when the Trie contains no entries.

Signature

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

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

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