SuffixTrie

A suffix trie that enables efficient substring searching over stored strings.

It wraps StringTrie internally, storing all suffixes of each inserted string to enable substring lookup. The API mirrors StringTrie for Dict-like operations and adds suffix-trie-specific search functions.

Data structure

type SuffixTrie a

An opaque suffix trie type that maps strings to values and supports efficient substring searching.

Build

empty : SuffixTrie a

Create an empty suffix trie.

singleton : String -> a -> SuffixTrie a

Create a suffix trie with one key-value pair.

insert : String -> a -> SuffixTrie a -> SuffixTrie a

Insert a key-value pair into a suffix trie. Replaces value when there is a collision.

update : String -> (Maybe a -> Maybe a) -> SuffixTrie a -> SuffixTrie a

Update the value of a suffix trie for a specific key with a given function.

remove : String -> SuffixTrie a -> SuffixTrie a

Remove a key-value pair from a suffix trie. If the key is not found, no changes are made.

Query

isEmpty : SuffixTrie a -> Bool

Determine if a suffix trie is empty.

member : String -> SuffixTrie a -> Bool

Determine if a key is in a suffix trie.

get : String -> SuffixTrie a -> Maybe a

Get the value associated with a key.

size : SuffixTrie a -> Int

Determine the number of key-value pairs in the suffix trie.

Lists

keys : SuffixTrie a -> List String

Get all of the keys in a suffix trie, sorted from lowest to highest.

values : SuffixTrie a -> List a

Get all of the values in a suffix trie, in the order of their keys.

toList : SuffixTrie a -> List ( String, a )

Convert a suffix trie into an association list of key-value pairs, sorted by keys.

fromList : List ( String, a ) -> SuffixTrie a

Convert an association list into a suffix trie.

Transform

map : (String -> a -> b) -> SuffixTrie a -> SuffixTrie b

Apply a function to all values in a suffix trie.

foldl : (String -> a -> b -> b) -> b -> SuffixTrie a -> b

Fold over the key-value pairs in a suffix trie from lowest key to highest key.

foldr : (String -> a -> b -> b) -> b -> SuffixTrie a -> b

Fold over the key-value pairs in a suffix trie from highest key to lowest key.

filter : (String -> a -> Bool) -> SuffixTrie a -> SuffixTrie a

Keep only the key-value pairs that pass the given test.

partition : (String -> a -> Bool) -> SuffixTrie a -> ( SuffixTrie a, SuffixTrie a )

Partition a suffix trie according to some test. The first suffix trie contains all key-value pairs which passed the test, and the second contains the pairs that did not.

Combine

union : SuffixTrie a -> SuffixTrie a -> SuffixTrie a

Combine two suffix tries. If there is a collision, preference is given to the first suffix trie.

intersect : SuffixTrie a -> SuffixTrie a -> SuffixTrie a

Keep a key-value pair when its key appears in the second suffix trie. Preference is given to values in the first suffix trie.

diff : SuffixTrie a -> SuffixTrie b -> SuffixTrie a

Keep a key-value pair when its key does not appear in the second suffix trie.

merge :

(String -> a -> result -> result)

-> (String -> a -> b -> result -> result)

-> (String -> b -> result -> result)

-> SuffixTrie a

-> SuffixTrie b

-> result

The most general way of combining two suffix tries.

Prefix search

expand : String -> SuffixTrie a -> List ( String, a )

Given a prefix, finds all entries where the original key starts with that prefix.

expandIgnoreCase : String -> SuffixTrie a -> List ( String, a )

Given a prefix, finds all entries where the original key starts with that prefix, ignoring case.

isPrefix : String -> SuffixTrie a -> Bool

Given a prefix, checks if there are keys that begin with that prefix.

Substring search

isSubstring : String -> SuffixTrie a -> Bool

Does any stored key contain the given substring?

findSubstring : String -> SuffixTrie a -> List ( String, a )

Returns all (key, value) pairs where the key contains the given substring.

findSubstringWithPositions : String -> SuffixTrie a -> List ( String, a, List Int )

Returns all (key, value, positions) triples where the key contains the given substring, along with the character positions where the substring occurs.

findSubstringIgnoreCase : String -> SuffixTrie a -> List ( String, a )

Case-insensitive variant of findSubstring.

Suffix search

isSuffix : String -> SuffixTrie a -> Bool

Is the given string a suffix of any stored key?

findSuffix : String -> SuffixTrie a -> List ( String, a )

Returns all (key, value) pairs where the key ends with the given suffix.

elm-scotland/elm-tries/1.1.0