binary-tree-0.1.0.0

Copyright (c) Donnacha Oisín Kidney 2018 MIT mail@doisinkidney.com experimental portable Safe Haskell2010

Data.Tree.Binary.Leafy

Description

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.

Synopsis

# The tree type

data Tree a Source #

A leafy binary tree.

Constructors

 Leaf a (Tree a) :*: (Tree a) infixl 5

Instances

# Construction

unfoldTree :: (b -> Either a (b, b)) -> b -> Tree a Source #

Unfold a tree from a seed.

replicate :: Int -> a -> Tree a Source #

replicate n a creates a tree of size n filled with a.

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

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

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

replicateA n a replicates the action a n times, trying to balance the result as much as possible. The actions are executed in the same order as the Foldable instance.

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


singleton :: a -> Tree a Source #

A binary tree with one element.

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

Construct a tree from a list.

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

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

>>> printTree (fromList [1,2,3,4,5,6])
  ┌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

depth :: Tree a -> Int Source #

The depth of the tree.

>>> depth (singleton ())
1


# Display

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

Convert a tree to a human-readable structural representation.

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


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

Pretty-print a tree with a custom show function.

printTree :: Show a => Tree a -> IO () Source #

Pretty-print a tree