Copyright | (c) Donnacha Oisín Kidney 2018 |
---|---|

License | MIT |

Maintainer | mail@doisinkidney.com |

Stability | experimental |

Portability | portable |

Safe Haskell | Safe |

Language | Haskell2010 |

This module provides a simple leafy binary tree, as is needed in several applications. Instances, if sensible, are defined, and generally effort is made to keep the implementation as generic as possible.

- data Tree a
- unfoldTree :: (b -> Either a (b, b)) -> b -> Tree a
- replicate :: Int -> a -> Tree a
- replicateA :: Applicative f => Int -> f a -> f (Tree a)
- singleton :: a -> Tree a
- fromList :: HasCallStack => [a] -> Tree a
- foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
- depth :: Tree a -> Int
- drawTree :: Show a => Tree a -> String
- drawTreeWith :: (a -> String) -> Tree a -> ShowS
- printTree :: Show a => Tree a -> IO ()

# The tree type

A leafy binary tree.

Monad Tree Source # | |

Functor Tree Source # | |

MonadFix Tree Source # | |

Applicative Tree Source # | |

Foldable Tree Source # | |

Traversable Tree Source # | |

Eq1 Tree Source # | |

Ord1 Tree Source # | |

Read1 Tree Source # | |

Show1 Tree Source # | |

MonadZip 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 # | |

Semigroup (Tree a) Source # | |

NFData a => NFData (Tree a) Source # | |

Generic1 * Tree Source # | |

type Rep (Tree a) Source # | |

type Rep1 * Tree Source # | |

# Construction

unfoldTree :: (b -> Either 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 a`n`

filled with `a`

.

`>>>`

┌() ┌┤ │└() ┤ │┌() └┤ └()`printTree (replicate 4 ())`

\(Positive n) -> length (replicate n ()) === n

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

replicates the action `replicateA`

n a`a`

`n`

times, trying
to balance the result as much as possible. The actions are executed
in the same order as the `Foldable`

instance.

`>>>`

[1,2,3,4,5,6,7,8,9,10]`toList (evalState (replicateA 10 (State (\s -> (s, s + 1)))) 1)`

fromList :: HasCallStack => [a] -> Tree a Source #

Construct a tree from a list.

The constructed tree is somewhat, but not totally, balanced.

`>>>`

┌1 ┌┤ │└2 ┤ │┌3 └┤ └4`printTree (fromList [1,2,3,4])`

`>>>`

┌1 ┌┤ │└2 ┌┤ ││┌3 │└┤ │ └4 ┤ │┌5 └┤ └6`printTree (fromList [1,2,3,4,5,6])`

# Consumption

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

Fold over a tree.

foldTree Leaf (:*:) xs === xs

# Querying

# Display

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

Convert a tree to a human-readable structural representation.

`>>>`

┌1 ┌┤ │└2 ┤ └3`putStr (drawTree (Leaf 1 :*: Leaf 2 :*: Leaf 3))`