Safe Haskell | Safe-Inferred |
---|
- data Nat
- data AVLNode where
- data AVLTree a = forall n . T (AVLNode n a) Integer
- foldNode :: (b -> b -> a -> b) -> b -> AVLNode n a -> b
- fmapNode :: (a -> b) -> AVLNode n a -> AVLNode n b
- traverseNode :: Applicative f => (a -> f b) -> AVLNode n a -> f (AVLNode n b)
- data Context where
- BC :: Bool -> a -> AVLNode n a -> Context (Succ n) a -> Context n a
- LRC :: a -> AVLNode (Succ n) a -> Context (Succ (Succ n)) a -> Context n a
- LLC :: a -> AVLNode n a -> Context (Succ (Succ n)) a -> Context (Succ n) a
- RLC :: a -> AVLNode (Succ n) a -> Context (Succ (Succ n)) a -> Context n a
- RRC :: a -> AVLNode n a -> Context (Succ (Succ n)) a -> Context (Succ n) a
- Root :: Integer -> Context n a
- data Zipper a = forall n . Zipper (AVLNode n a) (Context n a)
- value :: Zipper a -> a
- unZip :: AVLTree a -> Zipper a
- zipUp :: (Integer -> Integer) -> Zipper a -> AVLTree a
- up :: Zipper a -> Zipper a
- canGoUp :: Zipper a -> Bool
- left :: Zipper a -> Zipper a
- canGoLeft :: Zipper a -> Bool
- right :: Zipper a -> Zipper a
- canGoRight :: Zipper a -> Bool
- isLeft :: Zipper a -> Bool
- isRight :: Zipper a -> Bool
- isLeaf :: Zipper a -> Bool
- zipTo :: Ord a => a -> Zipper a -> Zipper a
- insertUnbalancedAt :: AVLNode (Succ n) a -> Context n a -> AVLTree a
- zipToSuccessor :: Zipper a -> Maybe (Zipper a)
- zipToPredecessor :: Zipper a -> Maybe (Zipper a)
- zipToSmallest :: Zipper a -> Zipper a
- zipToGreatest :: Zipper a -> Zipper a
- zipToFirstLeftChild :: Zipper a -> Maybe (Zipper a)
- zipToFirstRightChild :: Zipper a -> Maybe (Zipper a)
- fixContext :: forall a n. Eq a => a -> a -> Context n a -> Context n a
- deleteBST :: Eq a => Zipper a -> AVLTree a
- rebalance :: AVLNode n a -> Context (Succ n) a -> AVLTree a
Documentation
A natural number datatype, hoisted to a Kind using DataKinds.
An
is a node whose subtree has height AVLNode
n an
, and values of
type a
.
An
is a statically balanced tree, whose non-nil values
have type AVLTree
aa
.
traverseNode :: Applicative f => (a -> f b) -> AVLNode n a -> f (AVLNode n b)Source
The context for an 'AVLTree'\'s Zipper
.
The idea is that it represents an entire AVLTree
, save for a hole in it.
A Context
n
a
means an entire AVLTree
a
, with a hole of height n.
Its use is that, in a Zipper
, we have a simple way to move around in the
tree, starting at that hole.
See this paper by Conor McBride for more information.
BC :: Bool -> a -> AVLNode n a -> Context (Succ n) a -> Context n a | |
LRC :: a -> AVLNode (Succ n) a -> Context (Succ (Succ n)) a -> Context n a | |
LLC :: a -> AVLNode n a -> Context (Succ (Succ n)) a -> Context (Succ n) a | |
RLC :: a -> AVLNode (Succ n) a -> Context (Succ (Succ n)) a -> Context n a | |
RRC :: a -> AVLNode n a -> Context (Succ (Succ n)) a -> Context (Succ n) a | |
Root :: Integer -> Context n a |
A Zipper
is a useful construct for functional datastructure traversals.
For us, it can be thought of as a pointer to a subtree in an AVLTree
.
See Functional Pearls: Zippers for more information.
zipUp :: (Integer -> Integer) -> Zipper a -> AVLTree aSource
Given a function that manipulates the tree size (number of nodes), and a
Zipper
, constructs an AVLTree
with the new height, by zipping up to
the root of the tree pointed to by the Zipper
.
canGoRight :: Zipper a -> BoolSource
Returns whether we can navigate right.
isLeft :: Zipper a -> BoolSource
Returns whether the pointed to subtree is a left child of its parent.
isRight :: Zipper a -> BoolSource
Returns whether the pointed to subtree is a right child of its parent.
zipTo :: Ord a => a -> Zipper a -> Zipper aSource
Descends (never ascends) to a subtree whose root has a given value.
If no such subtree exists, points to a Nil
where the value would be found,
were it to exist.
insertUnbalancedAt :: AVLNode (Succ n) a -> Context n a -> AVLTree aSource
Insert an AVLNode
of height (n + 1) in a Context
with a hole of size n.
Since this cannot be done in the usual way, rotations are used to return
an AVLTree
that may nothave the same height as the 'Context'\'s tree did,
or have the same structure, but holds the same values, and has this enlarged
AVLNode
in it.
zipToSuccessor :: Zipper a -> Maybe (Zipper a)Source
zipToPredecessor :: Zipper a -> Maybe (Zipper a)Source
zipToSmallest :: Zipper a -> Zipper aSource
zipToGreatest :: Zipper a -> Zipper aSource
zipToFirstLeftChild :: Zipper a -> Maybe (Zipper a)Source
zipToFirstRightChild :: Zipper a -> Maybe (Zipper a)Source
fixContext :: forall a n. Eq a => a -> a -> Context n a -> Context n aSource
rebalance :: AVLNode n a -> Context (Succ n) a -> AVLTree aSource
Given an AVLNode
n
a
, and a Context
with a hole of size (n + 1)
,
returns an AVLTree
a
with the AVLNode
being placed in that Context
.
Since this cannot be done normally, it uses rotations to return an AVLTree
that has the same elements as the Context
and the AVLNode
together,
but may have a different structure than the tree the Context
represented.