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是如何知道在地图折叠时使用什么Monoid的？因为在默认情况下，树中的数字只是Num类型，而且我们从来没有明确地表示它们在哪，比如求和或积。

那么，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，这意味着您或多或少已经构造了一个“即席”单样体。如果我们看一下foldl，这是可行的。

(b -> a -> b) -> b -> t a -> b foldl f z t= appEndo (getDual (foldMap )对偶。恩多。( 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)。现在，如果我们检查源代码，我们会看到两件有趣的事情：

实例Monoid (Endo a)，其中instance = Endo id Endo f mappend Endo g= Endo (f )。( g)例子：=>单子(对偶a)，其中m空=对偶m空对偶x mappend对偶y=对偶(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作为非op(恒等函数)。

Answer 2

它不需要。foldl被转换为foldr，这意味着函数组合，这意味着您所提供的函数的简单嵌套。

或者别的什么。意思是，foldl可以被翻译成foldMap over Dual . Endo，它由左向右组成，等等。

更新:是的，医生说

可折叠的实例应符合以下法律： f= appEndo (foldMap )。f) t)foldMap= appEndo (getDual (foldMap (对偶)).恩多。( f) t)z -- << -折叠= foldMap id

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

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

或等效(这里显示为(+)情况)，应用于用户提供的值--在您的情况下，

                                                 0

另一件需要注意的是，Endo和Dual是newtype的，所以所有这些诡计都将由编译器完成，并在运行时消失。

Answer 3

存在(隐式的，如果不是显式的)表单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 -> a的恼人需求，这样它们就有了它们的自然Monoid实例。在foldMap完成后，通过将所有内容转化为a -> a并将它们与组合链接在一起，减少了我们的可折叠性，我们使用appEndo提取了最终的a -> a，并最终将其应用于0。