haskell - 没有 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

您将看到它有一个未绑定(bind)类型m。通常，当发生这种情况时，意味着 m 可以是任何东西，但这里它也用 Monoid m 约束 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 类中的函数或其派生类，因此它是类型反射(reflect)了这一点。 expr 最常见的类型是

expr :: Monoid m => m -> m

这里，m 是一个自由类型变量，被限制为some Monoid。

<小时/>

foldMap 允许您使用 Monoid 函数的原因是它明确限制了其类型签名中的 m 可以执行的操作类型。 。通过在那里施加限制，我们获得了更多的权力来操纵它们。