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部分：

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 (+)表示是最不明显的，这是一个不错的（高级）练习，尝试自己完成：D

---

外部资源

[我认为foldMap通常是关于Foldable and Traversable by A. Arnold（和Foldable）的不错的博客文章-也许您也觉得它很有帮助