| Copyright | Jeremy Groven |
|---|---|
| License | BSD3 |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.StableTree
Description
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.
- data StableTree k v
- fromMap :: (Ord k, StableKey k) => Map k v -> StableTree k v
- empty :: (Ord k, StableKey k) => StableTree k v
- insert :: (Ord k, StableKey k) => k -> v -> StableTree k v -> StableTree k v
- delete :: (Ord k, StableKey k) => k -> StableTree k v -> StableTree k v
- size :: StableTree k v -> ValueCount
- lookup :: Ord k => k -> StableTree k v -> Maybe v
- keys :: Ord k => StableTree k v -> [k]
- elems :: Ord k => StableTree k v -> [v]
- assocs :: Ord k => StableTree k v -> [(k, v)]
- append :: (Ord k, StableKey k) => StableTree k v -> StableTree k v -> StableTree k v
- concat :: (Ord k, StableKey k) => [StableTree k v] -> StableTree k v
- toMap :: Ord k => StableTree k v -> Map k v
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.
Instances
| (Ord k, StableKey k) => Functor (StableTree k) | |
| (Eq k, Eq v) => Eq (StableTree k v) | |
| (Ord k, Show k, Show v) => Show (StableTree k v) |
fromMap :: (Ord k, StableKey k) => Map k v -> StableTree k v Source
Convert a simple key/value map into a StableTree
empty :: (Ord k, StableKey k) => StableTree k v Source
Create a new empty StableTree
insert :: (Ord k, StableKey k) => k -> v -> StableTree k v -> StableTree k v Source
Insert a key/value into a StableTree. If the key exists, its existing
value is overwritten.
delete :: (Ord k, StableKey k) => k -> StableTree k v -> StableTree k v Source
Remove a key from the StableTree. If the key is not found, the tree is
returned unchanged.
size :: StableTree k v -> ValueCount Source
Get the total number of k/v pairs in the tree
lookup :: Ord k => k -> StableTree k v -> Maybe v Source
Get the value associated with the given key, or Nothing if there is no value for the key.
keys :: Ord k => StableTree k v -> [k] Source
Get the keys in the map
elems :: Ord k => StableTree k v -> [v] Source
Get the elements stored in the map
assocs :: Ord k => StableTree k v -> [(k, v)] Source
Get the key/value pairs in the map
append :: (Ord k, StableKey k) => StableTree k v -> StableTree k v -> StableTree k v Source
Smash two StableTree instances into a single one
concat :: (Ord k, StableKey k) => [StableTree k v] -> StableTree k v Source
Smash a whole bunch of StableTree instances into a single one
toMap :: Ord k => StableTree k v -> Map k v Source
Convert a StableTree into a normal key/value Map