这个Haskell类型的推理是在行动还是其他什么？

Question

我正在阅读在线LYAH书(该链接将直接带您到我的问题所涉及的部分).

作者定义了二叉树数据类型,并展示了如何通过实现foldMap函数将其作为Foldable类型的实例(在Data.Foldable中定义):

import Data.Monoid
import qualified Data.Foldable as F

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 

foldMap的类型声明如下:

F.foldMap :: (Monoid m, F.Foldable t) => (a -> m) -> t a -> m

所以它需要一个函数,它接受一个类型为"a"的实例并返回一个monoid.

现在作为示例,作者创建一个Tree实例

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

并执行以下折叠(为可折叠类型定义):

F.foldl (+) 0 testTree -- the answer is 42 (sum of the Node Integers)

我的问题是,Haskell如何计算出Integer类型的添加 - 查询Haskell的testTree类型给出Tree [Integer] - 可以被视为一个monoid操作(如果我的术语是正确的)？

(我自己尝试回答:作者在本节前几段描述了如何将Num类型以两种不同的方式解释为Monoid类型;通过(+)和(*)将它们包装到Sum和Product类型中作为mappend函数,0和1分别作为mempty元素.(树 a)中的"a"的类型以某种方式被推断为属于Sum类型(Haskell根据上下文不同地解释数值的方式)或它完全是另一回事吗？]

Answer 1

我的问题是,Haskell如何计算出Integer类型的添加 - 查询Haskell的testTree类型给出Tree [Integer] - 可以被视为一个monoid操作(如果我的术语是正确的)？

它不能!事实上,没有Monoid实例Integer.

现在,不要误解我的意思 - 整数是一个幺半群.然而,它们在乘法中也是一个幺半群,并且Haskell无法知道使用哪个,因此newtype包装器.

但是......这一切都不会发生在这里.继续...

(我自己尝试回答:作者在本节前几段描述了如何将Num类型以两种不同的方式解释为Monoid类型;通过(+)和(*)将它们包装到Sum和Product类型中作为mappend函数,0和1分别作为mempty元素.(树a)中的"a"的类型以某种方式被推断为属于​​Sum类型(Haskell根据上下文不同地解释数值的方式)或它完全是另一回事吗？]

不错的猜测,但是那种推断(Sum根据你给出的参数找到实例)超出了Haskell可以为你做的事情.

这里有两个关键点 - 首先,Monoid约束仅用于某些功能,而不是一般的折叠.特别是,foldl实际上根本不需要Monoid实例,因为您提供二进制操作和初始值供它使用.

第二点是我怀疑你真正追求的 - 它是如何创建一个foldl不需要a 的泛型Monoid,当你定义的是什么时foldMap,它是什么？要回答这个问题,我们可以简单地看一下默认实现的foldl:

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

这里Endo是另一个newtype包装器,特别是对于a -> a赋予Monoid组合的函数,id作为标识,同时Dual是一个反转a的方向的包装器Monoid.所以Monoid它实际上在这里使用的是它可以粘合使用(+)与函数组合,然后将结果应用于种子值.

Answer 2

幺半群在这里实际上并没有使用.最后一行是使用F.foldl哪个有签名F.Foldable t => (a -> b -> a) -> a -> t b -> a.基本上你通过提供(+)和0来'手动'使用一个monoid.

如果你想使用'隐式'的monoid,你可以使用F.fold(有签名(F.Foldable t, Monoid m) -> t m -> m).在这种情况下,如果你尝试它,你会得到:

*Main> F.fold testTree

<interactive>:1:1:
    No instance for (Monoid Integer)
      arising from a use of `F.fold'
    Possible fix: add an instance declaration for (Monoid Integer)
    In the expression: F.fold testTree
    In an equation for `it': it = F.fold testTree
*Main> :t F.foldl

现在,GHCI抱怨说Integer没有Monoid实例.您必须通过包装整数来选择Sum或Product.为此,我们可以使用F.foldMap(签名(F.Foldable t, Monoid m) => (a -> m) -> t a -> m):

*Main> F.foldMap Sum testTree
Sum {getSum = 42}