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 preorder 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 -> 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
- 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 preorder binary tree.

Functor Tree Source # | |

Applicative Tree Source # | |

Foldable Tree Source # | |

Traversable Tree Source # | |

Eq1 Tree Source # | |

Ord1 Tree Source # | |

Read1 Tree Source # | |

Show1 Tree Source # | |

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

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

filled `a`

.

`>>>`

┌() ┌()┘ ()┤ └()`putStr (drawTree (replicate 4 ()))`

\(NonNegative 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 a preorder traversal (same 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 :: [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

# Querying

# Display

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

Convert a tree to a human-readable structural representation.

`>>>`

┌3 ┌2┤ │ └4 1┤ │ ┌6 └5┤ └7`putStr (drawTree (fromList [1..7]))`

drawTreeWith :: (a -> String) -> Tree a -> ShowS Source #

Pretty-print a tree with a custom show function.

`>>>`

┌─ ┌─┤ │ └─ ─┤ │ ┌─ └─┤ └─`putStr (drawTreeWith (const "─") (fromList [1..7]) "")`

`>>>`

abc`putStr (drawTreeWith id (singleton "abc") "")`

`>>>`

┌d abc┘`putStr (drawTreeWith id (Node "abc" (singleton "d") Leaf) "")`

`>>>`

┌ef ┌d┘ abc┤ └ghij`putStr (drawTreeWith id (fromList ["abc", "d", "ef", "ghij"]) "")`