tree-traversals-0.1.1.0: Functions and newtype wrappers for traversing Trees

Safe HaskellSafe
LanguageHaskell2010

Data.Traversable.TreeLike

Description

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┐      ╵ ╵ ╵ ╵
        │ │
        ╵ ╵
Synopsis

Documentation

class Functor tree => TreeLike tree where Source #

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┐
│ │ │ │ │ │ │ │
╵ ╵ ╵ ╵ ╵ ╵ ╵ ╵

Methods

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

Instances
TreeLike Tree Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

TreeLike BinaryTree Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

TreeLike List Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

Traversable t => TreeLike (Flat t) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

(Traversable t, TreeLike tree) => TreeLike (Forest t tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

(TreeLike fst, TreeLike snd) => TreeLike (Product fst snd) Source #

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
│ │ │ │
╵ ╵ ╵ ╵
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

(TreeLike left, TreeLike right) => TreeLike (Sum left right) Source #

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]
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

(TreeLike outer, TreeLike inner) => TreeLike (Compose outer inner) Source #

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"]
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

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

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
>>> import Data.Semigroup
>>> :{
newtype Max = Max { getMax :: Natural } deriving (Num, Enum)
instance Semigroup Max where
  (<>) = mappend
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 Source #

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

Instances
(Functor t, Functor tree) => Functor (Forest t tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

newtype Flat t a Source #

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

Instances
Functor t => Functor (Flat t) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

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

Traversable t => TreeLike (Flat t) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

newtype List a Source #

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

Instances
Functor List Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

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

TreeLike List Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

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) Source #

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) Source #

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) Source #

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) Source #

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) Source #

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

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

Instances
Functor tree => Functor (InOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

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

TreeLike tree => Foldable (InOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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

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

Instances
Functor tree => Functor (PreOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

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

TreeLike tree => Foldable (PreOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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

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

Instances
Functor tree => Functor (PostOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

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

TreeLike tree => Foldable (PostOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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

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

Instances
Functor tree => Functor (LevelOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

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

TreeLike tree => Foldable (LevelOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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

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

Instances
Functor tree => Functor (RLevelOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

Methods

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

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

TreeLike tree => Foldable (RLevelOrder tree) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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) Source # 
Instance details

Defined in Data.Traversable.TreeLike

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

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

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

Print the tree, using the TreeDiagram monoid.