Data.VCache.Trie.Type

The underlying structure for a Trie.

This is an internal module, but is exposed for now because I'm not sure how to best generically target features such as structural diffs. And we might eventually benefit from zippers, etc. After experimenting and learning, I ask you to push the best generic code into the vcache-trie package (i.e. send a pull request).

Documentation

data Trie a

A trie data structure with bytestring keys, above VCache.

A trie supports keys of arbitrary size, though very large keys may cause performance degradation. Values are directly serialized into nodes, so very large values should use indirection.

Constructors

Trie

Fields

trie_root :: !(Child a)

trie_space :: !VSpace

Instances

Eq (Trie a)

Show (Trie a)

VCacheable a => VCacheable (Trie a)

Typeable (* -> *) Trie

data Node a

A node should either accept a value or branch into at least two children.

Constructors

Node

Fields

trie_branch :: !(Children a)

trie_prefix :: !ByteString

trie_accept :: !(Maybe a)

Instances

Eq a => Eq (Node a)

VCacheable a => VCacheable (Node a)

Typeable (* -> *) Node

type Children a = Array Word8 (Child a)

type Child a = Maybe (VRef (Node a))

unsafeTrieAddr :: Trie a -> Word64

Obtain unique address for Trie value. As with VRef addresses, this should be stable while the Trie is reachable, but may change if the value is GC'd and later reconstructed at a new address. Exposed for memoization and similar purposes.