Haskell

Question

我正在准备非过程语言考试。我有测试任务的例子，不知道怎么解决。

任务如下：

给定两个树结构：

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

写函数

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

这将 return 在预购中编号 NumTree a。

我试过了，但不知道如何继续。

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))

我不知道怎么写这样的东西myMap，因为它应该return树和累积的预购号码，但我不知道该怎么做。

欢迎提出任何建议。

Answer 1

你可以在这里使用 mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) 来发挥你的优势：

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.

查看类型，尝试连接匹配的电线，然后 main 函数看起来像

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) 棵树

不需要 Num a => 约束。你不访问节点的值，你只计算节点，不管它们携带什么：

> 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) []]

Answer 2

这是 State monad 的一个很好的用途，它负责通过访问每个节点的递归调用线程化用于为每个节点编号的值。

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)

Haskell - 树的预序编号

Haskell - Preorder Numbering of Tree

preorder