9

我在 Haskell 上一门课，我们需要为定义的树定义折叠操作：

data Tree a = Lf a | Br (Tree a) (Tree a)

我似乎找不到任何关于“tfold”操作的信息或它应该做什么。任何帮助将不胜感激。

4

4 回答 4

11

我一直认为折叠是一种用其他函数系统地替换构造函数的方式。因此，例如，如果您有一个自己动手的List类型（定义为data List a = Nil | Cons a (List a)），则相应的折叠可以写成：

listfold nil cons Nil = nil
listfold nil cons (Cons a b) = cons a (listfold nil cons b)

或者，也许更简洁，如：

listfold nil cons = go where
    go Nil = nil
    go (Cons a b) = cons a (go b)

的类型listfold是b -> (a -> b -> b) -> List a -> b。也就是说，它需要两个“替换构造函数”；一个告诉如何将一个Nil值转换为 a b，另一个是构造函数的替换构造Cons函数，告诉构造函数的第一个值Cons（类型a）应该如何与类型的值组合b（为什么b？因为折叠已经被递归应用了！ ) 产生一个新b的 ，最后是 aList a将整个 she-bang 应用到 - 结果为b。

在你的情况下，类型tfold应该是(a -> b) -> (b -> b -> b) -> Tree a -> b类似的推理；希望你能从那里拿走它！

于 2012-02-21T09:44:00.800 回答
3

想象一下，您定义一棵树应该以下列方式显示，

<1 # <<2#3> # <4#5>>>

折叠这样的树意味着用实际提供的操作替换每个分支节点，该操作要对数据类型的组成部分（这里是节点的两个子节点，它们本身就是一棵树）递归执行的折叠结果执行，例如,+产生

(1 + ((2+3) + (4+5)))

因此，对于叶子，您应该只取其中的值，对于分支，递归地为两个子节点中的每一个应用折叠，并将两个结果与提供的函数组合，即折叠树的函数。（编辑：）当从叶子中“获取”值时，您可以另外转换它们，应用一元函数。因此，一般来说，您的折叠将需要两个用户提供的函数，一个用于叶子，Lf另一个用于组合递归折叠分支节点的树状成分（即分支）的结果，。Br

您的树数据类型可能有不同的定义，例如可能是空的叶子，并且内部节点也携带值。然后你必须提供一个默认值来代替空的叶子节点，以及一个三向组合操作。您仍然可以通过与数据类型定义的两种情况相对应的两个函数定义折叠。

这里要实现的另一个区别是，你折叠什么，以及你如何折叠它。即你可以以线性方式折叠你的树，或者你可以以类似树的(1+(2+(3+(4+5)))) == ((1+) . (2+) . (3+) . (4+) . (5+)) 0方式折叠一个线性列表，。这完全取决于您如何为生成的“表达式”加上括号。当然，在折叠表达式的经典结构中，表达式的结构遵循被折叠的数据结构的结构；但变化确实存在。另请注意，组合操作可能并不严格，它使用/产生的“结果”类型可能表示复合（列表等）以及原子（数字等）值。((1+2)+((3+4)+5)) == (((1+2)+(3+4))+5)

（2019-01-26 更新）如果组合操作是关联的，那么这种重新括号是可能的，例如+: 。一种数据类型连同这种关联操作和一个“零”元素（(a1+a2)+a3 == a1+(a2+a3)a+0 == 0+a == aFoldable

于 2012-02-21T21:45:30.713 回答
1

列表上的折叠是将列表缩减为单个元素。它接受一个函数，然后将该函数应用于元素，一次两个，直到它只有一个元素。例如：

Prelude> foldl1 (+) [3,5,6,7]
21

...通过一对一的操作找到：

3 + 5 == 8
8 + 6 == 14
14 + 7 == 21

可以写一个折叠

ourFold :: (a -> a -> a) -> [a] -> a
ourFold _         [a]        = a -- pattern-match for a single-element list. Our work is done.
ourFold aFunction (x0:x1:xs) = ourFold aFunction ((aFunction x0 x1):xs)

树折叠可以做到这一点，但会向上或向下移动树枝。为此，它首先需要进行模式匹配以查看您是在叶子上还是在分支上进行操作。

treeFold _ (Lf a)   = Lf a -- You can't do much to a one-leaf tree
treeFold f (Br a b) = -- ...

剩下的就交给你了，因为这是家庭作业。如果您遇到困难，请尝试首先考虑类型应该是什么。

于 2012-02-21T03:50:03.483 回答
1

折叠是一种使用操作将数据结构“压缩”成单个值的操作。取决于您是否有起始值和执行顺序（例如，对于您有foldl、和的列表），会有一些变化foldr，因此正确的实现取决于您的分配。foldl1foldr1

我猜你tfold应该简单地用它的值替换所有叶子，并用给定操作的应用程序替换所有分支。画一个带有一些数字的示例树，给他一个“折叠”的操作，如(+). 在此之后，应该很容易编写一个执行相同操作的函数。

于 2012-02-21T08:35:28.223 回答