| Safe Haskell | None |
|---|
Data.StableTree
Description
A Rose Tree designed for maximal stability under mutation. The StableTree structure is meant to be used in places where different versions of a key/value map are kept, such as in a versioning file system or a revision control system. As a tree's contents are mutated (inserted, updated, deleted), it will tend to keep the vast majority of its branches untouched, with generally just the immediate branch and its immediate ancestor chain being modified. Put another way, trees with similar contents will also share a majority of their branches.
This module exports the public interface for StableTree. Right now, that's just a translation to the standard Data.Map and back. There's nothing about StableTree that forbids direct manipulation, but I've been playing with various implementations of this for way too long, and I just want to start using the dang thing now.
- data StableTree k v
- = StableTree_I (Tree Incomplete k v)
- | StableTree_C (Tree Complete k v)
- class IsKey k where
- fromMap :: (Ord k, IsKey k) => Map k v -> StableTree k v
- toMap :: Ord k => StableTree k v -> Map k v
Documentation
data StableTree k v Source
StableTree is the opaque type that wraps the actual Tree
implementation. All the public functions operate on this type.
Constructors
| StableTree_I (Tree Incomplete k v) | |
| StableTree_C (Tree Complete k v) |
Instances
| (Ord k, Show k, Show v) => Show (StableTree k v) |
Type class for anything that we can use as a key. The goal here is to wrap up a function that can generate a high-entropy eight-bit hash. Speed is somewhat important here, but since we only actually look at four bits of the hash, it really shouldn't be a problem to quickly generate sufficiently random data.
Implementors probably want to use hashSerialize, hashBinary, or
hashByteString when writing their hash functions.
fromMap :: (Ord k, IsKey k) => Map k v -> StableTree k vSource
Convert a Map into a StableTree.
toMap :: Ord k => StableTree k v -> Map k vSource
Convert a StableTree back into a Map