Safe Haskell | None |
---|---|
Language | Haskell2010 |
Synopsis
- class Tree (t :: * -> * -> * -> *) where
- type TreeGen t :: * -> *
- newTreeGen :: PrimMonad m => Proxy t -> m (TreeGen t (PrimState m))
- singleton :: (PrimMonad m, Monoid v) => TreeGen t (PrimState m) -> a -> v -> m (t (PrimState m) a v)
- append :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v)
- cons :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v)
- snoc :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v)
- split :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (Maybe (t (PrimState m) a v), Maybe (t (PrimState m) a v))
- connected :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m Bool
- root :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v)
- readRoot :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v)
- label :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m a
- aggregate :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m v
- toList :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m [a]
- concat :: forall t m a v. (Tree t, PrimMonad m, Monoid v) => NonEmpty (t (PrimState m) a v) -> m (t (PrimState m) a v)
- class Tree t => TestTree t where
- print :: Show a => t (PrimState IO) a v -> IO ()
- assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m ()
- assertSingleton :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m ()
- assertRoot :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m ()
Documentation
class Tree (t :: * -> * -> * -> *) where Source #
The chosen represenation of the tree has a big impact on the performance of the algorithms. This typeclass allows us to swap them out more easily.
newTreeGen :: PrimMonad m => Proxy t -> m (TreeGen t (PrimState m)) Source #
Create a tree gen itself
singleton :: (PrimMonad m, Monoid v) => TreeGen t (PrimState m) -> a -> v -> m (t (PrimState m) a v) Source #
Create a tree with a single element.
append :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v) Source #
Join two trees together.
cons :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v) Source #
Prepend a singleton tree
snoc :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m (t (PrimState m) a v) Source #
Append a singleton tree
split :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (Maybe (t (PrimState m) a v), Maybe (t (PrimState m) a v)) Source #
Split a tree, turning the argument into a singleton and returning the left and right halves of the tree.
connected :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> t (PrimState m) a v -> m Bool Source #
Check if two nodes belong to the same tree
root :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v) Source #
Find the root of a tree
readRoot :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m (t (PrimState m) a v) Source #
Read the root of a tree. This is not allowed to modify the tree (e.g., no splaying allowed).
label :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m a Source #
Read the label from a tree
aggregate :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m v Source #
Read the aggregate of a tree
toList :: (PrimMonad m, Monoid v) => t (PrimState m) a v -> m [a] Source #
Convert a tree to a list
Instances
concat :: forall t m a v. (Tree t, PrimMonad m, Monoid v) => NonEmpty (t (PrimState m) a v) -> m (t (PrimState m) a v) Source #
class Tree t => TestTree t where Source #
These methods can be used for testing and debugging.
print :: Show a => t (PrimState IO) a v -> IO () Source #
assertInvariants :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m () Source #
assertSingleton :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m () Source #
assertRoot :: (PrimMonad m, Monoid v, Eq v, Show v) => t (PrimState m) a v -> m () Source #