NAME

FP::Trie - purely functional prefix tree

SYNOPSIS

    use FP::Trie;

    my $t= empty_trie->set(string_to_list ("Hello"), "World");
    $t->perhaps_ref(string_to_list("Hell")); # ()
    if (my ($subt)= $t->perhaps_skip(string_to_list("Hell"))) {
        print $subt->sublevels_length;
        if (my ($v)= $subt->perhaps_ref(string_to_list("o"))) {
            print $v;
        }
    }
    # -> prints "1World"

    $t->maybe_ref ($keylist)
    $t->ref ($keylist)
    $t->ref_or ($keylist, $alternativevalue)
    $t->exists ($keylist) # boolean

    $t->xdelete(string_to_list("Hello"))
      ->delete(string_to_list("Hello"))  # silently does not change anything;
      ->xdelete(string_to_list("Hello")) # throws "key not found" exception

    $t->keys   # stream of keys
    $t->values # stream of values
    $t->alist  # stream of [ key, value ]

    $t->update($keylist, $fn) # $fn receives () if no such value is in
                              # the trie; if it returns (), the entry
                              # will be deleted

DESCRIPTION

The trie operations expect an efficiently dissectable sequence (linked list, stream) as the key. Each item denotes the next level in the nested trie levels. The items in the list can be anything with a sensible stringification. To use FP::Trie for string keys, turn the strings to character lists using `string_to_list`.

`perhaps_skip` returns the remainder of the trie with the given prefix skipped (again a trie, if available).

`skip` returns ($ending_level, $maybe_keyremainder, $maybe_lastvaluelevel, $maybe_keyremainder_lvl), where $maybe_keyremainder is the remainder of the key list after the last matching level, $ending_level is that level, and $maybe_lastvaluelevel is the last level holding a value and $maybe_keyremainder_lvl the remainder of the key at that point.

PERFORMANCE

Update performance is bad because we don't have an efficiently updatable pure (hash) table datastructure yet.

NAMES

Are the method names ok? What names are other common implementations using? (todo: check Hoogle etc.)

NOTE

This is alpha software! Read the status section in the package README or on the website.