在Haskell中实现可折叠

Question

例如,我有一些数据类型.让它成为二叉树:

data Tree a = Leaf a | Branch (Tree a) (Tree a)

例如,我实现了树的遍历:

treeFoldt :: Tree t -> [t]
treeFoldt = foldt1 (:) []

它的效果非常好.但我想实现Foldable界面.

我想,我应该这样写:

instance Foldable Tree where
  foldr = treeFoldt

但它不起作用.我怎样才能解决这个问题？

Answer 1

我可以尝试告诉你代码的问题在哪里,但遗憾的是你没有给出定义 foldt1

但这应该工作(如果你的实现treeFoldt是好的 - 记住:[]是一个实例Foldable):

instance Foldable Tree where
  foldr f s = Data.Foldable.foldr f s . treeFoldt

基本定义使用 Monoid

无论如何,我认为在这种情况下最简单的方法是实现这个foldMap部分:

import Data.Foldable
import Data.Monoid

data Tree a = Leaf a | Branch (Tree a) (Tree a)

instance Foldable Tree where
 foldMap f (Leaf a)     = f a
 foldMap f (Branch l r) = foldMap f l `mappend` foldMap f r 

这肯定有效.

示例/用法

?> let t = Branch (Branch (Leaf $ Sum 2) (Leaf $ Sum 4)) (Leaf $ Sum 6)
?> fold t
Sum {getSum = 12}

要么

?> let t = Branch (Branch (Leaf 2) (Leaf 4)) (Leaf 6)
?> foldMap Sum t
Sum {getSum = 12}

当然你根本不需要这个Monoid部分 - 默认的实现工作得很好:

?> Data.Foldable.foldr1 (+) t
12

顺便说一句:很可能并不明显如何foldr1 (+)才能表达,foldMap并且这是一个很好的(高级)练习,试图自己做:D

外部资源

我想通过A.阿诺德可折叠和Traversable的是相当一个不错的博客文章Foldable(和Traversable)一般-也许你会发现它也有帮助