Module trie

Description
Data Types
Function Index
Function Details

A trie data structure implementation.

The trie (i.e., from "retrieval") data structure was invented by Edward Fredkin (it is a form of radix sort). The implementation stores string suffixes as a list because it is a PATRICIA trie (PATRICIA - Practical Algorithm to Retrieve Information Coded in Alphanumeric, D.R.Morrison (1968)).

Version: 2.0.8 Apr 17 2026 11:03:15 ------------------------------------------------------------------------

Authors: Michael Truog (mjtruog at protonmail dot com).

Description

A trie data structure implementation.

This Erlang trie implementation uses string (list of integers) keys and is able to get performance close to the process dictionary when doing key lookups (find or fetch, see http://okeuday.livejournal.com/16941.html). Utilizing this trie, it is possible to avoid generating dynamic atoms in various contexts. Also, an added benefit to using this trie is that the traversals preserve alphabetical ordering.

Data Types

empty_trie()

empty_trie() = []

nonempty_trie()

nonempty_trie() = {integer(), integer(), tuple()}

trie()

trie() = nonempty_trie() | empty_trie()

Function Index

append/3
append_list/3
erase/2
erase_similar/2
fetch/2
fetch_keys/1
fetch_keys_similar/2
filter/2
find/2
find_match/2	Find a match with patterns held within a trie. All patterns held within the trie use a wildcard character "*" to represent a regex of ".+".
find_match2/2	Find a match with patterns (using 2 wildcard characters) held within a trie. All patterns held within the trie use the wildcard character "*" or "?" to represent a regex of ".+".
find_prefix/2
find_prefix_longest/2
find_prefixes/2
find_similar/2	Find the first key/value pair in a trie where the key shares a common prefix. The first match is found based on alphabetical order.
fold/3
fold_match/4	Fold a function over the keys within a trie that matches a pattern. Traverses in alphabetical order.
fold_similar/4
foldl/3
foldl_similar/4
foldr/3
foldr_similar/4
foreach/2
from_list/1
is_bytestring/1	Test if the parameter is a byte string. .
is_bytestring_nonempty/1	Test if the parameter is a nonempty byte string. .
is_key/2
is_pattern/1	Test to determine if a string is a pattern. "*" is the wildcard character (equivalent to the ".+" regex).
is_pattern2/1	Test to determine if a string is a pattern (using 2 wildcard characters). "*" and "?" are wildcard characters (equivalent to the ".+" regex).
is_pattern2_bytes/1	Test to determine if a byte string is a pattern (using 2 wildcard characters). "*" and "?" are wildcard characters (equivalent to the ".+" regex).
is_pattern_bytes/1	Test to determine if a byte string is a pattern. "*" is the wildcard character (equivalent to the ".+" regex).
is_prefix/2	Determine if the prefix provided has existed within a trie. The function returns true if the string supplied is a prefix for a key that has previously been stored within the trie.
is_prefixed/2	Determine if the provided string has a prefix within a trie. .
is_prefixed/3	Determine if the provided string has an acceptable prefix within a trie. The prefix within the trie must match at least 1 character that is not within the excluded list of characters.
iter/2	Iterate over a trie. Traverses in alphabetical order.
itera/3	Iterate over a trie with an accumulator. Traverses in alphabetical order.
map/2
merge/3
new/0
new/1
pattern2_fill/2	Fill wildcard characters in a string. The "*" and "?" wildcard characters may be used consecutively by this function to have parameters concatenated (both are processed the same way by this function).
pattern2_fill/4	Fill wildcard characters in a string. The "*" and "?" wildcard characters may be used consecutively by this function to have parameters concatenated (both are processed the same way by this function).
pattern2_parse/2	Parse a string based on the supplied wildcard pattern (using 2 wildcard characters). "*" and "?" are wildcard characters (equivalent to the ".+" regex).
pattern2_parse/3	Parse a string based on the supplied wildcard pattern (using 2 wildcard characters). "*" and "?" are wildcard characters (equivalent to the ".+" regex).
pattern2_suffix/2	Parse a string based on the supplied wildcard pattern (using 2 wildcard characters) to return only the suffix after the pattern. "*" and "?" are wildcard characters (equivalent to the ".+" regex).
pattern_fill/2	Fill wildcard characters in a string. The "*" wildcard character may be used consecutively by this function to have parameters concatenated.
pattern_fill/4	Fill wildcard characters in a string. The "*" wildcard character may be used consecutively by this function to have parameters concatenated.
pattern_parse/2	Parse a string based on the supplied wildcard pattern. "*" is the wildcard character (equivalent to the ".+" regex).
pattern_parse/3	Parse a string based on the supplied wildcard pattern. "*" is the wildcard character (equivalent to the ".+" regex).
pattern_suffix/2	Parse a string based on the supplied wildcard pattern to return only the suffix after the pattern. "*" is the wildcard character (equivalent to the ".+" regex).
prefix/3
size/1
store/2
store/3
take/2
to_list/1
to_list_similar/2
update/3
update/4
update_counter/3

Function Details

append/3

append(Key::nonempty_string(), Value::any(), Node::trie()) -> nonempty_trie()

append_list/3

append_list(Key::nonempty_string(), ValueList::list(), Node::trie()) -> nonempty_trie()

erase/2

erase(Key::nonempty_string(), Node::trie()) -> trie()

erase_similar/2

erase_similar(Similar::nonempty_string(), Node::trie()) -> [nonempty_string()]

fetch/2

fetch(T::nonempty_string(), Node::nonempty_trie()) -> any()

fetch_keys/1

fetch_keys(Node::trie()) -> [nonempty_string()]

fetch_keys_similar/2

fetch_keys_similar(Similar::nonempty_string(), Node::trie()) -> [nonempty_string()]

filter/2

filter(F::fun((nonempty_string(), any()) -> boolean()), Node::trie()) -> trie()

find/2

find(T::nonempty_string(), Node::trie()) -> {ok, any()} | error

find_match/2

find_match(Match::string(), Node::trie()) -> {ok, any(), any()} | error

Find a match with patterns held within a trie.

All patterns held within the trie use a wildcard character "*" to represent a regex of ".+". "**" within the trie will result in undefined behavior (the pattern is malformed). The function will search for the most specific match possible, given the input string and the trie contents. The input string must not contain wildcard characters, otherwise a badarg exit exception will occur. If you instead want to supply a pattern string to match the contents of the trie, see fold_match/4.

find_match2/2

find_match2(Match::string(), Node::trie()) -> {ok, any(), any()} | error

Find a match with patterns (using 2 wildcard characters) held within a trie.

All patterns held within the trie use the wildcard character "*" or "?" to represent a regex of ".+". "**", "??", "*?", or "?*" within the trie will result in undefined behavior (the pattern is malformed). The function will search for the most specific match possible, given the input string and the trie contents. The input string must not contain wildcard characters, otherwise a badarg exit exception will occur. The "?" wildcard character consumes the shortest match to the next character and must not be the the last character in the string (the pattern would be malformed).

find_prefix/2

find_prefix(T::nonempty_string(), X2::trie()) -> {ok, any()} | prefix | error

find_prefix_longest/2

find_prefix_longest(Match::nonempty_string(), Node::trie()) -> {ok, nonempty_string(), any()} | error

find_prefixes/2

find_prefixes(Match::nonempty_string(), Node::trie()) -> [{nonempty_string(), any()}]

find_similar/2

find_similar(Similar::string(), Node::trie()) -> {ok, string(), any()} | error

Find the first key/value pair in a trie where the key shares a common prefix.

The first match is found based on alphabetical order.

fold/3

fold(F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

fold_match/4

fold_match(Match::string(), F::fun((string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

Fold a function over the keys within a trie that matches a pattern.

Traverses in alphabetical order. Uses "*" as a wildcard character within the pattern (it acts like a ".+" regex, and "**" is forbidden). The trie keys must not contain wildcard characters, otherwise a badarg exit exception will occur. If you want to match a specific string without wildcards on trie values that contain wildcard characters, see find_match/2.

fold_similar/4

fold_similar(Similar::nonempty_string(), F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

foldl/3

foldl(F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

foldl_similar/4

foldl_similar(Similar::nonempty_string(), F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

foldr/3

foldr(F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

foldr_similar/4

foldr_similar(Similar::nonempty_string(), F::fun((nonempty_string(), any(), any()) -> any()), A::any(), Node::trie()) -> any()

foreach/2

foreach(F::fun((nonempty_string(), any()) -> any()), Node::trie()) -> any()

from_list/1

from_list(L::[nonempty_string() | tuple()]) -> trie()

is_bytestring/1

is_bytestring(L::[byte()]) -> true | false

Test if the parameter is a byte string.

is_bytestring_nonempty/1

is_bytestring_nonempty(L::[byte(), ...]) -> true | false

Test if the parameter is a nonempty byte string.

is_key/2

is_key(T::nonempty_string(), Node::trie()) -> boolean()

is_pattern/1

is_pattern(Pattern::string()) -> true | false

Test to determine if a string is a pattern.

"*" is the wildcard character (equivalent to the ".+" regex). "**" is forbidden.

is_pattern2/1

is_pattern2(Pattern::string()) -> true | false

Test to determine if a string is a pattern (using 2 wildcard characters).

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

is_pattern2_bytes/1

is_pattern2_bytes(Pattern::[byte()]) -> true | false

Test to determine if a byte string is a pattern (using 2 wildcard characters).

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

is_pattern_bytes/1

is_pattern_bytes(Pattern::[byte()]) -> true | false

Test to determine if a byte string is a pattern.

"*" is the wildcard character (equivalent to the ".+" regex). "**" is forbidden.

is_prefix/2

is_prefix(T::string(), X2::trie()) -> true | false

Determine if the prefix provided has existed within a trie.

The function returns true if the string supplied is a prefix for a key that has previously been stored within the trie. If no values with the prefix matching key(s) were removed from the trie, then the prefix currently exists within the trie.

is_prefixed/2

is_prefixed(T::string(), X2::trie()) -> true | false

Determine if the provided string has a prefix within a trie.

is_prefixed/3

is_prefixed(Key::string(), Exclude::string(), Node::trie()) -> true | false

Determine if the provided string has an acceptable prefix within a trie.

The prefix within the trie must match at least 1 character that is not within the excluded list of characters.

iter/2

iter(F::fun((string(), any(), fun(() -> any())) -> any()), Node::trie()) -> ok

Iterate over a trie.

Traverses in alphabetical order.

itera/3

itera(F::fun((string(), any(), any(), fun((any()) -> any())) -> any()), A::any(), Node::trie()) -> any()

Iterate over a trie with an accumulator.

Traverses in alphabetical order.

map/2

map(F::fun((nonempty_string(), any()) -> any()), Node::trie()) -> trie()

merge/3

merge(F::fun((nonempty_string(), any(), any()) -> any()), Node1::trie(), Node2::trie()) -> trie()

new/0

new() -> empty_trie()

new/1

new(L::[nonempty_string() | tuple()]) -> trie()

pattern2_fill/2

pattern2_fill(FillPattern::string(), Parameters::[string()]) -> {ok, string()} | {error, parameters_ignored | parameter_missing}

Fill wildcard characters in a string.

The "*" and "?" wildcard characters may be used consecutively by this function to have parameters concatenated (both are processed the same way by this function).

pattern2_fill/4

pattern2_fill(FillPattern::string(), Parameters::[string()], ParametersSelected::[pos_integer()], ParametersStrictMatching::boolean()) -> {ok, string()} | {error, parameters_ignored | parameter_missing | parameters_selected_empty | {parameters_selected_ignored, [pos_integer()]} | {parameters_selected_missing, pos_integer()}}

Fill wildcard characters in a string.

The "*" and "?" wildcard characters may be used consecutively by this function to have parameters concatenated (both are processed the same way by this function).

pattern2_parse/2

pattern2_parse(Pattern::string(), L::string()) -> [string()] | error

Parse a string based on the supplied wildcard pattern (using 2 wildcard characters).

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

pattern2_parse/3

pattern2_parse(Pattern::string(), L::string(), Option::default | with_suffix | expanded) -> [string()] | {[string()], string()} | [string() | {exact, string()}] | error

Parse a string based on the supplied wildcard pattern (using 2 wildcard characters).

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

pattern2_suffix/2

pattern2_suffix(Pattern::string(), L::string()) -> string() | error

Parse a string based on the supplied wildcard pattern (using 2 wildcard characters) to return only the suffix after the pattern.

"*" and "?" are wildcard characters (equivalent to the ".+" regex). "**", "??", "*?" and "?*" are forbidden. "?" must not be the last character in the pattern.

pattern_fill/2

pattern_fill(FillPattern::string(), Parameters::[string()]) -> {ok, string()} | {error, parameters_ignored | parameter_missing}

Fill wildcard characters in a string.

The "*" wildcard character may be used consecutively by this function to have parameters concatenated.

pattern_fill/4

pattern_fill(FillPattern::string(), Parameters::[string()], ParametersSelected::[pos_integer()], ParametersStrictMatching::boolean()) -> {ok, string()} | {error, parameters_ignored | parameter_missing | parameters_selected_empty | {parameters_selected_ignored, [pos_integer()]} | {parameters_selected_missing, pos_integer()}}