Data.Traversable.TreeLike

By providing a TreeLike instance, a functor can be traversed in several orders:

inorder / InOrder

Viewing a TreeLike functor as a sequence of values and subtrees, an inorder traversal iterates through this sequence visiting values and traversing subtrees in the order they are given.

>>> printTree (label inorder exampleBinaryTree)
      ┌──────6───┐
      │          │
  ┌──2┴───┐   ┌7─┴──┐
  │       │   │     │
┌0┴┐    ┌─┴5┐ ╵  ┌─9┴─┐
│  │    │   │    │    │
╵ ┌1┐ ┌3┴┐  ╵   ┌8┐ ┌10┐
  │ │ │  │      │ │ │  │
  ╵ ╵ ╵ ┌4┐     ╵ ╵ ╵  ╵
        │ │
        ╵ ╵

preorder / PreOrder

Viewing a TreeLike functor as a sequence of values and subtrees, a preorder traversal visits all the values in the sequence before traversing the subtrees.

>>> printTree (label preorder exampleBinaryTree)
      ┌──────0───┐
      │          │
  ┌──1┴───┐   ┌7─┴──┐
  │       │   │     │
┌2┴┐    ┌─┴4┐ ╵  ┌─8┴─┐
│  │    │   │    │    │
╵ ┌3┐ ┌5┴┐  ╵   ┌9┐ ┌10┐
  │ │ │  │      │ │ │  │
  ╵ ╵ ╵ ┌6┐     ╵ ╵ ╵  ╵
        │ │
        ╵ ╵

postorder / PostOrder

Viewing a TreeLike functor as a sequence of values and subtrees, a postorder traversal traverses all the subtrees in the sequence before visiting the values in the sequence before traversing the subtrees.

>>> printTree (label postorder exampleBinaryTree)
      ┌──────10───┐
      │           │
  ┌──5┴───┐    ┌9─┴─┐
  │       │    │    │
┌1┴┐    ┌─┴4┐  ╵  ┌─8─┐
│  │    │   │     │   │
╵ ┌0┐ ┌3┴┐  ╵    ┌6┐ ┌7┐
  │ │ │  │       │ │ │ │
  ╵ ╵ ╵ ┌2┐      ╵ ╵ ╵ ╵
        │ │
        ╵ ╵

levelorder / LevelOrder

Similar to a preorder traversal, a levelorder traversal first visits all the values at the root level before traversing any of the subtrees. Instead of traversing the subtrees one by one, though, a levelorder traversal interweaves their traversals, next visiting all the values at the root of each subtree, then visiting all the values at the roots of each subtree's subtrees, and so on. This is also known as a breadth-first traversal.

>>> printTree (label levelorder exampleBinaryTree)
       ┌──────0───┐
       │          │
  ┌──1─┴───┐   ┌2─┴─┐
  │        │   │    │
┌3┴┐    ┌──┴4┐ ╵  ┌─5─┐
│  │    │    │    │   │
╵ ┌6┐ ┌7┴─┐  ╵   ┌8┐ ┌9┐
  │ │ │   │      │ │ │ │
  ╵ ╵ ╵ ┌10┐     ╵ ╵ ╵ ╵
        │  │
        ╵  ╵

rlevelorder / RLevelOrder

Similar to a postlevel traversal, a reversed levelorder traversal only visits all the values at the root level after traversing all of the subtrees. Instead of traversing the subtrees one by one, though, a reversed levelorder traversal interweaves their traversals, working from the deepest level up, though still in left-to-right order.

>>> printTree (label rlevelorder exampleBinaryTree)
      ┌──────10───┐
      │           │
  ┌──8┴───┐    ┌9─┴─┐
  │       │    │    │
┌5┴┐    ┌─┴6┐  ╵  ┌─7─┐
│  │    │   │     │   │
╵ ┌1┐ ┌2┴┐  ╵    ┌3┐ ┌4┐
  │ │ │  │       │ │ │ │
  ╵ ╵ ╵ ┌0┐      ╵ ╵ ╵ ╵
        │ │
        ╵ ╵

Documentation

class Functor tree => TreeLike tree where

Notionally, functors are TreeLike if any values and TreeLike substructure they contain can be traversed distinctly.

For example, given the TreeDiagram monoid, one can use treeTraverse with the Const applicative to recursively create a drawing of any tree, rendering values inline with singleton and dropping a line to drawings of subtrees with subtree:

>>> :{
printTree :: (Show a, TreeLike tree) => tree a -> IO ()
printTree = printTreeDiagram . drawTree where
  drawTree :: (Show a, TreeLike tree) => tree a -> TreeDiagram
  drawTree = getConst . treeTraverse (Const . singleton) (Const . subtree . drawTree)
:}

This common pattern of mapping each element to a monoid and then modifying each monoidal value generated from a subtree is captured by treeFoldMap, which gives a slightly less verbose implementation of printTree.

