Haskell Language Traversable An instance of Traversable for a binary tree
Example
Implementations of traverse usually look like an implementation of fmap lifted into an Applicative context.
data Tree a = Leaf
| Node (Tree a) a (Tree a)
instance Traversable Tree where
traverse f Leaf = pure Leaf
traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f r
This implementation performs an in-order traversal of the tree.
ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf)
-- +--'b'--+
-- | |
-- +-'a'-+ +-'c'-+
-- | | | |
-- * * * *
ghci> traverse print myTree
'a'
'b'
'c'
The DeriveTraversable extension allows GHC to generate Traversable instances based on the structure of the type. We can vary the order of the machine-written traversal by adjusting the layout of the Node constructor.
data Inorder a = ILeaf
| INode (Inorder a) a (Inorder a) -- as before
deriving (Functor, Foldable, Traversable) -- also using DeriveFunctor and DeriveFoldable
data Preorder a = PrLeaf
| PrNode a (Preorder a) (Preorder a)
deriving (Functor, Foldable, Traversable)
data Postorder a = PoLeaf
| PoNode (Postorder a) (Postorder a) a
deriving (Functor, Foldable, Traversable)
-- injections from the earlier Tree type
inorder :: Tree a -> Inorder a
inorder Leaf = ILeaf
inorder (Node l x r) = INode (inorder l) x (inorder r)
preorder :: Tree a -> Preorder a
preorder Leaf = PrLeaf
preorder (Node l x r) = PrNode x (preorder l) (preorder r)
postorder :: Tree a -> Postorder a
postorder Leaf = PoLeaf
postorder (Node l x r) = PoNode (postorder l) (postorder r) x
ghci> traverse print (inorder myTree)
'a'
'b'
'c'
ghci> traverse print (preorder myTree)
'b'
'a'
'c'
ghci> traverse print (postorder myTree)
'a'
'c'
'b'
