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

filled `a`

.

`>>>`

Node () (Node () (Node () Leaf Leaf) Leaf) (Node () Leaf Leaf)`replicateTree 4 ()`

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

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

replicates the action `replicateA`

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