-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Trees whose branches are resistant to change
--   
@package stable-tree
@version 0.7.0


-- | Tools for working with StableTree keys.
module Data.StableTree.Key

-- | A wrapper for keys; this has an ephemeral <tt>t</tt> that will be
--   either <a>Terminal</a> or <a>Nonterminal</a> depending on the result
--   of <tt>byte k</tt>.
data Key t k

-- | A sum type to contain either a <a>Terminal</a> or a <a>Nonterminal</a>
--   <a>Key</a>
data SomeKey k
SomeKey_T :: (Key Terminal k) -> SomeKey k
SomeKey_N :: (Key Nonterminal k) -> SomeKey k

-- | Type class for <tt>StableTree</tt> keys
class StableKey k
hash :: StableKey k => k -> Word8

-- | Used to indicate that a <a>Key</a> is terminal
data Terminal

-- | Used to indicate that a <a>Key</a> is not terminal
data Nonterminal

-- | Do the magic of wrapping up a key into a <a>SomeKey</a>
wrap :: StableKey k => k -> SomeKey k

-- | Extract the original key from a wrapped one
unwrap :: SomeKey k -> k

-- | Calculate a single-byte hash for a <a>ByteString</a>
hashBs :: ByteString -> Word8
instance Eq k => Eq (Key t k)
instance Ord k => Ord (Key t k)
instance Show k => Show (Key t k)
instance Eq k => Eq (SomeKey k)
instance Ord k => Ord (SomeKey k)
instance Show k => Show (SomeKey k)
instance (Serialize a, Serialize b, Serialize c, Serialize d, Serialize e, Serialize f, Serialize g, Serialize h, Serialize i, Serialize j) => StableKey (a, b, c, d, e, f, g, h, i, j)
instance (Serialize a, Serialize b, Serialize c, Serialize d, Serialize e, Serialize f, Serialize g, Serialize h, Serialize i) => StableKey (a, b, c, d, e, f, g, h, i)
instance (Serialize a, Serialize b, Serialize c, Serialize d, Serialize e, Serialize f, Serialize g, Serialize h) => StableKey (a, b, c, d, e, f, g, h)
instance (Serialize a, Serialize b, Serialize c, Serialize d, Serialize e, Serialize f, Serialize g) => StableKey (a, b, c, d, e, f, g)
instance (Serialize a, Serialize b, Serialize c, Serialize d, Serialize e, Serialize f) => StableKey (a, b, c, d, e, f)
instance (Serialize a, Serialize b, Serialize c, Serialize d, Serialize e) => StableKey (a, b, c, d, e)
instance (Serialize a, Serialize b, Serialize c, Serialize d) => StableKey (a, b, c, d)
instance (Serialize a, Serialize b, Serialize c) => StableKey (a, b, c)
instance (Ord k, Serialize k, Serialize e) => StableKey (Map k e)
instance (Serialize a, Serialize b) => StableKey (a, b)
instance (Serialize a, Serialize b) => StableKey (Either a b)
instance Serialize e => StableKey (Seq e)
instance Serialize e => StableKey (Tree e)
instance (Ord a, Serialize a) => StableKey (Set a)
instance Serialize e => StableKey (IntMap e)
instance Serialize a => StableKey (Maybe a)
instance (Serialize a, Integral a) => StableKey (Ratio a)
instance Serialize a => StableKey [a]
instance StableKey IntSet
instance StableKey ByteString
instance StableKey ByteString
instance StableKey Word64
instance StableKey Word32
instance StableKey Word16
instance StableKey Word8
instance StableKey Word
instance StableKey Ordering
instance StableKey Integer
instance StableKey Int64
instance StableKey Int32
instance StableKey Int16
instance StableKey Int8
instance StableKey Int
instance StableKey Float
instance StableKey Double
instance StableKey Char
instance StableKey Bool


-- | Definitions of primitive types used in different modules of
--   stable-tree
module Data.StableTree.Types

-- | Alias to indicate how deep a branch in a tree is. Bottoms have depth 0
type Depth = Int

