Copyright	Jeremy Groven
License	BSD3
Safe Haskell	None
Language	Haskell2010

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.

Synopsis

Documentation

data StableTree k v Source

StableTree is the user-visible 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)

fromMap :: (Ord k, Serialize k, Serialize v) => Map k v -> StableTree k v Source

Convert a Map into a StableTree.

toMap :: Ord k => StableTree k v -> Map k v Source

Convert a StableTree back into a Map

class Error e where Source

Things go wrong with end-user storage, but things can also go wrong with reconstructing tree values. Implement stableTreeError to allow load and store to report their own errors.

Methods

stableTreeError :: Text -> e Source

load :: (Monad m, Error e, Ord k, Serialize k, Serialize v) => (a -> ObjectID -> m (Either e (a, Fragment k v))) -> a -> ObjectID -> m (Either e (a, StableTree k v)) Source

load' :: (Monad m, Error e, Ord k, Serialize k, Serialize v) => (ObjectID -> m (Either e (Fragment k v))) -> ObjectID -> m (Either e (StableTree k v)) Source

store :: (Monad m, Error e, Ord k) => (a -> ObjectID -> Fragment k v -> m (Either e a)) -> a -> StableTree k v -> m (Either e a) Source

Record the tree into storage. This works like a fold, where the function takes an accumulating state and each tree fragment to store, while returning either an error message (which will abort the loop immediately) or the next state for the accumulator.

Any fragment referring to other fragments (FragmentBranch fragments) will be given to the fold only after all their children have been given to the fold. Exact ordering beyond that is not guaranteed, but the current behaviour is post-order depth-first traversal.

store' :: (Monad m, Error e, Ord k) => (ObjectID -> Fragment k v -> m (Maybe e)) -> StableTree k v -> m (Either e ObjectID) Source

data Fragment k v Source

A Fragment is a user-visible part of a tree, i.e. a single node in the tree that can actually be manipulated by a user. This is useful when doing the work of persisting trees.

Constructors

FragmentBranch
Fields fragmentDepth :: Depth fragmentChildren :: Map k (ValueCount, ObjectID)
FragmentBottom
Fields fragmentMap :: Map k v

Instances

(Eq k, Eq v) => Eq (Fragment k v)
(Ord k, Ord v) => Ord (Fragment k v)
(Show k, Show v) => Show (Fragment k v)
(Ord k, Serialize k, Serialize v) => Serialize (Fragment k v)