树折操作？

Question

我正在Haskell中学习一个类,我们需要为以下定义的树定义折叠操作:

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

我似乎无法找到关于"tfold"操作的任何信息,或者它真的应该做什么.任何帮助将不胜感激.

Answer 1

我总是认为折叠是一种通过其他函数系统地替换构造函数的方法.因此,例如,如果您有自己动手的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值转换为b构造函数的另一个替换构造Cons函数,告诉Cons构造函数(类型a)的第一个值应该如何与类型值组合b(为什么b？因为折叠已经递归应用了! )产生一个新的b,最后一个List a应用整个she-bang - 结果b.

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

Answer 2

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

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

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