Haskell中的Monoids和Num

Question

在过去的几个月里，我一直在学习Haskell，我遇到了一个Monoid的例子，这让我感到困惑。

根据这些定义：

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  

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

Answer 1

简而言之：它是foldmap签名中的类型约束。

如果我们查看foldable（更具体地说foldmap)的源代码，我们会看到：

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

这意味着，如果我们声明树是foldable的成员（并不是树具有*->*)，这意味着在该树上定义了foldmap，例如:foldmap::Monoid m=>(a->m)->树a->m。因此，这意味着结果类型（以及传递给foldmap)M的函数结果）必须是monoid。

Haskell是静态类型化的：编译后，Haskell确切地知道每个函数实例中传递的类型。例如，这意味着它知道输出类型，以及如何处理它。

现在int不是monoid的实例。这里使用f.foldl(+)0 testtree，这意味着您或多或少构造了一个“ad hoc”monoid。如果我们查看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。远藤。翻转f。这是：

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

dual和endo都是类型，每个构造函数都接受一个参数。因此，我们将f y x的结果包装在dual(Endo…)构造函数中。

我们将此用作foldmap的函数。如果我们的f具有a->b->a类型，那么此函数具有b->Dual(endoa)类型。因此，传递给foldmap的函数的输出类型为dual(endoa)。现在，如果我们检查源代码，我们会看到两件有趣的事情：

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))

-- 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

这意味着如果我们有一棵树：

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))的结果。但是现在我们需要postprocess这个结果。使用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)
     )

( (\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)
)

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