haskell - Haskell 中的 Monoids 和 Num

Question

过去几个月我一直在学习 Haskell，遇到了一个令我困惑的 Monoids 示例。

鉴于这些定义:

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

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

而这棵树:

testTree = Node 5  
        (Node 3  
            (Node 1 Empty Empty)  
            (Node 6 Empty Empty)  
        )  
        (Node 9  
            (Node 8 Empty Empty)  
            (Node 10 Empty Empty)  
        )  

如果我运行:

ghci> F.foldl (+) 0 testTree  
42  
ghci> F.foldl (*) 1 testTree  
64800  

GHCi 如何知道折叠时 mappend 使用什么 Monoid？因为默认情况下，树中的数字只是 Num 类型，而且我们从未明确说明它们在某些 Monoid 中的位置，例如 Sum 或 Product。

那么 GHCi 如何推断要使用的正确 Monoid 呢？或者我现在完全不在了？

示例来源: http://learnyouahaskell.com/functors-applicative-functors-and-monoids#monoids

Answer 1

简答 : 它是 foldMap 签名中的类型约束.

如果我们查看 Foldable 的源代码(更具体地说 foldMap )，我们看到:

class Foldable (t :: * -> *) where
  ...
  foldMap :: Monoid m => (a -> m) -> t a -> m

这意味着如果我们声明 Tree Foldable 的成员(不是 Tree 有种类 * -> * )，这意味着 foldMap在该树上定义，例如: foldMap :: Monoid m => (a -> m) -> Tree a -> m .因此，这意味着结果类型(以及传递给 foldMap 的函数的结果) m必须是 Monoid .

Haskell 是静态类型的:在编译之后，Haskell 准确地知道传入每个函数实例的类型。这意味着它知道例如输出类型是什么，以及如何处理它。

现在 Int不是 Monoid 的实例.你在这里使用 F.foldl (+) 0 testTree ，所以这意味着您或多或少地构建了一个“临时”幺半群。如果我们查看 source code of foldl ，这将有效。 :

foldl :: (b -> a -> b) -> b -> t a -> b
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

这有很多关于参数 f 的逻辑。 , z和 t .所以让我们先分解一下。

我们先来看看 Dual . Endo . flip f .这是以下简称:

helper = \x -> Dual (Endo (\y -> f y x))

Dual和 Endo是每个构造函数都接受一个参数的类型。所以我们包装 f y x的结果在 Dual (Endo ...)构造函数。

我们将使用它作为 foldMap 的函数.如果我们的 f有类型 a -> b -> a , 那么这个函数的类型为 b -> Dual (Endo a) .所以函数的输出类型传递给 foldMap有输出类型 Dual (Endo a) .现在，如果我们检查源代码，我们会看到两件有趣的事情:

instance Monoid (Endo a) where
        mempty = Endo id
        Endo f `mappend` Endo g = Endo (f . g)

instance Monoid a => Monoid (Dual a) where
        mempty = Dual mempty
        Dual x `mappend` Dual y = Dual (y `mappend` x)

(请注意，它是 y `mappend` x ，而不是 x `mappend` y )。

所以这里发生的是 mempty用于 foldMap是 mempty = Dual mempty = Dual (Endo id) .所以一个 Dual (Endo ...)封装了身份功能。

此外， mappend两个对偶值归结为 Endo 中值的函数组合.所以:

mempty = Dual (Endo id)
mappend (Dual (Endo f)) (Dual (Endo g)) = Dual (Endo (g . f))

所以这意味着如果我们折叠树，以防我们看到 Empty (一片叶子)，我们将返回 mempty ，如果我们看到 Node x l r ，我们将执行 mappend如上所述。所以一个“专业” foldMap看起来像:

-- specialized foldMap
foldMap f Empty = Dual (Endo id)  
foldMap f (Node x l r) =  Dual (Endo (c . b . a))
        where Dual (Endo a) = foldMap f l
              Dual (Endo b) = helper x
              Dual (Endo c) = foldMap f l

所以对于每个 Node我们在节点的子项和项上从右到左进行函数组合。 a和 c也可以是树的组合(因为这些是递归调用)。如果是 Leaf ，我们什么也不做(我们返回 id ，但是 id 上的合成是无操作的)。

所以这意味着如果我们有一棵树:

5
|- 3
|  |- 1
|  `- 6
`- 9
   |- 8
   `- 10

这将产生一个函数:

(Dual (Endo ( (\x -> f x 10) .
              (\x -> f x 9) .
              (\x -> f x 8) .
              (\x -> f x 5) .
              (\x -> f x 6) .
              (\x -> f x 3) .
              (\x -> f x 1)
            )
      )
)

(省略了身份，以使其更清洁)。这是 getDual (foldMap (Dual . Endo . flip f)) 的结果.但是现在我们需要对这个结果进行后期处理。与 getDual ，我们得到包裹在 Dual 中的内容构造函数。所以现在我们有:

Endo ( (\x -> f x 10) .
       (\x -> f x 9) .
       (\x -> f x 8) .
       (\x -> f x 5) .
       (\x -> f x 6) .
       (\x -> f x 3) .
       (\x -> f x 1)
     )

和 appEndo ，我们得到包裹在 Endo中的函数， 所以:

( (\x -> f x 10) .
  (\x -> f x 9) .
  (\x -> f x 8) .
  (\x -> f x 5) .
  (\x -> f x 6) .
  (\x -> f x 3) .
  (\x -> f x 1)
)

然后我们将其应用于 z “初始”值。这意味着我们将处理以 z 开头的链。 (初始元素)，并像这样应用它:

f (f (f (f (f (f (f z 1) 3) 6) 5) 8) 9) 10

所以我们构建了某种 Monoid，其中 mappend替换为 f , 和 mempty作为无操作(身份函数)。