Haskell树结构讲解

Question

我目前正在尝试使用 haskell 中的树编写一个 minimax 算法，用于连接四人游戏，其中轮到 ai 时需要最大树，轮到玩家时需要最小树。我试图找出一般情况下如何使用树结构，例如：创建、写入、读取和遍历，但是互联网没有返回有用的结果，因为我以特定方式声明树

我正在实现的树结构定义如下

data Tree a = Node a [Tree a ]

我了解如何创建一个树变量

t :: Tree Int 
t = Node 0 [Node 1 [], Node 2 []]

但我不知道如何实际使用它或操作或访问节点的值 请提供任何或所有示例和解释

谢谢

Answer 1

要访问树值，您可以使用模式匹配，通常与递归和/或其他库函数一起使用。

例如，让我们对

Tree Int

中的所有值求和。

sumTree :: Tree Int -> Int
sumTree (Node x ts) = x + sum (map sumTree ts)

这里树值被分解为根值

x

和子树列表

ts

。然后

map sumTree ts

递归计算所有子树总和的列表。我们

sum

将整数列表合并为一个，然后我们添加

x

以得出结论。

在此示例中，我们不必提供基本情况，因为当子树列表为空时

map

不执行任何递归调用。

如果您是 Haskell 的新手，我建议您在像 LYAH 这样的教程中学习模式匹配。它是 Haskell 中最重要的技术之一。