Haskell 中的幺半群和 Num

Question

过去几个月我一直在学习Haskell，我遇到了一个令我困惑的幺半群的例子。

给出这些定义：

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 如何知道在折叠时将哪个 Monoid 用于 mappend？因为默认情况下，树中的数字只是 Num 类型，我们从未明确说明它们是 Sum 或 Product 等 Monoid 的位置。

那么 GHCi 如何推断出正确的 Monoid 来使用呢？还是我现在完全不在了？

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

Answer 1

不需要。 foldl 翻译成 foldr 翻译成 foldMap over Endo 这意味着函数组合，这意味着函数的简单嵌套 您提供的.

或者什么的。意思是，foldl 可以翻译成 foldMap 而不是 Dual . Endo，后者构成从左到右等等。

更新： 是的，the docs says：

Foldable instances are expected to satisfy the following laws:

foldr f z t = appEndo (foldMap (Endo . f) t ) z
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z  -- << --
fold = foldMap id

Dual (Endo f) <> Dual (Endo g) = Dual (Endo g <> Endo f) = Dual (Endo (g . f))。因此，当 appEndo 发生时，已构建的函数链，即

    ((+10) . (+9) . (+8) . (+5) . ... . (+1))

或等效项（此处显示的是 (+) 情况）应用于用户提供的值——在您的情况下，

另一件需要注意的事情是 Endo 和 Dual 是 newtype，所以所有这些阴谋都将由编译器完成，并在运行时间消失.

Answer 2

存在（隐式地，如果不是显式地）形式为 a -> a 的普通函数的幺半群实例，其中 mappend 对应于函数组合，而 mempty 对应于id 函数。

什么是(+)？它是一个函数 (Num a) => a -> a -> a。如果你 foldMap 用 + 覆盖你的可折叠数字，你将每个数字都变成部分应用的 (+ <some number)，即 a -> a。瞧，您发现了魔法 f 可以将折叠式设备中的所有东西变成幺半群！

假设函数有一个直接的幺半群实例，你可以这样做：

foldMap (+) [1, 2, 3, 4]

，这将产生最终的 (Num a) => a -> a，您可以将其应用于 0 以获得 10。

但是没有这样的直接实例，所以你需要使用内置的 newtype 包装器 Endo 和相应的解包器 appEndo，它们为 a -> a 实现了 monoid职能。这是它的样子：

Prelude Data.Monoid> (appEndo (foldMap (Endo . (+)) [1, 2, 3, 4])) 0
10

这里 Endo . 只是我们恼人的需求，需要提升普通的 a -> as 以便它们具有自然的 Monoid 实例。在 foldMap 通过将所有内容变成 a -> a 并将它们与组合链接在一起来完成减少我们的可折叠之后，我们使用 appEndo 提取最终的 a -> a，最后将其应用于0.

Answer 3

简答：这是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 确切地知道每个函数 instance 传入和传出的类型。所以这意味着它知道例如输出类型是什么，以及如何处理它。

现在 Int 不是 Monoid 的实例。你在这里使用 F.foldl (+) 0 testTree，那么这意味着你或多或少地构造了一个 "ad hoc" 幺半群。如果我们查看 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）。

所以这里发生的是 foldMap 中使用的 mempty 是 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（一片叶子），我们将 return mempty，如果我们看到Node x l r，我们将执行如上所述的mappend。所以“specialized”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 的情况下，我们什么也不做（我们 return 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)) 的结果。但是现在我们需要 post 处理这个结果。使用 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 和 "initial" 值。所以这意味着我们将处理以 z（初始元素）开始的链，并将其应用为：

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

所以我们构造了某种类幺半群，其中 mappend 被 f 替换，mempty 作为空操作（恒等函数）。

Haskell 中的幺半群和 Num

Monoids and Num in Haskell

haskell

monoids