| Safe Haskell | Safe |
|---|---|
| Language | Haskell2010 |
Data.Traversable.TreeLike
Description
By providing a TreeLike instance, a functor can be traversed in several
orders:
inorder/InOrder- Viewing a
TreeLikefunctor 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
TreeLikefunctor 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
TreeLikefunctor 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
- class Functor tree => TreeLike tree where
- treeTraverse :: Applicative f => (a -> f b) -> (forall subtree. TreeLike subtree => subtree a -> f (subtree b)) -> tree a -> f (tree b)
- treeFoldMap :: (Monoid m, TreeLike tree) => (a -> m) -> (m -> m) -> tree a -> m
- newtype Forest t tree a = Forest {
- getForest :: t (tree a)
- newtype Flat t a = Flat {
- getFlat :: t a
- newtype List a = List {
- getList :: [a]
- inorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
- preorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
- postorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
- levelorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
- rlevelorder :: (Applicative f, TreeLike tree) => (a -> f b) -> tree a -> f (tree b)
- newtype InOrder tree a = InOrder {
- getInOrder :: tree a
- newtype PreOrder tree a = PreOrder {
- getPreOrder :: tree a
- newtype PostOrder tree a = PostOrder {
- getPostOrder :: tree a
- newtype LevelOrder tree a = LevelOrder {
- getLevelOrder :: tree a
- newtype RLevelOrder tree a = RLevelOrder {
- getRLevelOrder :: tree a
- showTree :: (TreeLike tree, Show a) => tree a -> ShowS
- printTree :: (TreeLike tree, Show a) => tree a -> IO ()
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 # | |
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 # | |
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 # | |
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 # | |
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 # | |
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
|
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
|
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 For example
|
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 exampleTree4
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]
Instances
| (Functor t, Functor tree) => Functor (Forest t tree) Source # | |
| (Traversable t, TreeLike tree) => TreeLike (Forest t tree) Source # | |
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 # | |
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]
Instances
| Functor t => Functor (Flat t) Source # | |
| Traversable t => TreeLike (Flat t) Source # | |
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 # | |
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]
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 traversed0┬──┬───┬─────────┐ │ │ │ │ 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 traversed0┬──┬───┬─────────┐ │ │ │ │ 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 traversed15┬──┬───┬─────────┐ │ │ │ │ 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 traversed0┬──┬───┬─────────┐ │ │ │ │ 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 traversed15─┬──┬─────┬────────┐ │ │ │ │ 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 # | |
| TreeLike tree => Foldable (InOrder tree) Source # | |
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 # | |
| TreeLike tree => Traversable (InOrder tree) Source # | |
Defined in Data.Traversable.TreeLike | |
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 # | |
| TreeLike tree => Foldable (PreOrder tree) Source # | |
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 # | |
| TreeLike tree => Traversable (PreOrder tree) Source # | |
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 # | |
| TreeLike tree => Foldable (PostOrder tree) Source # | |
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 # | |
| TreeLike tree => Traversable (PostOrder tree) Source # | |
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 # | |
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 # | |
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 # | |
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 # | |
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 # | |
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 # | |
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) # | |