>>> printTree = printTreeDiagram . treeFoldMap singleton subtree

Instances of TreeLike are encouraged to avoid recursively defining treeTraverse in terms of itself, and to instead traverse subtrees using the provided argument.

For example, given this definition for balanced binary trees:

>>> :{
data BBT a = Nil | a `Cons` BBT (a,a)
  deriving Functor
infixr 4 `Cons`
:}

Its TreeLike instance can be defined as:

>>> :{
instance TreeLike BBT where
  treeTraverse = \f g t -> case t of
     Nil          -> pure Nil
     a `Cons` at  -> branch <$> g (fst <$> at) <*> f a <*> g (snd <$> at)
   where
     branch :: BBT b -> b -> BBT b -> BBT b
     branch Nil b ~Nil = b `Cons` Nil
     branch (x `Cons` xt) b ~(y `Cons` yt) = b `Cons` branch xt (x,y) yt
:}

This definition exposes the substructure in a way that can be used by functions implemented in terms of treeTraverse, such as printTree:

>>> printTree $ 1 `Cons` (2,3) `Cons` ((4,5),(6,7)) `Cons` Nil
   ┌───1───┐
   │       │
 ┌─2─┐   ┌─3─┐
 │   │   │   │
┌4┐ ┌6┐ ┌5┐ ┌7┐
│ │ │ │ │ │ │ │
╵ ╵ ╵ ╵ ╵ ╵ ╵ ╵

Minimal complete definition

treeTraverse

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall subtree. TreeLike subtree => subtree a -> f (subtree b)) -> tree a -> f (tree b)

Instances

TreeLike Tree

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> Tree a -> f (Tree b)

TreeLike BinaryTree

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> BinaryTree a -> f (BinaryTree b)

TreeLike List

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> List a -> f (List b)

Traversable t => TreeLike (Flat t)

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> Flat t a -> f (Flat t b)

(Traversable t, TreeLike tree) => TreeLike (Forest t tree)

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> Forest t tree a -> f (Forest t tree b)

(TreeLike fst, TreeLike snd) => TreeLike (Product * fst snd)

Use Product to combine a pair of TreeLike values into a single tree.

>>> smallBinaryTree = Branch (Branch Leaf [0,1] Leaf) [0] (Branch Leaf [0,2] Leaf)
>>> smallRoseTree = Node [1] [Node [1,0] [], Node [1,1] [], Node [1,2] [], Node [1,3] []]
>>> printTree $ Pair smallBinaryTree smallRoseTree
        ┌────────────────────┐
        │                    │
   ┌───[0]───┐   [1]──┬─────┬┴────┬─────┐
   │         │        │     │     │     │
┌[0,1]┐   ┌[0,2]┐   [1,0] [1,1] [1,2] [1,3]
│     │   │     │
╵     ╵   ╵     ╵
>>> visit a = StateT $ \e -> print a >> return (e, succ e)
>>> traversed <- postorder visit (Pair smallBinaryTree smallRoseTree) `evalStateT` 0
[0,1]
[0,2]
[0]
[1,0]
[1,1]
[1,2]
[1,3]
[1]
>>> printTree traversed
   ┌───────┐
   │       │
 ┌─2─┐ 7┬─┬┴┬─┐
 │   │  │ │ │ │
┌0┐ ┌1┐ 3 4 5 6
│ │ │ │
╵ ╵ ╵ ╵

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> Product * fst snd a -> f (Product * fst snd b)

(TreeLike left, TreeLike right) => TreeLike (Sum * left right)

Use Sum to unify two different types of trees into a single type.

>>> smallBinaryTree = Branch (Branch Leaf [0,1] Leaf) [0] (Branch Leaf [0,2] Leaf)
>>> smallRoseTree = Node [1] [Node [1,0] [], Node [1,1] [], Node [1,2] [], Node [1,3] []]
>>> someTree b = if not b then InL smallBinaryTree else InR smallRoseTree
>>> :t someTree
someTree :: Num a => Bool -> Sum BinaryTree Tree [a]
>>> printTree (someTree False)
        ╷
        │
   ┌───[0]───┐
   │         │
┌[0,1]┐   ┌[0,2]┐
│     │   │     │
╵     ╵   ╵     ╵
>>> printTree (someTree True)
            ╷
            │
[1]──┬─────┬┴────┬─────┐
     │     │     │     │
   [1,0] [1,1] [1,2] [1,3]

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> Sum * left right a -> f (Sum * left right b)

(TreeLike outer, TreeLike inner) => TreeLike (Compose * * outer inner)

Treat subtrees and values of outer (inner a) as subtrees of Compose outer inner a.

For example

>>> :{
exampleCompose =  Compose $ 
   Branch 
     (Branch Leaf (Node 'a' [Node 'b' [], Node 'c' [], Node 'd' []]) Leaf)
     (Node 'e' [Node 'f' [Node 'g' [], Node 'h' []]]) 
     (Branch Leaf (Node 'i' [Node 'i' [Node 'j' [Node 'k' []]]]) Leaf)
:}

