algorithm - 如何在 Haskell 中编写 N 元树遍历函数

Question

当我按顺序访​​问时，我需要遍历 N 元树并向每个节点添加数字。我有这样定义的 n 叉树:

data NT a = N a [NT a] deriving Show

示例:
如果我有以下树:

let ntree = N "eric" [N "lea" [N "kristy" [],N "pedro" [] ,N "rafael" []],N "anna" [],N "bety" []]

我想把它转换成

let ntree = N (1,"eric") [N (2,"lea") [N (3,"kristy") [],N (4,"pedro") [] ,N (5,"rafael") []],N (6,"anna") [],N (7,"bety") []]

“先入为主”没那么重要。

我想看看如何编写一个函数 在级别 之间传递值，例如如何将数字向下传递给后继列表以及如何将更新的数字传递给父级并将该数字传递给其他分支。

到目前为止，我已经能够编写这样的函数:

traverse :: NT String -> String
traverse (N val []) =" "++val++" "
traverse (N val list) =val++" " ++ (concat $ map  traverse list)

哪个输出

"eric lea  kristy  pedro  rafael  anna  bety "

编辑: 问题是:

我怎样才能写一个函数

numberNodes :: NT a -> NT (a,Int)

根据树的前序遍历对节点进行编号？

我很难理解的是传递辅助数据，你能详细说明一下吗？

在这种具体情况下，一个 Int 表示我遍历这棵树的“时间”或顺序。

Answer 1

第一次尝试:努力工作

对于 n 叉树，需要进行三件事:元素编号、树编号和树的编号列表。将它们分开处理会有所帮助。类型优先:

aNumber   :: a                -- thing to number
          -> Int              -- number to start from
          -> ( (a, Int)       -- numbered thing
             , Int            -- next available number afterwards
             )

ntNumber  :: NT a             -- thing to number
          -> Int              -- number to start from
          -> ( NT (a, Int)    -- numbered thing
             , Int            -- next available number afterwards
             )

ntsNumber :: [NT a]           -- thing to number
          -> Int              -- number to start from
          -> ( [NT (a, Int)]  -- numbered thing
             , Int            -- next available number afterwards
             )

请注意，所有三种类型共享相同的模式。当您发现自己遵循某种模式时，显然是巧合，您就知道自己有机会学到一些东西。但是让我们先按一下，稍后再学习。

给元素编号很容易:将起始编号复制到输出中，然后将其后继作为下一个可用编号返回。

aNumber a i = ((a, i), i + 1)

对于另外两个，模式(又是那个词)是

将输入拆分为其顶级组件

依次给每个组件编号，将这些编号穿过

第一个使用模式匹配(视觉检查数据)和第二个使用 where 子句(获取输出的两个部分)很容易。

对于树，顶级拆分为我们提供了两个组件:元素和列表。在 where 子句中，我们按照这些类型的指示调用适当的编号函数。在每种情况下，“事物”输出都会告诉我们用什么来代替“事物”输入。同时，我们将数字贯穿，所以整体的起始数字是第一个组件的起始数字，第一个组件的“下一个”数字开始第二个，第二个的“下一个”数字是“下一个” ”的数字。

ntNumber (N a ants) i0  = (N ai aints, i2) where
  (ai,    i1) = aNumber   a    i0
  (aints, i2) = ntsNumber ants i1

对于列表，我们有两种可能性。一个空列表没有组件，所以我们直接返回它而不使用更多的数字。 “缺点”有两个组成部分，我们完全像以前一样，按照类型使用适当的编号函数。

ntsNumber []           i  = ([], i)
ntsNumber (ant : ants) i0 = (aint : aints, i2) where
  (aint,  i1) = ntNumber  ant  i0
  (aints, i2) = ntsNumber ants i1

让我们试一试吧。

> let ntree = N "eric" [N "lea" [N "kristy" [],N "pedro" [] ,N "rafael" []],N "anna" [],N "bety" []]
> ntNumber ntree 0
(N ("eric",0) [N ("lea",1) [N ("kristy",2) [],N ("pedro",3) [],N ("rafael",4) []],N ("anna",5) [],N ("bety",6) []],7)

所以我们在那里。但我们快乐吗？嗯，我不是。我有一种恼人的感觉，我写了 3 次几乎相同的类型和几乎相同的程序两次。如果我想对不同组织的数据(例如，您的二叉树)进行更多元素编号，我将不得不再次编写相同的内容。 Haskell 代码中的重复模式总是会错失机会:培养自我批评意识并询问是否有更简洁的方法很重要。

第二次尝试:编号和线程

我们在上面看到的两个重复模式是
1.类型的相似性，
2. 数字串接方式的相似性。

