8

我有一个简单的树结构：

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实现是如何工作的呢？

4

1 回答 1

9

如果您检查类型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是一个自由类型变量，被限制为some Monoid。

foldMap允许您使用函数的原因是因为它显式地限制了其类型签名中Monoid的事物类型。m通过在那里设置约束，我们获得了更多的权力来操纵它们。

于 2013-11-08T01:51:47.187 回答