>>> printTree exampleCompose
        ┌─────────────┬───────────────┐
        │             │               │
┌───────┼───────┐ 'e'─┴──┐     ┌────┬─┴──────┐
│       │       │        │     │    │        │
╵ 'a'─┬─┴─┬───┐ ╵    'f'─┼───┐ ╵ 'i'┴──┐     ╵
      │   │   │          │   │         │
     'b' 'c' 'd'        'g' 'h'     'i'┴─┐
                                         │
                                       'j'─┐
                                           │
                                          'k'
>>> treeFoldMap (const ["value"]) (const ["subtree"]) exampleCompose
["subtree","subtree","subtree"]

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> Compose * * outer inner a -> f (Compose * * outer inner b)

treeFoldMap :: (Monoid m, TreeLike tree) => (a -> m) -> (m -> m) -> tree a -> m

Recursively fold a tree into a monoid, using the given functions to transform values and folded subtrees.

For example, one can find the maximum depth of a tree:

>>> printTree exampleTree
[]─┬─────┬───────────┬─────────────────────────────┐
   │     │           │                             │
  [0] [1]┴─┐  [2]──┬─┴─────┐       [3]──┬───────┬──┴──────────────┐
           │       │       │            │       │                 │
         [1,0]   [2,0] [2,1]───┐      [3,0] [3,1]───┐   [3,2]───┬─┴────────┐
                               │                    │           │          │
                            [2,1,0]              [3,1,0]     [3,2,0] [3,2,1]────┐
                                                                                │
                                                                            [3,2,1,0]
>>> :set -XGeneralizedNewtypeDeriving
>>> import GHC.Natural
>>> :{
newtype Max = Max { getMax :: Natural } deriving (Num, Enum)
instance Monoid Max where
  mempty = Max 0
  Max a `mappend` Max b = Max $ a `max` b
:}

>>> getMax $ treeFoldMap (const 0) succ exampleTree
4

TreeLike wrappers

These newtypes define TreeLike instances for Traversable types.

newtype Forest t tree a

A newtype wrapper to allow traversing an entire traversable of trees simultaneously.

>>> printTree $ Forest exampleTrees
 ┌─────┬───────────┬─────────────────────────────┐
 │     │           │                             │
[0] [1]┴─┐  [2]──┬─┴─────┐       [3]──┬───────┬──┴──────────────┐
         │       │       │            │       │                 │
       [1,0]   [2,0] [2,1]───┐      [3,0] [3,1]───┐   [3,2]───┬─┴────────┐
                             │                    │           │          │
                          [2,1,0]              [3,1,0]     [3,2,0] [3,2,1]────┐
                                                                              │
                                                                          [3,2,1,0]
>>> visit a = StateT $ \e -> print a >> return (e, succ e)
>>> traversed <- levelorder visit (Forest exampleTrees) `evalStateT` 0
[0]
[1]
[2]
[3]
[1,0]
[2,0]
[2,1]
[3,0]
[3,1]
[3,2]
[2,1,0]
[3,1,0]
[3,2,0]
[3,2,1]
[3,2,1,0]
>>> printTree traversed
┌──┬───┬────────┐
│  │   │        │
0 1┤ 2┬┴─┐ 3┬──┬┴────┐
   │  │  │  │  │     │
   4  5 6┴┐ 7 8┴┐ 9─┬┴──┐
          │     │   │   │
         10    11  12 13┴┐
                         │
                        14

This is more of a convenience than a necessity, as Forest t tree ~ Compose (Flat t) tree

>>> printTree . Compose $ Flat exampleTrees
 ┌─────┬───────────┬─────────────────────────────┐
 │     │           │                             │
[0] [1]┴─┐  [2]──┬─┴─────┐       [3]──┬───────┬──┴──────────────┐
         │       │       │            │       │                 │
       [1,0]   [2,0] [2,1]───┐      [3,0] [3,1]───┐   [3,2]───┬─┴────────┐
                             │                    │           │          │
                          [2,1,0]              [3,1,0]     [3,2,0] [3,2,1]────┐
                                                                              │
                                                                          [3,2,1,0]

Constructors

Forest

Fields

• getForest :: t (tree a)

Instances

(Functor tree, Functor t) => Functor (Forest t tree)

Methods

fmap :: (a -> b) -> Forest t tree a -> Forest t tree b

(<$) :: a -> Forest t tree b -> Forest t tree a

(Traversable t, TreeLike tree) => TreeLike (Forest t tree)

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> Forest t tree a -> f (Forest t tree b)

newtype Flat t a

A newtype wraper for t a whose TreeLike instance treats the t a as a flat structure with no subtrees.

>>> printTree $ Flat [1..5]
1─2─3─4─5
>>> import Data.Foldable (toList)
>>> toList . PostOrder $ Flat [1..5]
[1,2,3,4,5]

