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 a`n`

, and values of
type `a`

.

An

is a statically balanced tree, whose non-nil values
have type `AVLTree`

a`a`

.

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.