haskell - 用 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是幺半群且 f是一个仿函数。此外，我们还有一个函数 g :: a -> m我们可以用来获取一些 a进入幺半群 - 很好。

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

fold :: f m -> m来自我们自己的类(class)

fmap :: (a -> b) -> f a -> f b来自仿函数 f

好的，我们需要 f a -> m现在如果只有 a将是 m那么我们可以使用 fold ……该死。

但是等等:我们可以做一个 a成 m使用 g - 但 a被包装成 f ……该死。

哦等等:我们可以做一个 f a成 f m使用 fmap .... 叮叮叮

所以让我们这样做:

制作 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}

这对我来说似乎很好。