Constructors

Flat

Fields

• getFlat :: t a

Instances

Functor t => Functor (Flat t)

Methods

fmap :: (a -> b) -> Flat t a -> Flat t b

(<$) :: a -> Flat t b -> Flat t a

Traversable t => TreeLike (Flat t)

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> Flat t a -> f (Flat t b)

newtype List a

A newtype wrapper for [a] whose TreeLike instance treats each cons-cell as a tree containing one value and one subtree.

>>> printTree $ List [1..5]
1─┐
  │
 2┴┐
   │
  3┴┐
    │
   4┴┐
     │
    5┤
     │
     ╵
>>> import Data.Foldable (toList)
>>> toList . PostOrder $ List [1..5]
[5,4,3,2,1]

Contrast with Flat [] a:

>>> printTree $ Flat [1..5]
1─2─3─4─5
>>> toList . PostOrder $ Flat [1..5]
[1,2,3,4,5]

Constructors

List

Fields

• getList :: [a]

Instances

Functor List

Methods

fmap :: (a -> b) -> List a -> List b

(<$) :: a -> List b -> List a

TreeLike List

Methods

treeTraverse :: Applicative f => (a -> f b) -> (forall (subtree :: * -> *). TreeLike subtree => subtree a -> f (subtree b)) -> List a -> f (List b)

Traversals

Each TreeLike type admits multiple traversal orders:

inorder, preorder, postorder, levelorder, rlevelorder
  :: TreeLike tree => Traversal (tree a) (tree b) a b

Using the definition of Traversal from Control.Lens.Traversal:

type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t 

inorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)

Traverse all the values in a tree in left-to-right order.

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> visit a = StateT $ \e -> print a >> return (e, succ e)
>>> traversed <- inorder visit exampleBinaryTree `evalStateT` 0
[L,L]
[L,L,R]
[L]
[L,R,L]
[L,R,L,R]
[L,R]
[]
[R]
[R,R,L]
[R,R]
[R,R,R]
>>> printTree traversed
      ┌──────6───┐
      │          │
  ┌──2┴───┐   ┌7─┴──┐
  │       │   │     │
┌0┴┐    ┌─┴5┐ ╵  ┌─9┴─┐
│  │    │   │    │    │
╵ ┌1┐ ┌3┴┐  ╵   ┌8┐ ┌10┐
  │ │ │  │      │ │ │  │
  ╵ ╵ ╵ ┌4┐     ╵ ╵ ╵  ╵
        │ │
        ╵ ╵
>>> printTree exampleTree
[]─┬─────┬───────────┬─────────────────────────────┐
   │     │           │                             │
  [0] [1]┴─┐  [2]──┬─┴─────┐       [3]──┬───────┬──┴──────────────┐
           │       │       │            │       │                 │
         [1,0]   [2,0] [2,1]───┐      [3,0] [3,1]───┐   [3,2]───┬─┴────────┐
                               │                    │           │          │
                            [2,1,0]              [3,1,0]     [3,2,0] [3,2,1]────┐
                                                                                │
                                                                            [3,2,1,0]
>>> traversed <- inorder visit exampleTree `evalStateT` 0
[]
[0]
[1]
[1,0]
[2]
[2,0]
[2,1]
[2,1,0]
[3]
[3,0]
[3,1]
[3,1,0]
[3,2]
[3,2,0]
[3,2,1]
[3,2,1,0]
>>> printTree traversed
0┬──┬───┬─────────┐
 │  │   │         │
 1 2┤ 4┬┴─┐ 8┬───┬┴─────┐
    │  │  │  │   │      │
    3  5 6┤  9 10┴┐ 12─┬┴──┐
          │       │    │   │
          7      11   13 14┴┐
                            │
                           15

preorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)

Traverse all the values of a node, then recurse into each of its subtrees in left-to-right order.

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> visit a = StateT $ \e -> print a >> return (e, succ e)
>>> traversed <- preorder visit exampleBinaryTree `evalStateT` 0
[]
[L]
[L,L]
[L,L,R]
[L,R]
[L,R,L]
[L,R,L,R]
[R]
[R,R]
[R,R,L]
[R,R,R]
>>> printTree traversed
      ┌──────0───┐
      │          │
  ┌──1┴───┐   ┌7─┴──┐
  │       │   │     │
┌2┴┐    ┌─┴4┐ ╵  ┌─8┴─┐
│  │    │   │    │    │
╵ ┌3┐ ┌5┴┐  ╵   ┌9┐ ┌10┐
  │ │ │  │      │ │ │  │
  ╵ ╵ ╵ ┌6┐     ╵ ╵ ╵  ╵
        │ │
        ╵ ╵
