没有Monoid实例的折叠

Question

我有一个简单的树结构:

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

还有一个可折叠的实现:

import qualified Data.Foldable as F

instance F.Foldable Tree where
  foldMap f Leaf         = mempty
  foldMap f (Node x l r) = F.foldMap f l `mappend`
                           f x           `mappend`
                           F.foldMap f r

和它的作品,即使有对没有实现Monoid,我不能既不使用mappend也不mempty在我的代码.那么这个Foldable实现如何工作？

Answer 1

如果检查类型 foldMap

class Foldable f where
  foldMap :: Monoid m => (a -> m) -> f a -> m

你会看到它有一个未绑定的类型m.通常,当这种情况发生时则表示m可能是任何东西,但在这里它也限制m使用Monoid m.那Monoid就是来自.

值得注意的是,如果我们没有Monoid实例,那么定义一个返回"可能是任何东西"的值的函数就很难了.如果你尝试它,你会发现它几乎是不可能的(没有"作弊").

impossible :: Int -> b -- no constraints on `b` at all!
impossible i = ...?

但如果我们对这种类型有所了解,那就很容易了

veryPossible  :: Num b => Int -> b
veryPossible  i = fromIntegral i
-- or
veryPossible2 i = fromIntegral (i * i) + fromIntegral i

作为另一个例子,考虑表达式的类型

expr m = mconcat [m <> m <> mempty, mempty <> m]

因为这个表达式是基于一些未知值构建的,m并且只使用Monoid类中的函数或它们的派生类,所以它的类型反映了这一点.最一般的类型expr是

expr :: Monoid m => m -> m

在这里,m一个自由类型变量被约束为一些 Monoid.

foldMap让你使用Monoid函数的原因是因为它明确地约束了m它的类型签名可以是的东西.通过设置约束,我们可以获得更多操纵它们的能力.