Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
A simple, generic binary tree and some operations. Used in some of the heaps.
- data Tree a
- foldTree :: b -> (a -> b -> b -> b) -> Tree a -> b
- isHeap :: Ord a => Tree a -> Bool
- unfoldTree :: (b -> Maybe (a, b, b)) -> b -> Tree a
- replicateTree :: Int -> a -> Tree a
- replicateA :: Applicative f => Int -> f a -> f (Tree a)
- treeFromList :: [a] -> Tree a
- zygoTree :: b1 -> (a -> b1 -> b1 -> b1) -> b -> (a -> b1 -> b -> b1 -> b -> b) -> Tree a -> b
- drawBinaryTree :: Show a => Tree a -> String
Documentation
A simple binary tree for use in some of the heaps.
Functor Tree Source # | |
Foldable Tree Source # | |
Traversable Tree Source # | |
Generic1 Tree Source # | |
Eq1 Tree Source # | |
Ord1 Tree Source # | |
Read1 Tree Source # | |
Show1 Tree Source # | |
Eq a => Eq (Tree a) Source # | |
Data a => Data (Tree a) Source # | |
Ord a => Ord (Tree a) Source # | |
Read a => Read (Tree a) Source # | |
Show a => Show (Tree a) Source # | |
Generic (Tree a) Source # | |
Monoid (Tree a) Source # | |
NFData a => NFData (Tree a) Source # | |
type Rep1 Tree Source # | |
type Rep (Tree a) Source # | |
unfoldTree :: (b -> Maybe (a, b, b)) -> b -> Tree a Source #
Unfold a tree from a seed.
replicateTree :: Int -> a -> Tree a Source #
creates a tree of size replicateTree
n an
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 #
replicates the action replicateA
n aa
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 isBalancedLeaf
= 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 goLeaf
= (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