Haskell Monads and Custom Bypass Functions

Question

Given the following simple definition of BST:

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 would like to write a function in an order that can have side effects. I have achieved this:

 inOrderM :: (Show x, Monad m) => (x -> ma) -> Tree x -> m () inOrderM f (Empty) = return () inOrderM f (Leaf y) = fy >> 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 makes me believe that I probably do something wrong if I write a similar thing twice.

Is there a way to write a single inOrder function that can accept either pure or monadic functions?

Answer 1

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

 mapM_ print $ inOrder tree 

Just to recall the types of functions that I mentioned:

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

Answer 2

You may need to implement the Data.Traversable class or Data.Foldable class for your tree structure. Each only needs to define one method.

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

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

It will also provide you with a rich set of functions ( foldr , concatMap , any , ...) that you use to use with a list type.

You need to perform one of the following functions to create an instance of Data.Foldable :

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