bytestring-trie-0.2.4.1: An efficient finite map from (byte)strings to values.

CopyrightCopyright (c) 2008--2015 wren gayle romano
LicenseBSD3
Maintainerwren@community.haskell.org
Stabilityexperimental
Portabilityportable
Safe HaskellNone
LanguageHaskell98

Data.Trie

Contents

Description

An efficient implementation of finite maps from strings to values. The implementation is based on big-endian patricia trees, like Data.IntMap. We first trie on the elements of Data.ByteString and then trie on the big-endian bit representation of those elements. For further details on the latter, see

  • Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps", Workshop on ML, September 1998, pages 77-86, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452

    • D.R. Morrison, "PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric", Journal of the ACM, 15(4), October 1968, pages 514-534.

This module aims to provide an austere interface, while being detailed enough for most users. For an extended interface with many additional functions, see Data.Trie.Convenience. For functions that give more detailed (potentially abstraction-breaking) access to the data strucuture, or for experimental functions which aren't quite ready for the public API, see Data.Trie.Internal.

Synopsis

Data type

data Trie a Source

A map from ByteStrings to a. For all the generic functions, note that tries are strict in the Maybe but not in a.

The Monad instance is strange. If a key k1 is a prefix of other keys, then results from binding the value at k1 will override values from longer keys when they collide. If this is useful for anything, or if there's a more sensible instance, I'd be curious to know.

Instances

Basic functions

empty :: Trie a Source

O(1), Construct the empty trie.

null :: Trie a -> Bool Source

O(1), Is the trie empty?

singleton :: ByteString -> a -> Trie a Source

O(1), Construct a singleton trie.

size :: Trie a -> Int Source

O(n), Get count of elements in trie.

Conversion functions

fromList :: [(ByteString, a)] -> Trie a Source

Convert association list into a trie. On key conflict, values earlier in the list shadow later ones.

toListBy :: (ByteString -> a -> b) -> Trie a -> [b] Source

Convert a trie into a list using a function. Resulting values are in key-sorted order.

toList :: Trie a -> [(ByteString, a)] Source

Convert trie into association list. Keys will be in sorted order.

keys :: Trie a -> [ByteString] Source

Return all keys in the trie, in sorted order.

elems :: Trie a -> [a] Source

Return all values in the trie, in sorted order according to the keys.

Query functions

lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b Source

Generic function to find a value (if it exists) and the subtrie rooted at the prefix.

lookup :: ByteString -> Trie a -> Maybe a Source

Return the value associated with a query string if it exists.

member :: ByteString -> Trie a -> Bool Source

Does a string have a value in the trie?

submap :: ByteString -> Trie a -> Trie a Source

Return the subtrie containing all keys beginning with a prefix.

match :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString) Source

Given a query, find the longest prefix with an associated value in the trie, returning that prefix, it's value, and the remaining string.

matches :: Trie a -> ByteString -> [(ByteString, a, ByteString)] Source

Given a query, find all prefixes with associated values in the trie, returning the prefixes, their values, and their remaining strings. This function is a good producer for list fusion.

Single-value modification

alterBy :: (ByteString -> a -> Maybe a -> Maybe a) -> ByteString -> a -> Trie a -> Trie a Source

Generic function to alter a trie by one element with a function to resolve conflicts (or non-conflicts).

insert :: ByteString -> a -> Trie a -> Trie a Source

Insert a new key. If the key is already present, overrides the old value

adjust :: (a -> a) -> ByteString -> Trie a -> Trie a Source

Apply a function to the value at a key.

delete :: ByteString -> Trie a -> Trie a Source

Remove the value stored at a key.

Combining tries

mergeBy :: (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a Source

Combine two tries, using a function to resolve collisions. This can only define the space of functions between union and symmetric difference but, with those two, all set operations can be defined (albeit inefficiently).

unionL :: Trie a -> Trie a -> Trie a Source

Combine two tries, resolving conflicts by choosing the value from the left trie.

unionR :: Trie a -> Trie a -> Trie a Source

Combine two tries, resolving conflicts by choosing the value from the right trie.

Mapping functions

mapBy :: (ByteString -> a -> Maybe b) -> Trie a -> Trie b Source

Generic version of fmap. This function is notably more expensive than fmap or filterMap because we have to reconstruct the keys.

filterMap :: (a -> Maybe b) -> Trie a -> Trie b Source

Apply a function to all values, potentially removing them.