>>> printTree exampleTree
[]─┬─────┬───────────┬─────────────────────────────┐
   │     │           │                             │
  [0] [1]┴─┐  [2]──┬─┴─────┐       [3]──┬───────┬──┴──────────────┐
           │       │       │            │       │                 │
         [1,0]   [2,0] [2,1]───┐      [3,0] [3,1]───┐   [3,2]───┬─┴────────┐
                               │                    │           │          │
                            [2,1,0]              [3,1,0]     [3,2,0] [3,2,1]────┐
                                                                                │
                                                                            [3,2,1,0]
>>> traversed <- inorder visit exampleTree `evalStateT` 0
[]
[0]
[1]
[1,0]
[2]
[2,0]
[2,1]
[2,1,0]
[3]
[3,0]
[3,1]
[3,1,0]
[3,2]
[3,2,0]
[3,2,1]
[3,2,1,0]
>>> printTree traversed
0┬──┬───┬─────────┐
 │  │   │         │
 1 2┤ 4┬┴─┐ 8┬───┬┴─────┐
    │  │  │  │   │      │
    3  5 6┤  9 10┴┐ 12─┬┴──┐
          │       │    │   │
          7      11   13 14┴┐
                            │
                           15

postorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)

Traverse all the values of a node after recursing into each of its subtrees in left-to-right order.

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> visit a = StateT $ \e -> print a >> return (e, succ e)
>>> traversed <- postorder visit exampleBinaryTree `evalStateT` 0
[L,L,R]
[L,L]
[L,R,L,R]
[L,R,L]
[L,R]
[L]
[R,R,L]
[R,R,R]
[R,R]
[R]
[]
>>> printTree traversed
      ┌──────10───┐
      │           │
  ┌──5┴───┐    ┌9─┴─┐
  │       │    │    │
┌1┴┐    ┌─┴4┐  ╵  ┌─8─┐
│  │    │   │     │   │
╵ ┌0┐ ┌3┴┐  ╵    ┌6┐ ┌7┐
  │ │ │  │       │ │ │ │
  ╵ ╵ ╵ ┌2┐      ╵ ╵ ╵ ╵
        │ │
        ╵ ╵
>>> printTree exampleTree
[]─┬─────┬───────────┬─────────────────────────────┐
   │     │           │                             │
  [0] [1]┴─┐  [2]──┬─┴─────┐       [3]──┬───────┬──┴──────────────┐
           │       │       │            │       │                 │
         [1,0]   [2,0] [2,1]───┐      [3,0] [3,1]───┐   [3,2]───┬─┴────────┐
                               │                    │           │          │
                            [2,1,0]              [3,1,0]     [3,2,0] [3,2,1]────┐
                                                                                │
                                                                            [3,2,1,0]
>>> traversed <- postorder visit exampleTree `evalStateT` 0
[0]
[1,0]
[1]
[2,0]
[2,1,0]
[2,1]
[2]
[3,0]
[3,1,0]
[3,1]
[3,2,0]
[3,2,1,0]
[3,2,1]
[3,2]
[3]
[]
>>> printTree traversed
15┬──┬───┬─────────┐
  │  │   │         │
  0 2┤ 6┬┴─┐ 14┬──┬┴────┐
     │  │  │   │  │     │
     1  3 5┤   7 9┤ 13─┬┴──┐
           │      │    │   │
           4      8   10 12┴┐
                            │
                           11

levelorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)

Traverse all the values of a tree in left-to-right breadth-first order. (i.e. all nodes of depth 0, then all nodes of depth 1, then all nodes of depth 2, etc.)

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> visit a = StateT $ \e -> print a >> return (e, succ e)
>>> traversed <- levelorder visit exampleBinaryTree `evalStateT` 0
[]
[L]
[R]
[L,L]
[L,R]
[R,R]
[L,L,R]
[L,R,L]
[R,R,L]
[R,R,R]
[L,R,L,R]
>>> printTree traversed
       ┌──────0───┐
       │          │
  ┌──1─┴───┐   ┌2─┴─┐
  │        │   │    │
┌3┴┐    ┌──┴4┐ ╵  ┌─5─┐
│  │    │    │    │   │
╵ ┌6┐ ┌7┴─┐  ╵   ┌8┐ ┌9┐
  │ │ │   │      │ │ │ │
  ╵ ╵ ╵ ┌10┐     ╵ ╵ ╵ ╵
        │  │
        ╵  ╵
>>> printTree exampleTree
[]─┬─────┬───────────┬─────────────────────────────┐
   │     │           │                             │
  [0] [1]┴─┐  [2]──┬─┴─────┐       [3]──┬───────┬──┴──────────────┐
           │       │       │            │       │                 │
         [1,0]   [2,0] [2,1]───┐      [3,0] [3,1]───┐   [3,2]───┬─┴────────┐
                               │                    │           │          │
                            [2,1,0]              [3,1,0]     [3,2,0] [3,2,1]────┐
                                                                                │
                                                                            [3,2,1,0]
