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


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


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

-- | 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 :: Serialize k => k -> SomeKey k

-- | Extract the original key from a wrapped one
unwrap :: SomeKey k -> k
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)


-- | 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 :: ObjectID -> (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> (Key Terminal k, v) -> Tree Z Complete k v
IBottom0 :: ObjectID -> Maybe (SomeKey k, v) -> Tree Z Incomplete k v
IBottom1 :: ObjectID -> (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> Tree Z Incomplete k v
Branch :: ObjectID -> 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 :: ObjectID -> Depth -> (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v
IBranch1 :: ObjectID -> 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 :: ObjectID -> 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

-- | 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, and its serialize instance is
--   also used to calculate Tree ObjectIDs. 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 :: Depth -> Map k (ValueCount, ObjectID) -> Fragment k v
fragmentDepth :: Fragment k v -> Depth
fragmentChildren :: Fragment k v -> Map k (ValueCount, ObjectID)
FragmentBottom :: Map k v -> Fragment k v
fragmentMap :: Fragment k v -> Map k v

-- | Helper to create a <a>Bottom</a> instance with a calculated ObjectID
mkBottom :: (Ord k, Serialize k, Serialize v) => (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> (Key Terminal k, v) -> Tree Z Complete k v

-- | Helper to create an <a>IBottom0</a> instance with a calculated
--   ObjectID
mkIBottom0 :: (Ord k, Serialize k, Serialize v) => Maybe (SomeKey k, v) -> Tree Z Incomplete k v

-- | Helper to create an <a>IBottom1</a> instance with a calculated
--   ObjectID
mkIBottom1 :: (Ord k, Serialize k, Serialize v) => (SomeKey k, v) -> (SomeKey k, v) -> Map (Key Nonterminal k) v -> Tree Z Incomplete k v

-- | Helper to create a <a>Branch</a> instance with a calculated ObjectID
mkBranch :: (Ord k, Serialize k, Serialize v) => 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

-- | Helper to create an <a>IBranch0</a> instance with a calculated
--   ObjectID
mkIBranch0 :: (Ord k, Serialize k, Serialize v) => Depth -> (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v

-- | Helper to create an <a>IBranch1</a> instance with a calculated
--   ObjectID
mkIBranch1 :: (Ord k, Serialize k, Serialize v) => Depth -> (SomeKey k, ValueCount, Tree d Complete k v) -> Maybe (SomeKey k, ValueCount, Tree d Incomplete k v) -> Tree (S d) Incomplete k v

-- | Helper to create an <a>IBranch2</a> instance with a calculated
--   ObjectID
mkIBranch2 :: (Ord k, Serialize k, Serialize v) => 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 ObjectID of a <a>Tree</a> or <a>StableTree</a>
getObjectID :: TreeNode n => n k v -> ObjectID

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

-- | Do the (expensive) calculation of a <a>Tree</a> or <a>StableTree</a>;
--   generally used to do the initial ObjectID calculation when
--   constructing an instance
calcObjectID :: (TreeNode n, Ord k, Serialize k, Serialize v) => n k v -> ObjectID

-- | Recalculate the object's ObjectID and return the updated object;
--   pretty much a convenience function around <a>calcObjectID</a>
fixObjectID :: (TreeNode n, Ord k, Serialize k, Serialize v) => n k v -> n k v

-- | Get the <a>Fragment</a> representing this exact <a>Tree</a> node, used
--   for persistent storage
makeFragment :: (TreeNode n, Ord k) => n k v -> Fragment k v
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 (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)
instance Ord (StableTree k v)
instance Eq (StableTree k v)
instance 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, Serialize k, Serialize v) => Map k v -> StableTree k v

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

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

-- | Smash a whole bunch of StableTree instances into a single one
concat :: (Ord k, Serialize k, Serialize v) => [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, Serialize k, Serialize v) => [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, Serialize k, Serialize v) => 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, Serialize k, Serialize v) => 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, Serialize k, Serialize v) => [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, Serialize k, Serialize v) => 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, Serialize k, Serialize v) => 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, Serialize k, Serialize v) => [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))

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, Serialize k, Serialize v) => 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, Serialize k, Serialize v) => k -> StableTree k v -> StableTree k v

-- | Same as the <a>fmap</a> instance of <a>Functor</a>, but with the
--   restriction that the input and output of the mutation function must be
--   <a>Serialize</a>-able. Using the real instance would be really cool,
--   but we need that Serialize instance.
fmap :: (SerialFunctor f, Serialize a, Serialize b) => (a -> b) -> f a -> f b
instance (Ord k, Serialize k) => SerialFunctor (StableTree k)
instance (Ord k, Serialize k) => SerialFunctor (Tree d c k)


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

-- | 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 => StableTree k v -> [(ObjectID, 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, 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)


-- | 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, and its serialize instance is
--   also used to calculate Tree ObjectIDs. 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 :: Depth -> Map k (ValueCount, ObjectID) -> Fragment k v
fragmentDepth :: Fragment k v -> Depth
fragmentChildren :: Fragment k v -> Map k (ValueCount, ObjectID)
FragmentBottom :: Map k v -> Fragment k v
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) => (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) => (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, 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, 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, Serialize k, Serialize v) => Map k v -> StableTree k v

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

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

-- | Same as the <a>fmap</a> instance of <a>Functor</a>, but with the
--   restriction that the input and output of the mutation function must be
--   <a>Serialize</a>-able. Using the real instance would be really cool,
--   but we need that Serialize instance.
fmap :: (SerialFunctor f, Serialize a, Serialize b) => (a -> b) -> f a -> f b

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

-- | Smash a whole bunch of StableTree instances into a single one
concat :: (Ord k, Serialize k, Serialize v) => [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