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

该函数将以先序遍历方式返回带编号的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的代码，因为它应该返回树和累计先序号，但我不知道如何实现。

欢迎提出任何建议。

- Vojacejo

---

我不明白为什么你需要 Num a 约束。 - melpomene

我认为你的辅助函数应该有类型 numberTree' :: Tree a -> Int -> (NumTree a, Int)。 - melpomene

谢谢，但我认为它是 numberTree' :: Tree a -> Int -> NumTree a 吗？ - Vojacejo

“Num a”是因为在树中将会有数字。 - Vojacejo

你的 numberTree 函数不应该关心树的元素，它只需要将数字相加即可。 - melpomene

Answer 1

你可以利用这里的mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])：

mapAccumL函数类似于map和foldl的组合，它将一个函数应用到列表的每个元素上，并将累加参数从左到右传递，最后返回此累加器的最终值和新列表。

查看类型并尝试连接匹配的线路，主要功能将如下:

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

不需要 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) []]

- Will Ness

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)

- chepner

---

非常感谢您提供的解决方案。它似乎正在运作，但在我的ghci中不是State单子。它是如何实现的？ - Vojacejo

@Vojacejo 请尝试访问 https://www.haskell.org/hoogle/?hoogle=Control.Monad.State。 - Will Ness