在 Haskell 中实现可折叠

Implementation of Foldable in Haskell

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

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

比如我实现了树的遍历:

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

效果不错。但是我想实现 Foldable 接口。

我想,我应该写这样的东西:

instance Foldable Tree where
  foldr = treeFoldt

但是不行。我该如何解决这个问题?

我可以尝试告诉您代码的问题出在哪里,但遗憾的是您没有给出 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)的一个很好的博客 post 总的来说 - 也许您也觉得它有帮助