我是 Haskell 的初学者,正在从“Learn You a Haskell”学习。
我不明白 Foldable
的 Tree
实现。
instance F.Foldable Tree where
foldMap f Empty = mempty
foldMap f (Node x l r) = F.foldMap f l `mappend`
f x `mappend`
F.foldMap f r
引用 LYAH 的话:“因此,如果我们只为某种类型实现 foldMap
, 我们会得到 foldr
和 foldl
免费使用该类型!”。
有人能解释一下吗?我不明白现在如何以及为何免费获得 foldr
和 foldl
...
最佳答案
我们从 foldMap
的类型开始:
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldMap
的工作原理是将 a -> m
函数映射到数据结构上,然后运行它,使用 mappend< 将元素粉碎为单个累积值
.
接下来,我们注意到,给定某种类型 b
,b -> b
函数形成一个幺半群,其中 (.)
为它的二元运算(即 mappend
)和 id
作为标识元素(即 mempty
)。如果您还没有遇到过它,id
定义为id x = x
)。如果我们将 foldMap
专门用于该幺半群,我们将得到以下类型:
foldEndo :: Foldable t => (a -> (b -> b)) -> t a -> (b -> b)
(我将函数命名为foldEndo
,因为内函数是从一种类型到同一类型的函数。)
现在,如果我们查看列表的签名foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
我们可以看到 foldEndo
与它匹配,除了对任何 Foldable
的泛化以及对参数的一些重新排序。
在我们开始实现之前,有一个技术复杂性,即 b -> b
无法直接成为 Monoid
的实例。为了解决这个问题,我们使用 Data.Monoid
中的 Endo
新类型包装器:
newtype Endo a = Endo { appEndo :: a -> a }
instance Monoid (Endo a) where
mempty = Endo id
Endo f `mappend` Endo g = Endo (f . g)
根据Endo
编写,foldEndo
只是专门的foldMap
:
foldEndo :: Foldable t => (a -> Endo b) -> t a -> Endo b
因此我们将直接跳转到foldr
,并根据foldMap
定义它。
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z
这是默认定义you can find in Data.Foldable
。最棘手的部分可能是 Endo 。 f
;如果您对此有困难,请不要将 f
视为二元运算符,而是将其视为类型为 a -> (b -> b)
的一个参数的函数;然后我们用 Endo
包装生成的内函数。
对于foldl
,推导本质上是相同的,除了我们使用不同的内函数幺半群,以flip (.)
作为二元运算(即我们以相反的方向组合函数)。
关于haskell - Tree 实现 Foldable FoldMap 时 Foldr/Foldl 是免费的吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23319683/