>>> traversed <- levelorder visit exampleTree `evalStateT` 0
[]
[0]
[1]
[2]
[3]
[1,0]
[2,0]
[2,1]
[3,0]
[3,1]
[3,2]
[2,1,0]
[3,1,0]
[3,2,0]
[3,2,1]
[3,2,1,0]
>>> printTree traversed
0┬──┬───┬─────────┐
 │  │   │         │
 1 2┤ 3┬┴─┐ 4┬──┬─┴────┐
    │  │  │  │  │      │
    5  6 7┴┐ 8 9┴┐ 10─┬┴──┐
           │     │    │   │
          11    12   13 14┴┐
                           │
                          15

rlevelorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)

Traverse all the values of a tree in left-to-right inverse breadth-first order. (i.e. all nodes of n, then all nodes of depth n-1, then all nodes of depth n-2, etc.)

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> visit a = StateT $ \e -> print a >> return (e, succ e)
>>> traversed <- rlevelorder visit exampleBinaryTree `evalStateT` 0
[L,R,L,R]
[L,L,R]
[L,R,L]
[R,R,L]
[R,R,R]
[L,L]
[L,R]
[R,R]
[L]
[R]
[]
>>> printTree traversed
      ┌──────10───┐
      │           │
  ┌──8┴───┐    ┌9─┴─┐
  │       │    │    │
┌5┴┐    ┌─┴6┐  ╵  ┌─7─┐
│  │    │   │     │   │
╵ ┌1┐ ┌2┴┐  ╵    ┌3┐ ┌4┐
  │ │ │  │       │ │ │ │
  ╵ ╵ ╵ ┌0┐      ╵ ╵ ╵ ╵
        │ │
        ╵ ╵
>>> printTree exampleTree
[]─┬─────┬───────────┬─────────────────────────────┐
   │     │           │                             │
  [0] [1]┴─┐  [2]──┬─┴─────┐       [3]──┬───────┬──┴──────────────┐
           │       │       │            │       │                 │
         [1,0]   [2,0] [2,1]───┐      [3,0] [3,1]───┐   [3,2]───┬─┴────────┐
                               │                    │           │          │
                            [2,1,0]              [3,1,0]     [3,2,0] [3,2,1]────┐
                                                                                │
                                                                            [3,2,1,0]
>>> traversed <- rlevelorder visit exampleTree `evalStateT` 0
[3,2,1,0]
[2,1,0]
[3,1,0]
[3,2,0]
[3,2,1]
[1,0]
[2,0]
[2,1]
[3,0]
[3,1]
[3,2]
[0]
[1]
[2]
[3]
[]
>>> printTree traversed
15─┬──┬─────┬────────┐
   │  │     │        │
  11 12┐ 13┬┴─┐ 14┬──┼────┐
       │   │  │   │  │    │
       5   6 7┤   8 9┤ 10┬┴─┐
              │      │   │  │
              1      2   3 4┤
                            │
                            0

Traversable wrappers

These newtypes define Traversable instances for TreeLike types.

newtype InOrder tree a

Tree wrapper to use inorder traversal

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> _ <- traverse print $ InOrder exampleBinaryTree
[L,L]
[L,L,R]
[L]
[L,R,L]
[L,R,L,R]
[L,R]
[]
[R]
[R,R,L]
[R,R]
[R,R,R]

Constructors

InOrder

Fields

• getInOrder :: tree a

Instances

Functor tree => Functor (InOrder tree)

Methods

fmap :: (a -> b) -> InOrder tree a -> InOrder tree b

(<$) :: a -> InOrder tree b -> InOrder tree a

TreeLike tree => Foldable (InOrder tree)

Methods

fold :: Monoid m => InOrder tree m -> m

foldMap :: Monoid m => (a -> m) -> InOrder tree a -> m

foldr :: (a -> b -> b) -> b -> InOrder tree a -> b

foldr' :: (a -> b -> b) -> b -> InOrder tree a -> b

foldl :: (b -> a -> b) -> b -> InOrder tree a -> b

foldl' :: (b -> a -> b) -> b -> InOrder tree a -> b

foldr1 :: (a -> a -> a) -> InOrder tree a -> a

foldl1 :: (a -> a -> a) -> InOrder tree a -> a

toList :: InOrder tree a -> [a]

null :: InOrder tree a -> Bool

length :: InOrder tree a -> Int

elem :: Eq a => a -> InOrder tree a -> Bool

maximum :: Ord a => InOrder tree a -> a

minimum :: Ord a => InOrder tree a -> a

sum :: Num a => InOrder tree a -> a

product :: Num a => InOrder tree a -> a

TreeLike tree => Traversable (InOrder tree)

Methods

traverse :: Applicative f => (a -> f b) -> InOrder tree a -> f (InOrder tree b)

sequenceA :: Applicative f => InOrder tree (f a) -> f (InOrder tree a)

mapM :: Monad m => (a -> m b) -> InOrder tree a -> m (InOrder tree b)

sequence :: Monad m => InOrder tree (m a) -> m (InOrder tree a)

