haskell - 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

外部资源
我认为 Foldable and Traversable by A. Arnold是一篇关于 Foldable 的不错的博文(和 Traversable )一般 - 也许你觉得它也有帮助