在Haskell中编写foldMap

Question

我正在尝试编写自己的foldMap函数作为学习Haskell的例外

目前它看起来像这样

class Functor f => Foldable f where
    fold    :: Monoid m =>             f m -> m
    foldMap :: Monoid m => (a -> m) -> f a -> m
    foldMap g a = fold (<>) mempty (fmap g a)

但是在编译时会出现以下错误

Could not deduce (Monoid ((f m -> m) -> fm -> m)) arising from use of 'fold'
from the context (Foldable f) bound by the class declaration for 'Foldable' at (file location)
or from (Monoid m) bound by the type signature for foldMap :: Monoid m => (a -> m) -> f a -> m at (file location
In the expression fold (<>) mempty (fmap g a)
In an equation for 'foldMap':
     foldMap g a = fold (<>) mempty (fmap g a)

我无法弄清楚编译器试图用这个错误告诉我什么,有人能告诉我我的foldMap出了什么问题吗？

Answer 1

也许我们应该用实际的解决方案来回答:

我希望现在很清楚,这是一个可能的定义:

class Functor f => Foldable f where
    fold    :: Monoid m =>             f m -> m
    foldMap :: Monoid m => (a -> m) -> f a -> m
    foldMap g a = fold $ fmap g a

按照类型

安德鲁和李已经给了你一个高级别的解释,但也许我可以给你另一个观点:

让我们按照类型来寻找这个答案:

我们想要一个函数f a -> m,其中m是一个monoid并且f是一个函子.另外我们有一个函数g :: a -> m可以用来从一些a变成monoid - 很好.

现在我们得到一些额外的功能:

• fold :: f m -> m 来自我们自己的班级
• fmap :: (a -> b) -> f a -> f b 来自Functor f

好了,我们需要f a -> m现在如果只是a将是一个m那么我们就可以用fold...宕.

但是等一下:我们可以a成为一个m使用g- 但是a被包装成f... dang.

哦等等:我们可以f a成为一个f m使用fmap.... ding-ding-ding

所以我们这样做:

• 制作f a成f m:fmap g a
• 使用折叠: fold (fmap g a)

或使用$:

foldMap g a = fold $ fmap g a

例

让我们得到一些东西,我们可以尝试:

module Foldable where

import Data.Monoid

class Functor f => Foldable f where
    fold    :: Monoid m => f m -> m
    foldMap :: Monoid m => (a -> m) -> f a -> m
    foldMap g a = fold $ fmap g a

instance Foldable [] where
  fold []     = mempty
  fold (x:xs) = mappend x (fold xs)

这是一个简单的例子,使用Sum和[1..4]:

?> foldMap Sum [1..4]
Sum {getSum = 10}

这对我来说似乎很好.