CODEWITHSUNDEEP
haskelltree
Yan Zhu
Yan Zhu

Reputation: 4356

traversal on tree in Haskell with print

I have following toy haskell code for binary search tree. The function preorderV is to traverse the tree with a function applying to every element. It works fine for normal function. However if I apply function "print", I got compiling error. How could I make function related to IO work with preorderV?

Thanks

Code: 

data BSTree a = EmptyTree | Node a (BSTree a) (BSTree a) deriving (Show)
data Mode = IN | POST | PRE

singleNode :: a -> BSTree a
singleNode x = Node x EmptyTree EmptyTree

bstInsert :: (Ord a) => a -> BSTree a -> BSTree a
bstInsert x EmptyTree = singleNode x
bstInsert x (Node a left right)
          | x == a = Node a left right
          | x < a  = Node a (bstInsert x left) right
          | x > a  = Node a left (bstInsert x right)

buildTree :: String -> BSTree String
buildTree = foldr bstInsert EmptyTree . words    

preorderV :: (a->b) -> BSTree a -> BSTree b
preorderV f EmptyTree = EmptyTree
preorderV f (Node x left right) = Node (f x) (preorderV f left) (preorderV f right)

Error:

Couldn't match type ‘BSTree’ with ‘IO’
Expected type: IO (IO ())
  Actual type: BSTree (IO ())
In a stmt of a 'do' block: preorderV print $ buildTree content

Upvotes: 0

Views: 337

Answers (2)

Random Dev
Random Dev

Reputation: 52290

your code works so far but you got a BSTree (IO ()) back and as you use this inside a do Block (main most likely) you get the error.

what you now can do is fold over the tree to get the actions back, then you can use sequence or something similar to use each of those actions one after the other:

foldT :: (a -> s -> s) -> s -> BSTree a -> s
foldT _ s EmptyTree = s
foldT f s (Node a left right) =
  let s' = foldT f s left
      s'' = f a s'
  in foldT f s'' right

main :: IO ()
main = do
  let doPrint = preorderV print $ buildTree "C A B D E"
      folded = foldT (:) [] doPrint
  sequence_ . reverse $ folded

This will print

λ> :main
"A"
"B"
"C"
"D"
"E"

BTW: Your preorderV is usually called map ;)

Upvotes: 1

ErikR
ErikR

Reputation: 52057

The type of preorderV print $ buildTree content is BSTree (IO ()), that is, you are creating a binary tree of IO computations - you don't have an IO computation itself.

To do what I think you want to do you need to create a monadic version of preorderV which has the following type:

preorderVM :: (a -> IO ()) -> BSTree a -> IO ()
preorderVM f EmptyTree = ... -- what do you want to do here?
preorderVM f (Node x left right) = do
    f x 
    preorderVM f left
    preorderVM f right

Upvotes: 3

Related Questions