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在折叠时用于mappend？因为默认情况下,树中的数字只是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在该树上定义了a ,这样:foldMap :: Monoid m => (a -> m) -> Tree a -> m.因此,这意味着结果类型(以及传递给函数的结果foldMap)m必须是a Monoid.

Haskell是静态类型的:在编译之后,Haskell确切地知道在每个函数实例中传递的类型.这意味着它知道输出类型将是什么,以及如何处理它.

现在Int不是一个实例Monoid.你在这里使用F.foldl (+) 0 testTree,这意味着你或多或少地构建了一个"临时"幺半群.如果我们查看以下源代码,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那就是在使用foldMapIS 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,如果我们看到a 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也可以是树的组合(因为这些是递归调用).在a的情况下Leaf,我们什么都不做(我们返回id,但是a上的组合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

因此,我们已经构建了某种含半幺群,其中mappend被替换f,并mempty作为无操作(身份功能).

Answer 2

它不需要.foldl被翻译成foldr其转化为foldMap过Endo这意味着功能组合物,这意味着功能的简单嵌套您所提供.

或者其他的东西.这意味着,foldl可以转化成foldMap在Dual . Endo其组成由左到右,等等.

更新:是的,文档说:

可折叠的实例预计将满足以下法律:

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

或等效物(此处,为(+)案例显示),应用于用户提供的值 - 在您的情况下,

                                                 0

需要注意的另一件事是,Endo并且Dual是newtypes,因此所有这些诡计都将由编译器完成,并且在运行时间之后就消失了.