type-indexed-queues-0.1.0.1: Queues with verified and unverified versions.

Data.BinaryTree

Description

A simple, generic binary tree and some operations. Used in some of the heaps.

Synopsis

Documentation

data Tree a Source #

A simple binary tree for use in some of the heaps.

Constructors

 Leaf Node a (Tree a) (Tree a)

Instances

foldTree :: b -> (a -> b -> b -> b) -> Tree a -> b Source #

Fold over a tree.

isHeap :: Ord a => Tree a -> Bool Source #

Check to see if this tree maintains the heap property.

unfoldTree :: (b -> Maybe (a, b, b)) -> b -> Tree a Source #

Unfold a tree from a seed.

replicateTree :: Int -> a -> Tree a Source #

replicateTree n a creates a tree of size n filled a.

>>> replicateTree 4 ()
Node () (Node () (Node () Leaf Leaf) Leaf) (Node () Leaf Leaf)

n >= 0 ==> length (replicateTree n x) == n

replicateA :: Applicative f => Int -> f a -> f (Tree a) Source #

replicateA n a replicates the action a n times.

treeFromList :: [a] -> Tree a Source #

Construct a tree from a list, putting each even-positioned element to the left.

zygoTree :: b1 -> (a -> b1 -> b1 -> b1) -> b -> (a -> b1 -> b -> b1 -> b -> b) -> Tree a -> b Source #

A zygomorphism over a tree. Used if you want perform two folds over a tree in one pass.

As an example, checking if a tree is balanced can be performed like this using explicit recursion:

isBalanced :: Tree a -> Bool
isBalanced Leaf = True
isBalanced (Node _ l r)
= length l == length r && isBalanced l && isBalanced r


However, this algorithm performs several extra passes over the tree. A more efficient version is much harder to read, however:

isBalanced :: Tree a -> Bool
isBalanced = snd . go where
go Leaf = (0 :: Int,True)
go (Node _ l r) =
let (llen,lbal) = go l
(rlen,rbal) = go r
in (llen + rlen + 1, llen == rlen && lbal && rbal)


This same algorithm (the one pass version) can be expressed as a zygomorphism:

isBalanced :: Tree a -> Bool
isBalanced =
zygoTree
(0 :: Int)
(\_ x y -> 1 + x + y)
True
go
where
go _ llen lbal rlen rbal = llen == rlen && lbal && rbal


drawBinaryTree :: Show a => Tree a -> String Source #

Pretty-print a tree.