newtype PreOrder tree a

Tree wrapper to use preorder traversal

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> _ <- traverse print $ PreOrder exampleBinaryTree
[]
[L]
[L,L]
[L,L,R]
[L,R]
[L,R,L]
[L,R,L,R]
[R]
[R,R]
[R,R,L]
[R,R,R]

Constructors

PreOrder

Fields

• getPreOrder :: tree a

Instances

Functor tree => Functor (PreOrder tree)

Methods

fmap :: (a -> b) -> PreOrder tree a -> PreOrder tree b

(<$) :: a -> PreOrder tree b -> PreOrder tree a

TreeLike tree => Foldable (PreOrder tree)

Methods

fold :: Monoid m => PreOrder tree m -> m

foldMap :: Monoid m => (a -> m) -> PreOrder tree a -> m

foldr :: (a -> b -> b) -> b -> PreOrder tree a -> b

foldr' :: (a -> b -> b) -> b -> PreOrder tree a -> b

foldl :: (b -> a -> b) -> b -> PreOrder tree a -> b

foldl' :: (b -> a -> b) -> b -> PreOrder tree a -> b

foldr1 :: (a -> a -> a) -> PreOrder tree a -> a

foldl1 :: (a -> a -> a) -> PreOrder tree a -> a

toList :: PreOrder tree a -> [a]

null :: PreOrder tree a -> Bool

length :: PreOrder tree a -> Int

elem :: Eq a => a -> PreOrder tree a -> Bool

maximum :: Ord a => PreOrder tree a -> a

minimum :: Ord a => PreOrder tree a -> a

sum :: Num a => PreOrder tree a -> a

product :: Num a => PreOrder tree a -> a

TreeLike tree => Traversable (PreOrder tree)

Methods

traverse :: Applicative f => (a -> f b) -> PreOrder tree a -> f (PreOrder tree b)

sequenceA :: Applicative f => PreOrder tree (f a) -> f (PreOrder tree a)

mapM :: Monad m => (a -> m b) -> PreOrder tree a -> m (PreOrder tree b)

sequence :: Monad m => PreOrder tree (m a) -> m (PreOrder tree a)

newtype PostOrder tree a

Tree wrapper to use postorder traversal

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> _ <- traverse print $ PostOrder exampleBinaryTree
[L,L,R]
[L,L]
[L,R,L,R]
[L,R,L]
[L,R]
[L]
[R,R,L]
[R,R,R]
[R,R]
[R]
[]

Constructors

PostOrder

Fields

• getPostOrder :: tree a

Instances

Functor tree => Functor (PostOrder tree)

Methods

fmap :: (a -> b) -> PostOrder tree a -> PostOrder tree b

(<$) :: a -> PostOrder tree b -> PostOrder tree a

TreeLike tree => Foldable (PostOrder tree)

Methods

fold :: Monoid m => PostOrder tree m -> m

foldMap :: Monoid m => (a -> m) -> PostOrder tree a -> m

foldr :: (a -> b -> b) -> b -> PostOrder tree a -> b

foldr' :: (a -> b -> b) -> b -> PostOrder tree a -> b

foldl :: (b -> a -> b) -> b -> PostOrder tree a -> b

foldl' :: (b -> a -> b) -> b -> PostOrder tree a -> b

foldr1 :: (a -> a -> a) -> PostOrder tree a -> a

foldl1 :: (a -> a -> a) -> PostOrder tree a -> a

toList :: PostOrder tree a -> [a]

null :: PostOrder tree a -> Bool

length :: PostOrder tree a -> Int

elem :: Eq a => a -> PostOrder tree a -> Bool

maximum :: Ord a => PostOrder tree a -> a

minimum :: Ord a => PostOrder tree a -> a

sum :: Num a => PostOrder tree a -> a

product :: Num a => PostOrder tree a -> a

TreeLike tree => Traversable (PostOrder tree)

Methods

traverse :: Applicative f => (a -> f b) -> PostOrder tree a -> f (PostOrder tree b)

sequenceA :: Applicative f => PostOrder tree (f a) -> f (PostOrder tree a)

mapM :: Monad m => (a -> m b) -> PostOrder tree a -> m (PostOrder tree b)

sequence :: Monad m => PostOrder tree (m a) -> m (PostOrder tree a)

newtype LevelOrder tree a

Tree wrapper to use levelorder traversal

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> _ <- traverse print $ LevelOrder exampleBinaryTree
[]
[L]
[R]
[L,L]
[L,R]
[R,R]
[L,L,R]
[L,R,L]
[R,R,L]
[R,R,R]
[L,R,L,R]

Constructors

LevelOrder

Fields

• getLevelOrder :: tree a

Instances

Functor tree => Functor (LevelOrder tree)

Methods

fmap :: (a -> b) -> LevelOrder tree a -> LevelOrder tree b

(<$) :: a -> LevelOrder tree b -> LevelOrder tree a