如果您匹配类型以查看共同点，您会注意到它们都是

input -> Int -> (output, Int)

用于不同的输入和输出。让我们为最大的公共(public)组件命名。

type Numbering output = Int -> (output, Int)

现在我们的三种类型是

aNumber   :: a      -> Numbering (a, Int)
ntNumber  :: NT a   -> Numbering (NT (a, Int))
ntsNumber :: [NT a] -> Numbering [NT (a, Int)]

你经常在 Haskell 中看到这样的类型:

             input  -> DoingStuffToGet output

现在，为了处理线程，我们可以构建一些有用的工具来处理和组合 Numbering 操作。要了解我们需要哪些工具，请查看在对组件进行编号后如何组合输出。输出的“事物”部分总是通过将一些未编号的函数(通常是数据构造函数)应用于编号的某些“事物”输出来构建。

为了处理这些函数，我们可以构建一个看起来很像我们的 [] 案例的小工具，其中不需要实际编号。

steady :: thing -> Numbering thing
steady x i = (x, i)

不要因为类型使它看起来好像 steady 只有一个参数而被推迟:记住 Numbering thing 是函数类型的缩写，所以那里确实还有另一个 ->。我们得到

steady [] :: Numbering [a]
steady [] i = ([], i)

就像在 ntsNumber 的第一行。

但是其他构造函数 N 和 (:) 呢？问 ghci 。

> :t steady N
steady N :: Numbering (a -> [NT a] -> NT a)
> :t steady (:)
steady (:) :: Numbering (a -> [a] -> [a])

我们得到以函数为输出的编号操作，我们希望通过更多的编号操作来生成这些函数的参数，从而产生一个大的整体编号操作，其中的数字是线程化的。该过程的一个步骤是为编号生成的函数提供一个编号生成的输入。我将其定义为中缀运算符。

($$) :: Numbering (a -> b) -> Numbering a -> Numbering b
infixl 2 $$

与显式应用运算符的类型比较， $

> :t ($)
($) :: (a -> b) -> a -> b

这个 $$ 运算符是“编号应用程序”。如果我们做对了，我们的代码就会变成

ntNumber  :: NT a -> Numbering (NT (a, Int))
ntNumber  (N a ants)   i = (steady N $$ aNumber a $$ ntsNumber ants) i

ntsNumber :: [NT a] -> Numbering [NT (a, Int)]
ntsNumber []           i = steady [] i
ntsNumber (ant : ants) i = (steady (:) $$ ntNumber ant $$ ntsNumber ants) i

与 aNumber 原样(目前)。这段代码只是进行数据重建，将构造函数和组件的编号过程插入在一起。我们最好给出 $$ 的定义并确保它得到正确的线程。

($$) :: Numbering (a -> b) -> Numbering a -> Numbering b
(fn $$ an) i0 = (f a, i2) where
  (f, i1) = fn i0
  (a, i2) = an i1

在这里，我们的旧线程模式完成一次。 fn和 an都是一个函数，需要一个起始编号，整个 fn $$ sn都是一个函数，得到起始编号 i0我们遍历数字，首先收集函数，然后是参数。然后我们进行实际应用并交回最终的“下一个”数字。

现在，请注意，在每一行代码中，输入 i 作为编号过程的参数输入。我们可以通过只讨论过程而不是数字来简化此代码。

ntNumber  :: NT a -> Numbering (NT (a, Int))
ntNumber  (N a ants)   = steady N $$ aNumber a $$ ntsNumber ants

ntsNumber :: [NT a] -> Numbering [NT (a, Int)]
ntsNumber []           = steady []
ntsNumber (ant : ants) = steady (:) $$ ntNumber ant $$ ntsNumber ants

阅读此代码的一种方法是过滤掉所有 Numbering 、 steady 和 $$ 用途。

ntNumber  :: NT a -> ......... (NT (a, Int))
ntNumber  (N a ants)   = ...... N .. (aNumber a) .. (ntsNumber ants)

ntsNumber :: [NT a] -> ......... [NT (a, Int)]
ntsNumber []           = ...... []
ntsNumber (ant : ants) = ...... (:) .. (ntNumber ant) .. (ntsNumber ants)

你会看到它看起来像一个预序遍历，在处理完元素后重建原始数据结构。我们正在对这些值做正确的事情，前提是 steady 和 $$ 正确地组合了这些过程。

我们可以尝试对 aNumber 做同样的事情

aNumber  :: a -> Numbering a
aNumber a = steady (,) $$ steady a $$ ????

但是 ???? 是我们实际需要的数字。我们可以建立一个适合那个洞的编号过程:一个发出下一个数字的编号过程。

next :: Numbering Int
next i = (i, i + 1)