-- | Alias that indicates the total number of values underneath a tree
type ValueCount = Int

-- | <tt>StableTree</tt> is the user-visible type that wraps the actual
--   <a>Tree</a> implementation. All the public functions operate on this
--   type.
data StableTree k v
StableTree_I :: (Tree d Incomplete k v) -> StableTree k v
StableTree_C :: (Tree d Complete k v) -> StableTree k v

-- | Used to indicate that a <a>Tree</a> is not complete
data Incomplete

-- | Used to indicate that a <a>Tree</a> is complete
data Complete

-- | Empty type to indicate a Tree with Zero depth (a bottom node)
data Z

-- | Empty type to indicate a Tree with some known height (a branch)
data S a

-- | The actual B-Tree variant. StableTree is built on one main idea: every
--   <a>Key</a> is either <a>Terminal</a> or <a>Nonterminal</a>, and every
--   <a>Tree</a> is <a>Complete</a> or <a>Incomplete</a>. A complete
--   <a>Tree</a> is one whose final element's Key is terminal, and the rest
--   of the Keys are not (exept for two freebies at the beginning to
--   guarantee convergence). A complete tree always has complete children.
--   
--   If we don't have enough data to generate a complete tree (i.e. we ran
--   out of elements before hitting a terminal key), then an
--   <a>Incomplete</a> tree is generated. Incomplete trees are always
--   contained by other incomplete trees, and a tree built from only the
--   complete children of an incomplete tree would never itself be
--   complete.
--   
--   It is easiest to understand how this structure promotes stability by
--   looking at how trees typically work. The easiest tree to understand is
--   a simple, well balanced, binary tree. In that case, we would have a
--   structure like this:
--   
--   <pre>
--         |D|
--     |B|     |F|
--   |A| |C| |E| |G|
--   </pre>
--   
--   Now, suppose that we want to delete the data stored in <tt>|A|</tt>.
--   Then, we'll get a new structure that shares nothing in common with the
--   original one:
--   
--   <pre>
--         |E|
--     |C|     |G|
--   |B| |D| |F|
--   </pre>
--   
--   The entire tree had to be re-written. This structure is clearly
--   unstable under mutation. Making the tree wider doesn't help much if
--   the tree's size is changing. Simple updates to existing keys are
--   handled well by branches with many children, but deleting from or
--   adding to the beginning of the tree will always cause every single
--   branch to change, which is what this structure is trying to avoid.
--   
--   Instead, the stable tree branches have variable child counts. A branch
--   is considered full when its highest key is "terminal", which is
--   determined by hashing the key and looking at some bits of the hash.
--   I've found that a target branch size of 16 children works fairly well,
--   so we check to see if the hash has its least-significant four bits
--   set; if that's the case, the key is terminal. A branch gets two free
--   children (meaning it doesn't care about whether the keys are terminal
--   or not), and then a run of nonterminal keys, and a final, terminal
--   key. Under this scheme, inserting a new entry into a branch will
--   probably mean inserting a nonterminal key, and it will probably be
--   inserted into the run of nonterminal children. If that's the case, no
--   neighbors will be affected, and only the parents will have to change
--   to point to the new branch. Stability is achieved!
data Tree d c k v
Bottom :: (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> (Key Terminal k, v) -> Tree Z Complete k v
IBottom0 :: Maybe (SomeKey k, v) -> Tree Z Incomplete k v
IBottom1 :: (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> Tree Z Incomplete k v
Branch :: Depth -> (SomeKey k, ValueCount, Tree d Complete k v) -> (SomeKey k, ValueCount, Tree d Complete k v) -> Map (Key Nonterminal k) (ValueCount, Tree d Complete k v) -> (Key Terminal k, ValueCount, Tree d Complete k v) -> Tree (S d) Complete k v
IBranch0 :: Depth -> (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v
IBranch1 :: Depth -> (SomeKey k, ValueCount, Tree d Complete k v) -> Maybe (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v
IBranch2 :: Depth -> (SomeKey k, ValueCount, Tree d Complete k v) -> (SomeKey k, ValueCount, Tree d Complete k v) -> Map (Key Nonterminal k) (ValueCount, Tree d Complete k v) -> Maybe (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v

-- | Get the depth (height?) of a <a>Tree</a> or <a>StableTree</a>
getDepth :: TreeNode n => n k v -> Depth

-- | Get the total number of key/value pairs stored under this <a>Tree</a>
--   or <a>StableTree</a>
getValueCount :: TreeNode n => n k v -> ValueCount
instance (Ord k, Show k, Show v) => Show (Tree d c k v)
instance (Ord k, Show k, Show v) => Show (StableTree k v)
instance (Ord k, StableKey k) => Functor (StableTree k)
instance (Ord k, StableKey k) => Functor (Tree d c k)
instance (Eq k, Eq v) => Eq (StableTree k v)
instance (Eq k, Eq v) => Eq (Tree d c k v)
instance TreeNode StableTree
instance TreeNode (Tree d c)


-- | Various functions for getting interested data about <a>StableTree</a>s
--   and <a>Tree</a>s.
module Data.StableTree.Properties

-- | Get the key of the first entry in this branch. If the branch is empty,
--   returns Nothing.
getKey :: Tree d c k v -> Maybe k

-- | Get the key of the first entry in this complete branch. This function
--   is total.
completeKey :: Tree d Complete k v -> k

-- | Get the total number of k/v pairs in the tree
size :: StableTree k v -> ValueCount

-- | Get the value associated with the given key, or Nothing if there is no
--   value for the key.
lookup :: Ord k => k -> StableTree k v -> Maybe v

-- | Get the keys in the map
keys :: Ord k => StableTree k v -> [k]

-- | Get the elements stored in the map
elems :: Ord k => StableTree k v -> [v]

-- | Get the key/value pairs in the map
assocs :: Ord k => StableTree k v -> [(k, v)]

-- | Convert an entire Tree into a k/v map.
treeContents :: Ord k => Tree d c k v -> Map k v

-- | Convert a <a>StableTree</a> into a normal key/value Map
toMap :: Ord k => StableTree k v -> Map k v

-- | Either get the StableTree "children" of a <a>StableTree</a>, or get
--   the key/value map if the tree is already a bottom.
stableChildren :: Ord k => StableTree k v -> Either (Map k v) (Map k (ValueCount, StableTree k v))

-- | Non-recursive function to simply get the immediate children of the
--   given branch. This will either give the key<i>value map of a Bottom,
--   or the key</i>tree map of a non-bottom branch.
bottomChildren :: Ord k => Tree Z c k v -> Map k v

-- | Get the <a>Tree</a>s stored under the given Tree. The Tree type
--   prevents this function from being called on bottom Trees.
branchChildren :: Ord k => Tree (S d) c k v -> (Map k (ValueCount, Tree d Complete k v), Maybe (k, ValueCount, Tree d Incomplete k v))

-- | Choose the child node most likely to hold the given key. If this
--   returns Left, then the chosen node is the Incomplete node. In the
--   Right case, the sole Complete node is the best node. The Complete
--   nodes in the first slot of the quad are the nodes that came before the
--   chosen node, while the nodes in the third slot are the nodes that came
--   after. This is useful for changing a specific node, and then patching
--   things back together with the <a>merge</a> function.
selectNode :: Ord k => k -> Tree (S d) c k v -> Either ([Tree d Complete k v], Tree d Incomplete k v) ([Tree d Complete k v], Tree d Complete k v, [Tree d Complete k v], Maybe (Tree d Incomplete k v))


-- | Functions for iterating over a StableTree. Currently just folds, but
--   convenience functions for maps will probably be added at some point.
module Data.StableTree.Walk

-- | Monadic fold over a StableTree in the style of <a>foldM</a>.
foldM :: (Monad m, Ord k) => (a -> k -> v -> m a) -> a -> StableTree k v -> m a

-- | Right fold over a StableTree. Similar to <a>foldrWithKey</a>.
foldr :: Ord k => (k -> v -> a -> a) -> a -> StableTree k v -> a

-- | Left fold over a StableTree. Similar to <a>foldlWithKey</a>.
foldl :: Ord k => (a -> k -> v -> a) -> a -> StableTree k v -> a


-- | This is the core implementation of the stable tree. The primary
--   functions exported by this module are <a>nextBottom</a> and
--   <a>nextBranch</a>, which gather values or lower-level <a>Tree</a>s
--   into <a>Tree</a>s of the next level.
--   
--   This module is fairly esoteric. <a>Data.StableTree</a> is probably
--   what you actually want to be using.
module Data.StableTree.Build

-- | Convert a simple key/value map into a StableTree
fromMap :: (Ord k, StableKey k) => Map k v -> StableTree k v

-- | Create a new empty StableTree
empty :: (Ord k, StableKey k) => StableTree k v

-- | Smash two StableTree instances into a single one
append :: (Ord k, StableKey k) => StableTree k v -> StableTree k v -> StableTree k v

-- | Smash a whole bunch of StableTree instances into a single one
concat :: (Ord k, StableKey k) => [StableTree k v] -> StableTree k v

-- | Helper function to convert a complete bunch of Tree instances (of the
--   same depth) into a single StableTree.
consume :: (Ord k, StableKey k) => [Tree d Complete k v] -> Maybe (Tree d Incomplete k v) -> StableTree k v

-- | Convert a single key/value map into Tree bottom (zero-depth)
--   instances. The resulting list of Tree instances will never be
--   overlapping, and will be sorted such that each Tree's highest key is
--   lower than the next Tree's lowest key. This is not guaranteed by types
--   because i don't think that can be done in Haskell.
consumeMap :: (Ord k, StableKey k) => Map k v -> ([Tree Z Complete k v], Maybe (Tree Z Incomplete k v))

-- | Given a mapping from each Tree's first key to that Tree, (and a final
--   incomplete Tree if desired), this will build the next level of Tree
--   instances. As with consumeMap, the resulting list of Tree instances
--   will be non-overlapping and ordered such that each Tree's highest key
--   is smaller than the next Tree's lowest key.
consumeBranches :: (Ord k, StableKey k) => Map k (Tree d Complete k v) -> Maybe (k, Tree d Incomplete k v) -> ([Tree (S d) Complete k v], Maybe (Tree (S d) Incomplete k v))

-- | Given a simple listing of complete Trees and maybe an incomplete one,
--   this will build the next level ot Trees. This just builds a map and
--   calls the previous <a>consumeBranches</a> function, but it's a
--   convenient function to have.
consumeBranches' :: (Ord k, StableKey k) => [Tree d Complete k v] -> Maybe (Tree d Incomplete k v) -> ([Tree (S d) Complete k v], Maybe (Tree (S d) Incomplete k v))

-- | Wrap up some of a k/v map into a <a>Tree</a>. A <a>Right</a> result
--   gives a complete tree and the map updated to not have the key/values
--   that went into that tree. A <a>Left</a> result gives an incomplete
--   tree that contains everything that the given map contained.
nextBottom :: (Ord k, StableKey k) => Map k v -> Either (Tree Z Incomplete k v) (Tree Z Complete k v, Map k v)

-- | Result of the <a>nextBranch</a> function; values are described below.
data NextBranch d k v
Empty :: NextBranch d k v
Final :: (Tree (S d) Incomplete k v) -> NextBranch d k v
More :: (Tree (S d) Complete k v) -> (Map k (Tree d Complete k v)) -> NextBranch d k v

-- | Generate a parent for a k/Tree map. An <a>Empty</a> result means that
--   the function was called with an empty Map and <a>Nothing</a> for an
--   incomplete. A <a>Final</a> result means that an incomplete Tree was
--   build and there is no more work to be done. A <a>More</a> result means
--   that a complete Tree was built, and there is (possibly) more work to
--   do.
nextBranch :: (Ord k, StableKey k) => Map k (Tree d Complete k v) -> Maybe (k, Tree d Incomplete k v) -> NextBranch d k v

-- | Tree mutation functions (insert, delete) will generally wind up with a
--   bunch of Trees that come before the key that was to be changed, and
--   then the result of updating the relevant Tree, and then a bunch of
--   Trees (and maybe an incomplete Tree) that come after it. Merge can
--   splice this result back into a correctly ordered, non-overlapping list
--   of complete Trees and maybe a final incomplete one.
merge :: (Ord k, StableKey k) => [Tree d Complete k v] -> Maybe (Tree d Incomplete k v) -> [Tree d Complete k v] -> Maybe (Tree d Incomplete k v) -> ([Tree d Complete k v], Maybe (Tree d Incomplete k v))


-- | Functions for "updating" StableTrees, in the functional sense. This
--   covers insertion, deletion, etc.
module Data.StableTree.Mutate

-- | Insert a key/value into a <a>StableTree</a>. If the key exists, its
--   existing value is overwritten.
insert :: (Ord k, StableKey k) => k -> v -> StableTree k v -> StableTree k v

-- | Remove a key from the <a>StableTree</a>. If the key is not found, the
--   tree is returned unchanged.
delete :: (Ord k, StableKey k) => k -> StableTree k v -> StableTree k v


-- | Functions for converting between <a>Tree</a> and <a>Fragment</a> types
module Data.StableTree.Conversion

-- | A <a>Fragment</a> 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. See <a>toFragments</a> and
--   <a>fromFragments</a> for functions to convert between Fragments and
--   Trees. see <a>store</a> and <a>load</a> for functions related to
--   storing and retrieving Fragments.
data Fragment k v
FragmentBranch :: ObjectID -> Depth -> Map k (ValueCount, ObjectID) -> Fragment k v
fragmentObjectID :: Fragment k v -> ObjectID
fragmentDepth :: Fragment k v -> Depth
fragmentChildren :: Fragment k v -> Map k (ValueCount, ObjectID)
FragmentBottom :: ObjectID -> Map k v -> Fragment k v
fragmentObjectID :: Fragment k v -> ObjectID
fragmentMap :: Fragment k v -> Map k v

-- | Convert a <a>StableTree</a> <a>Tree</a> into a list of storable
--   <a>Fragment</a>s. The resulting list is guaranteed to be in an order
--   where each <a>Fragment</a> will be seen after all its children.
toFragments :: (Ord k, Serialize k, StableKey k, Serialize v) => StableTree k v -> [Fragment k v]

-- | Recover a <a>Tree</a> from a single <a>Fragment</a> and a map of the
--   fragments as returned from <a>toFragments</a>. If the fragment set was
--   already stored, it is the caller's responsibility to load all the
--   child fragments into a map (probably involving finding children using
--   the fragmentChildren field of the Fragment type).
fromFragments :: (Ord k, Serialize k, StableKey k, Serialize v) => Map ObjectID (Fragment k v) -> Fragment k v -> Either Text (StableTree k v)

-- | Directly convert a bunch of <a>Fragment</a>s and a root fragment into
--   a <a>Map</a> instance. Mostly useful for testing the correctness of
--   the <a>fromFragments</a> function.
fragsToMap :: Ord k => Map ObjectID (Fragment k v) -> Fragment k v -> Either Text (Map k v)
instance (Eq k, Eq v) => Eq (Fragment k v)
instance (Ord k, Ord v) => Ord (Fragment k v)
instance (Show k, Show v) => Show (Fragment k v)
instance (Ord k, Serialize k, Serialize v) => Serialize (Fragment k v)


-- | Logic for dealing with the actual persistence of Stable Trees. The key
--   exports here are <a>Error</a>, <a>load</a>, and <a>store</a>. A user
--   needs to make an appropriate Error type to report storage errors, and
--   then the <a>load</a> and <a>store</a> functions can just do their
--   thing. If necessary, a user can also implement <a>Serialize</a> for
--   custom data types.
module Data.StableTree.Persist

-- | Things go wrong with end-user storage, but things can also go wrong
--   with reconstructing tree values. Implement <a>stableTreeError</a> to
--   allow <a>load</a> and <a>store</a> to report their own errors.
class Error e
stableTreeError :: Error e => Text -> e

-- | A <a>Fragment</a> 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. See <a>toFragments</a> and
--   <a>fromFragments</a> for functions to convert between Fragments and
--   Trees. see <a>store</a> and <a>load</a> for functions related to
--   storing and retrieving Fragments.
data Fragment k v
FragmentBranch :: ObjectID -> Depth -> Map k (ValueCount, ObjectID) -> Fragment k v
fragmentObjectID :: Fragment k v -> ObjectID
fragmentDepth :: Fragment k v -> Depth
fragmentChildren :: Fragment k v -> Map k (ValueCount, ObjectID)
FragmentBottom :: ObjectID -> Map k v -> Fragment k v
fragmentObjectID :: Fragment k v -> ObjectID
fragmentMap :: Fragment k v -> Map k v

-- | 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 (<a>FragmentBranch</a>
--   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, Serialize k, StableKey k, Serialize v) => (a -> ObjectID -> Fragment k v -> m (Either e a)) -> a -> StableTree k v -> m (Either e a)

-- | Alternate store function that acts more like a map than a fold. See
--   <a>store</a> for details.
store' :: (Monad m, Error e, Ord k, Serialize k, StableKey k, Serialize v) => (ObjectID -> Fragment k v -> m (Maybe e)) -> StableTree k v -> m (Either e ObjectID)

-- | Reverse of <a>store</a>. As with <a>store</a>, this acts like a fold,
--   but converts an <a>ObjectID</a> into a tree, rather than storing a
--   tree. This will always build the tree from the top down.
load :: (Monad m, Error e, Ord k, Serialize k, StableKey k, Serialize v) => (a -> ObjectID -> m (Either e (a, Fragment k v))) -> a -> ObjectID -> m (Either e (a, StableTree k v))

-- | Version of <a>load</a> that acts like a map rather than a fold.
load' :: (Monad m, Error e, Ord k, Serialize k, StableKey k, Serialize v) => (ObjectID -> m (Either e (Fragment k v))) -> ObjectID -> m (Either e (StableTree k v))


-- | A B-Tree variation 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 lowest branch and
--   its immediate ancestor chain being modified. Put another way, trees
--   with similar contents will also share a majority of their internal
--   branches.
--   
--   This module exports the public interface for StableTree. It largely
--   mimics the Data.Map interface, so it should be fairly familiar to
--   Haskell users.
module Data.StableTree

-- | <tt>StableTree</tt> is the user-visible type that wraps the actual
--   <a>Tree</a> implementation. All the public functions operate on this
--   type.
data StableTree k v

-- | Convert a simple key/value map into a StableTree
fromMap :: (Ord k, StableKey k) => Map k v -> StableTree k v

-- | Create a new empty StableTree
empty :: (Ord k, StableKey k) => StableTree k v

-- | Insert a key/value into a <a>StableTree</a>. If the key exists, its
--   existing value is overwritten.
insert :: (Ord k, StableKey k) => k -> v -> StableTree k v -> StableTree k v

-- | Remove a key from the <a>StableTree</a>. If the key is not found, the
--   tree is returned unchanged.
delete :: (Ord k, StableKey k) => k -> StableTree k v -> StableTree k v

-- | Get the total number of k/v pairs in the tree
size :: StableTree k v -> ValueCount

-- | Get the value associated with the given key, or Nothing if there is no
--   value for the key.
lookup :: Ord k => k -> StableTree k v -> Maybe v

-- | Get the keys in the map
keys :: Ord k => StableTree k v -> [k]

-- | Get the elements stored in the map
elems :: Ord k => StableTree k v -> [v]

-- | Get the key/value pairs in the map
assocs :: Ord k => StableTree k v -> [(k, v)]

-- | Smash two StableTree instances into a single one
append :: (Ord k, StableKey k) => StableTree k v -> StableTree k v -> StableTree k v

-- | Smash a whole bunch of StableTree instances into a single one
concat :: (Ord k, StableKey k) => [StableTree k v] -> StableTree k v

-- | Convert a <a>StableTree</a> into a normal key/value Map
toMap :: Ord k => StableTree k v -> Map k v