TreeLike tree => Foldable (LevelOrder tree)

Methods

fold :: Monoid m => LevelOrder tree m -> m

foldMap :: Monoid m => (a -> m) -> LevelOrder tree a -> m

foldr :: (a -> b -> b) -> b -> LevelOrder tree a -> b

foldr' :: (a -> b -> b) -> b -> LevelOrder tree a -> b

foldl :: (b -> a -> b) -> b -> LevelOrder tree a -> b

foldl' :: (b -> a -> b) -> b -> LevelOrder tree a -> b

foldr1 :: (a -> a -> a) -> LevelOrder tree a -> a

foldl1 :: (a -> a -> a) -> LevelOrder tree a -> a

toList :: LevelOrder tree a -> [a]

null :: LevelOrder tree a -> Bool

length :: LevelOrder tree a -> Int

elem :: Eq a => a -> LevelOrder tree a -> Bool

maximum :: Ord a => LevelOrder tree a -> a

minimum :: Ord a => LevelOrder tree a -> a

sum :: Num a => LevelOrder tree a -> a

product :: Num a => LevelOrder tree a -> a

TreeLike tree => Traversable (LevelOrder tree)

Methods

traverse :: Applicative f => (a -> f b) -> LevelOrder tree a -> f (LevelOrder tree b)

sequenceA :: Applicative f => LevelOrder tree (f a) -> f (LevelOrder tree a)

mapM :: Monad m => (a -> m b) -> LevelOrder tree a -> m (LevelOrder tree b)

sequence :: Monad m => LevelOrder tree (m a) -> m (LevelOrder tree a)

newtype RLevelOrder tree a

Tree wrapper to use rlevelorder traversal

>>> printTree exampleBinaryTree
                    ┌──────────────────────[]────────┐
                    │                                │
     ┌─────────[L]──┴─────────────┐          ┌[R]────┴──────┐
     │                            │          │              │
┌[L,L]────┐              ┌────────┴──[L,R]┐  ╵       ┌────[R,R]────┐
│         │              │                │          │             │
╵     ┌[L,L,R]┐   ┌[L,R,L]─────┐          ╵      ┌[R,R,L]┐     ┌[R,R,R]┐
      │       │   │            │                 │       │     │       │
      ╵       ╵   ╵       ┌[L,R,L,R]┐            ╵       ╵     ╵       ╵
                          │         │
                          ╵         ╵
>>> _ <- traverse print $ RLevelOrder exampleBinaryTree
[L,R,L,R]
[L,L,R]
[L,R,L]
[R,R,L]
[R,R,R]
[L,L]
[L,R]
[R,R]
[L]
[R]
[]

Constructors

RLevelOrder

Fields

• getRLevelOrder :: tree a

Instances

Functor tree => Functor (RLevelOrder tree)

Methods

fmap :: (a -> b) -> RLevelOrder tree a -> RLevelOrder tree b

(<$) :: a -> RLevelOrder tree b -> RLevelOrder tree a

TreeLike tree => Foldable (RLevelOrder tree)

Methods

fold :: Monoid m => RLevelOrder tree m -> m

foldMap :: Monoid m => (a -> m) -> RLevelOrder tree a -> m

foldr :: (a -> b -> b) -> b -> RLevelOrder tree a -> b

foldr' :: (a -> b -> b) -> b -> RLevelOrder tree a -> b

foldl :: (b -> a -> b) -> b -> RLevelOrder tree a -> b

foldl' :: (b -> a -> b) -> b -> RLevelOrder tree a -> b

foldr1 :: (a -> a -> a) -> RLevelOrder tree a -> a

foldl1 :: (a -> a -> a) -> RLevelOrder tree a -> a

toList :: RLevelOrder tree a -> [a]

null :: RLevelOrder tree a -> Bool

length :: RLevelOrder tree a -> Int

elem :: Eq a => a -> RLevelOrder tree a -> Bool

maximum :: Ord a => RLevelOrder tree a -> a

minimum :: Ord a => RLevelOrder tree a -> a

sum :: Num a => RLevelOrder tree a -> a

product :: Num a => RLevelOrder tree a -> a

TreeLike tree => Traversable (RLevelOrder tree)

Methods

traverse :: Applicative f => (a -> f b) -> RLevelOrder tree a -> f (RLevelOrder tree b)

sequenceA :: Applicative f => RLevelOrder tree (f a) -> f (RLevelOrder tree a)

mapM :: Monad m => (a -> m b) -> RLevelOrder tree a -> m (RLevelOrder tree b)

sequence :: Monad m => RLevelOrder tree (m a) -> m (RLevelOrder tree a)

Convenience functions

showTree :: (TreeLike tree, Show a) => tree a -> ShowS

Render the tree as a string, using the TreeDiagram monoid.

printTree :: (TreeLike tree, Show a) => tree a -> IO ()

Print the tree, using the TreeDiagram monoid.