3

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.

4

2 回答 2

3

You can use mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) here to your advantage:

The mapAccumL function behaves like a combination of map and foldl; it applies a function to each element of a list, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new list.

Looking at the types, trying to connect the matching wires, main function would then look something like 

import Data.List (mapAccumL)

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 tree = tree2
   where
   (_, [tree2]) = mapAccumL g 1 [tree]
   g n Nil1 = (n, Nil2)
   g n (Node1 x trees) = (z, Node2 (x,n) trees2)
      where
      (z, trees2) = ....

                mapAccumL g (n+1) trees

There's no need for the Num a => constraint. You don't visit the nodes' values, you just count the nodes regardless of what they carry:

> numberTree (Node1 1.1 [Node1 2.2 [ Node1 3.3 [], Nil1], Node1 4.4 [] ])
Node2 (1.1,1) [Node2 (2.2,2) [Node2 (3.3,3) [],Nil2],Node2 (4.4,4) []]

于 2016-06-17T19:34:09.530 回答
2

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)
于 2016-06-17T23:14:27.377 回答