Monads and custom traversal functions in Haskell

Question

Given the following simple BST definition:

data Tree x = Empty | Leaf x | Node x (Tree x) (Tree x)
          deriving (Show, Eq)

inOrder :: Tree x -> [x]
inOrder Empty                  = []
inOrder (Leaf x)               = [x]
inOrder (Node root left right) = inOrder left ++ [root] ++ inOrder right

I'd like to write an in-order function that can have side effects. I achieved that with:

inOrderM :: (Show x, Monad m) => (x -> m a) -> Tree x -> m ()
inOrderM f (Empty) = return ()
inOrderM f (Leaf y) = f y >> return ()
inOrderM f (Node root left right) = inOrderM f left >> f root >> inOrderM f right

-- print tree in order to stdout
inOrderM print tree

This works fine, but it seems repetitive - the same logic is already present in inOrder and my experience with Haskell leads me to believe that I'm probably doing something wrong if I'm writing a similar thing twice.

Is there any way that I can write a single function inOrder that can take either pure or monadic functions?

Answer 1

In inOrder you are mapping a Tree x to a [x], i. e. you sequentialize your tree. Why not just use mapM or mapM_ on the resulting list?

mapM_ print $ inOrder tree

Just to remind the types of the functions I've mentioned:

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
mapM_ :: (Monad m) => (a -> m b) -> [a] -> m ()

Answer 2

You might want to look at implementing the Data.Traversable class or Data.Foldable class for your tree structure. Each only requires the definition of a single method.

In particular, if you implement the Data.Foldable class, you get the following two functions for free:

mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
toList :: Foldable t => t a -> [a]

It will also give you the rich set of functions (foldr, concatMap, any, ...) that you are used to using with the list type.

You only have to implement one of the following functions to create an instance of Data.Foldable:

foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b