Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
A simple, generic binary tree and some operations.
- data Tree a
- unfoldTree :: (b -> Maybe (a, b, b)) -> b -> Tree a
- replicate :: Int -> a -> Tree a
- replicateA :: Applicative f => Int -> f a -> f (Tree a)
- singleton :: a -> Tree a
- empty :: Tree a
- fromList :: [a] -> Tree a
- foldTree :: b -> (a -> b -> b -> b) -> Tree a -> b
- zygoTree :: p -> (a -> p -> p -> p) -> b -> (a -> p -> b -> p -> b -> b) -> Tree a -> b
- drawBinaryTree :: Show a => Tree a -> String
The tree type
A simple binary tree.
Functor Tree Source # | |
Foldable Tree Source # | |
Traversable 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 # | This instance is necessarily inefficient, to obey the monoid laws.
toList (mappend xs (ys :: Tree Int)) === mappend (toList xs) (toList ys) |
NFData a => NFData (Tree a) Source # | |
Generic1 * Tree Source # | |
type Rep (Tree a) Source # | |
type Rep1 * Tree Source # | |
Construction
unfoldTree :: (b -> Maybe (a, b, b)) -> b -> Tree a Source #
Unfold a tree from a seed.
replicate :: Int -> a -> Tree a Source #
creates a tree of size replicate
n an
filled a
.
>>>
putStr (drawBinaryTree (replicate 4 ()))
() () () ()
\(NonNegative n) -> length (replicate n ()) === n
replicateA :: Applicative f => Int -> f a -> f (Tree a) Source #
replicates the action replicateA
n aa
n
times, trying
to balance the result as much as possible. The actions are executed
in a preorder traversal (same as the Foldable
instance.)
>>>
toList (evalState (replicateA 10 (State (\s -> (s, s + 1)))) 1)
[1,2,3,4,5,6,7,8,9,10]
fromList :: [a] -> Tree a Source #
Construct a tree from a list, in an preorder fashion.
toList (fromList xs) === xs
Consumption
foldTree :: b -> (a -> b -> b -> b) -> Tree a -> b Source #
Fold over a tree.
foldTree Leaf Node xs === xs
zygoTree :: p -> (a -> p -> p -> p) -> b -> (a -> p -> b -> p -> 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