tries

This library provides a persistent trie (also known as a prefix tree) that associates complete strings with values. The supported string representations are atoms, lists of character codes, and lists of characters, selected using the trie(atom), trie(codes), and trie(chars) parametric objects. Trie representations are opaque terms and should only be accessed using the library predicates.

API documentation

Open the ../../apis/library_index.html#tries link in a web browser.

Loading

To load all entities in this library, load the loader.lgt file:

| ?- logtalk_load(tries(loader)).

Testing

To test this library predicates, load the tester.lgt file:

| ?- logtalk_load(tries(tester)).

Usage

Select the parametric object matching the desired string representation. For example, to create an atom-based trie from a list of string-value pairs:

| ?- trie(atom)::as_trie([
        ''-default_handler,
        '/users'-users_handler,
        '/users/me'-profile_handler,
        '/usage'-usage_handler
     ], Trie).
Trie = ...
yes

The string in each pair is the complete stored string. The value is arbitrary application data associated with that string. Individual characters and internal trie nodes are not exposed by the API.

For autocomplete-style queries, lookup_prefix/4 enumerates all stored strings beginning with a prefix in lexicographic order:

| ?- trie(atom)::lookup_prefix('/us', String, Handler, Trie).
String = '/usage',
Handler = usage_handler ;
String = '/users',
Handler = users_handler ;
String = '/users/me',
Handler = profile_handler ;
no

The as_list/3, strings/3, and values/3 predicates provide materialized versions of the same prefix-restricted traversal.

A more traditional trie use case is a dictionary of words. For example, long words with a common stem can be stored with their definitions and efficiently enumerated from a partial spelling:

| ?- trie(atom)::as_trie([
        electroencephalogram-'record of brain electrical activity',
        electroencephalograph-'instrument for recording brain electrical activity',
        electroencephalographic-'relating to electroencephalography',
        electroencephalography-'recording of brain electrical activity'
     ], Trie),
     trie(atom)::lookup_prefix(
        electroencephalogra, Word, Definition, Trie
     ).
Word = electroencephalogram,
Definition = 'record of brain electrical activity' ;
Word = electroencephalograph,
Definition = 'instrument for recording brain electrical activity' ;
Word = electroencephalographic,
Definition = 'relating to electroencephalography' ;
Word = electroencephalography,
Definition = 'recording of brain electrical activity' ;
no

For routing-style queries, longest_prefix/4 finds the most specific stored string that prefixes a query:

| ?- trie(atom)::longest_prefix(
        Trie, '/users/me/settings', Prefix, Handler
     ).
Prefix = '/users/me',
Handler = profile_handler
yes

The prefixes/3 predicate returns all matching stored prefixes from shortest to longest. The empty string is a valid stored string and can therefore be used as a default route.

All updates are persistent: insertion, update, exact deletion, and prefix deletion return a new trie and leave the original trie unchanged. Exact deletion preserves longer strings that share the deleted string as a prefix; delete_prefix/3 removes the complete matching subtree.