Haskell - Preorder Numbering of Tree

Question

I'm preparing for my exam from nonprocedural languages. I have example of test task and I don't know how to solve it.

Task is following:

Given two tree structures:

data Tree a = Nil1 | Node1 a [Tree a]
data NumTree a  = Nil2 | Node2 (a,Int) [NumTree a]

write function

numberTree :: Num a => Tree a -> NumTree a

which will return numbered NumTree a in preorder.

I tried this, but don't know how to continue.

numberTree tree = numberTree' tree 1

numberTree' :: Num a => Tree a -> Int -> NumTree a
numberTree' Nil1 _ = Nil2
numberTree' (Node1 num list) x = (Node2 (num,x) (myMap x numberTree list))

I dont know how to write something like this myMap,because it should return tree and the acumulated preorder number, but i don't know how to do this.

Any suggestions are welcome.

Answer 1

This is a good use for the State monad, which takes care of threading the value used to number each node through the recursive calls that visit each node.

import Control.Monad
import Control.Monad.State

data Tree a = Nil1 | Node1 a [Tree a] deriving (Show)
data NumTree a = Nil2 | Node2 (a,Int) [NumTree a] deriving (Show)

numberTree :: Tree a -> NumTree a
numberTree Nil1 = Nil2
numberTree tree = evalState (numberTree' tree) 0

-- The state stores the value used to number the root
-- of the current tree. Fetch it with get, and put back
-- the number to use for the next root.
-- numberTree' is then used to number each child tree
-- in order before returning a new NumTree value.

numberTree' :: Tree a -> State Int (NumTree a)
numberTree' Nil1 = return Nil2
numberTree' (Node1 root children) = do rootNum <- get
                                       put (rootNum + 1)
                                       newChildren <- mapM numberTree' children
                                       return (Node2 (root, rootNum) newChildren)