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，因为它应该返回树和累积的预订编号，但我不知道该怎么做。

欢迎提出任何建议。

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

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