这就是编号的本质，“事物”输出的是现在要使用的数字(即起始数字)，“下一个”数字输出是后面的数字。我们可能会写

aNumber a = steady (,) $$ steady a $$ next

这简化为

aNumber a = steady ((,) a) $$ next

在我们的过滤 View 中，那是

aNumber a = ...... ((,) a) .. next

我们所做的是将“编号过程”的概念封装起来，并且我们已经构建了正确的工具来对这些过程进行普通的函数式编程。线程模式变成了 steady 和 $$ 的定义。

编号并不是唯一以这种方式工作的东西。试试这个...

> :info Applicative
class Functor f => Applicative (f :: * -> *) where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

......你还会得到更多的东西。我只想提请注意 pure 和 <*> 的类型。它们很像 steady 和 $$ ，但它们不仅仅是 Numbering 。 Applicative 是每种以这种方式工作的进程的类型类。我不是说“现在学习 Applicative!”，只是建议一个旅行方向。

第三次尝试:类型导向编号

到目前为止，我们的解决方案是针对一个特定的数据结构 NT a ，其中 [NT a] 显示为辅助概念，因为它用于 NT a 。如果我们一次专注于类型的一个层，我们可以使整个事情变得更加即插即用。我们根据编号树定义了对树的列表进行编号。一般来说，如果我们知道如何为每一项物品编号，我们就知道如何为一系列物品编号。

如果我们知道如何对 a 进行编号以获得 b ，我们应该能够对 a 的列表进行编号以获得 b 的列表。我们可以抽象出“如何处理每个项目”。

listNumber :: (a -> Numbering b) -> [a] -> Numbering [b]
listNumber na []       = steady []
listNumber na (a : as) = steady (:) $$ na a $$ listNumber na as

现在我们旧的树列表编号函数变成了

ntsNumber :: [NT a] -> Numbering [NT (a, Int)]
ntsNumber = listNumber ntNumber

这几乎不值得命名。我们可以写

ntNumber :: NT a -> Numbering (NT (a, Int))
ntNumber (N a ants) = steady N $$ aNumber a $$ listNumber ntNumber ants

我们可以为树木本身玩同样的游戏。如果你知道如何给东西编号，你就知道如何给一棵东西树编号。

ntNumber' :: (a -> Numbering b) -> NT a -> Numbering (NT b)
ntNumber' na (N a ants) = steady N $$ na a $$ listNumber (ntNumber' na) ants

现在我们可以做这样的事情

myTree :: NT [String]
myTree = N ["a", "b", "c"] [N ["d", "e"] [], N ["f"] []]

> ntNumber' (listNumber aNumber) myTree 0
(N [("a",0),("b",1),("c",2)] [N [("d",3),("e",4)] [],N [("f",5)] []],6)

在这里，节点数据现在本身就是一个事物列表，但我们已经能够单独为这些事物编号。我们的设备适应性更强，因为每个组件都与该类型的一层对齐。

现在，试试这个:

> :t traverse
traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)

这与我们刚刚做的事情非常相似，其中 f 是 Numbering 并且 t 有时是列表，有时是树。
Traversable 类捕捉成为类型形成器意味着什么，它允许您通过存储的元素线程化某种进程。同样，您使用的模式非常普遍，并且是预料之中的。学习使用 traverse 可以节省大量工作。

最终...

...您将了解到库中已经存在完成 Numbering 的工作:它被称为 State Int，它属于 Monad 类，这意味着它也必须在 0.1323113 类中为了掌握它，

import Control.Monad.State

启动一个有状态进程的操作，就像我们输入的 Applicative 一样，是这样的:

> :t evalState
evalState :: State s a -> s -> a

我们的 0 操作变成了

next' :: State Int Int
next' = get <* modify (1+)

其中 next 是访问状态的进程， get 是一个改变状态的进程， modify 的意思是“但也做”。

如果您使用语言扩展 pragma 启动文件

{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}

你可以像这样声明你的数据类型

data NT a = N a [NT a] deriving (Show, Functor, Foldable, Traversable)

Haskell 会为你写 <*。

你的程序然后变成一行......

evalState (traverse (\ a -> pure ((,) a) <*> get <* modify (1+)) ntree) 0
--                  ^ how to process one element ^^^^^^^^^^^^^^^
--         ^ how to process an entire tree of elements ^^^^^^^^^
--        ^ processing your particular tree ^^^^^^^^^^^^^^^^^^^^^^^^^^^
-- ^ kicking off the process with a starting number of 0 ^^^^^^^^^^^^^^^^

...但到那一行的旅程涉及许多“装瓶模式”的步骤，这需要一些(希望有所返回)学习。