這是Haskell類型推斷的行動，還是別的？

Question

我正在通過在線LYAH書（該鏈接將直接轉到我的問題所關注的部分）。

的作者定義的二進制樹的數據類型，並且示出了它如何可製成型摺疊（在Data.Foldable定義）的一個實例，通過實施foldMap功能：

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操作（如果我的術語是正確的）？

（我自己的答案嘗試：筆者本節之前的幾段描述民類型如何，可以解釋爲兩種不同的方式含半幺羣類型;通過包裝他們進入總和和產品型與（+）和（*）作爲mappend功能和在0和1作爲mempty元件，分別是「A」中（樹一個）以某種方式被推斷爲屬於​​的類型到總和類型（哈斯克的方式埃爾根據上下文不同地解釋數值）還是完全不同？ ]

Answer 1

我的問題是，如何哈斯克爾弄清楚，除了在整型 - 查詢哈斯克爾爲testTree的類型給出了樹[整數] - 可被視爲幺半羣手術（如果我的術語是正確的）？

它不能！實際上，Integer沒有Monoid實例。

現在，不要誤解我的意思 - 整數是下的一個monoid。然而，它們也是乘法運算下的幺半羣，Haskell無法知道要使用哪一個，因此包裝器也是如此。

但...沒有一個是這裏發生的事情。繼續前進......

（我自己的答案嘗試：筆者本節之前的幾段描述的Num類型如何被解釋爲以兩種不同的方式一個Monoid類型;通過包裝他們進入總和Product類型，其中（+）和（*）分別作爲mappend函數，0和1分別作爲mempty元素。（Tree a）中的「a」類型被推斷爲屬於​​Sum類型根據上下文根據的論點，你哈斯克爾不同解釋數值）或者是別的東西完全？]

不是一個糟糕的猜測，但那種推理（發現使用Sum實例給出）超出了Haskell可以爲你做的。

這裏有兩個關鍵點 - 首先，Monoid約束僅用於某些功能，而不是一般的摺疊。特別是，foldl實際上並不需要Monoid實例，因爲您提供二進制操作和初始值供其使用。

第二點是我懷疑你真的以後 - 它是如何創建一個通用的foldl不需要Monoid，當你定義的全部是foldMap，哪一個呢？要回答這個問題，我們可以簡單look at the default implementation的foldl：

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

這裏，Endo is another newtype wrapper，專門爲使構圖的Monoid，與id爲標識功能a -> a，而Dual is a wrapper從而推翻一個Monoid的方向。所以它實際上在這裏使用的Monoid可以將(+)與功能組合一起使用，然後將結果應用到種子值。

Answer 2

monoid在這裏沒有實際使用。最後一行使用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來選擇Sum或Product。爲此，我們可以使用F.foldMap（簽名(F.Foldable t, Monoid m) => (a -> m) -> t a -> m）：

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