2

以下是 Learn You a Haskell 中的一些示例：

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  

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

测试它：

> let z = F.foldMap (+) testTree
> :t F.foldMap
F.foldMap :: (Monoid m, F.Foldable t) => (a -> m) -> t a -> m
> :t (+)
(+) :: Num a => a -> a -> a
> :t z
z :: (Monoid a, Num a) => a -> a

of的第一个参数F.foldable是一个返回Monoid的函数，但是Num不是Monoid的子类，所以(+)在这里肯定是不合格的吧？但从测试来看，它似乎很合适。

这里z有点神秘，它应该是一个 Monoid，但具体是什么？

4

2 回答 2

2

"Num a =>" 是一个类型类约束，它表示 (+) 的参数和结果必须至少是类型类 "Num" 的成员，但它们也可以是任何其他类型类的完美成员（在这种情况下，单体）。

关于 z，有几个标准类型可以满足这些约束（同时是 Num 和 Monoid 的一部分）。它们是在 Data.Monoid 中定义的 Sum 和 Product。

要回答您的问题，Sum 或 Product 的树将通过类型检查并工作，您定义为类型类 Num 和 Monoid 的一部分的任何其他类型也将如此。

于 2015-03-29T22:05:27.880 回答
1

所以让我们弄清楚这里发生了什么。我们有这两种我们应该统一的类型：

Num a => a -> a -> a
Monoid m => b -> m

这可以通过设置b ~ aand来完成m ~ a -> a，导致

(Num a, Monoid (a -> a)) => a -> a -> a

此外，还有一个用于函数的 monoid 实例：

instance Monoid b => Monoid (a -> b) where
    mempty = \_ -> mempty
    mappend f g = \x -> f x `mappend` g x

（让我们暂时搁置为什么这个实例有用。）这意味着，事实上，为了满足Monoid (a -> a)约束，我们只需要确保返回类型————a是一个幺半群，因此我们现在得到这个类型(+)：

(Num a, Monoid a) => a -> a -> a

这种类型用于foldMap (+)：

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

这样做的行为是遍历树，（部分）应用于(+)树的每个元素，然后用于mappend组合所有结果。因此，小示例树Node 3 (Node 1 Empty Empty) (Node 6 Empty Empty)将产生如下结果：

(mempty `mappend` (+) 1 `mappend` mempty) `mappend`
(+) 3                                     `mappend`
(mempty `mappend` (+) 6 `mappend` mempty)

为了紧凑，让我们把它写成mconcat [(1+), (3+), (6+)]，尽管这有点捏造东西。在更大的示例树上运行foldMap (+)将是mconcat [(1+), (3+), (6+), (5+), (8+), (9+), (10+)].

现在，计算出函数上的 monoid 实例所说的内容，我们发现mconcat [f,g,h] = \x -> mconcat [f x, g x, h x]，等等，还有更多函数。所以foldMap (+) testTree出来

\n -> mconcat [1+n, 3+n, 6+n, 5+n, 8+n, 9+n, 10+n]

可能您期望foldMap (+) testTree出现类似的东西1+3+6+5+8+9+10；希望您能看到实际结果与您的期望（以及为什么）大不相同。

如果我们想要做的是将树的所有元素相加，我们实际上可以偶然完成这项工作。我们可以专门选择Sum幺半群并选择n为0：所以，例如

getSum $ foldMap (+) testTree 0
= { by our computations above }
getSum $ (\n -> mconcat [1+n, 3+n, 6+n, 5+n, 8+n, 9+n, 10+n]) 0
= { beta reduction }
getSum $ mconcat [1+0, 3+0, 6+0, 5+0, 8+0, 9+0, 10+0]
= { n+0 = n }
getSum $ mconcat [1, 3, 6, 5, 8, 9, 10]
= { definition of mconcat for Sum }
getSum $ sum [1, 3, 6, 5, 8, 9, 10]
= { playing fast and loose with polymorphic literals }
sum [1, 3, 6, 5, 8, 9, 10]

这是获取树中元素总和的一种非常复杂的方法。但希望这能解释为什么你写的不仅仅是一个类型错误。是什么意思z；以及为什么它既Num不是子类也不是超类并不重要Monoid。

于 2015-03-29T22:58:59.313 回答