This package provides three different binary tree types, in a very generic and portable form. They are:
Preorder:
data Tree a = Leaf | Node a (Tree a) (Tree a)
Inorder:
data Tree a = Leaf | Node (Tree a) a (Tree a)
Leafy:
data Tree a = Leaf a | Tree a :*: Tree a
Effort is made to ensure the types provided are portable and generic: CI tests go back to GHC 7.2, and in cases where more than one sensible instance exists none are provided.
Tricky instances include:
- Lifted Read and Show classes (Read1, Show1, etc).
- MonadFix for the leafy tree and Applicative for the others.
- Semigroup and Monoid instances.
- Handwritten foldable instances
Beyond the instances, a general drawing algorithm is provided, to produce diagrams like so:
┌1
┌2┤
│ └3
4┤
│ ┌5
└6┤
└7
┌[1,2,3]
┌2<=3┤
│ └[1,3,2]
┌1<=3┤
│ └[3,1,2]
1<=2┤
│ ┌[2,1,3]
└1<=3┤
│ ┌[2,3,1]
└2<=3┤
└[3,2,1]
The library is tested using quickcheck and doctest.