vcache-trie-0.1.1: patricia tries modeled above VCache

Safe HaskellNone
LanguageHaskell2010

Data.VCache.Trie.Type

Description

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).

Synopsis

Documentation

data Trie a Source

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 Source

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

Constructors

Node 

Instances

Eq a => Eq (Node a) 
VCacheable a => VCacheable (Node a) 
Typeable (* -> *) Node 

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

unsafeTrieAddr :: Trie a -> Word64 Source

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.