Haskell/Monoids

在本書的早期部分，我們已經對么半群和 Monoid 型別類做了一些間接的提及（最值得注意的是在討論 MonadPlus 時）。這裡我們將對它們進行更詳細的介紹，並展示它們為何有用。

什麼是么半群？

將數字加起來的運算有一些非常基本的性質，我們在將數字加起來的時候甚至不會去想它們。其中之一是結合律：當加三個或多個數字時，我們對這些數字進行分組的方式並不重要。

GHCi> (5 + 6) + 10
21
GHCi> 5 + (6 + 10)
21

另一個是它有一個單位元，可以將它加到任何其他數字上而不改變它的值。這個元素是數字零。

GHCi> 255 + 0
255
GHCi> 0 + 255
255

加法並不是唯一一個滿足結合律且具有單位元的二元運算。乘法也滿足，儘管其單位元不同。

GHCi> (5 * 6) * 10
300
GHCi> 5 * (6 * 10)
300
GHCi> 255 * 1
255
GHCi> 1 * 255
255

我們也不必侷限於算術。(++)，Haskell 列表的追加操作，是另一個例子。它以空列表作為它的單位元。

GHCi> ([1,2,3] ++ [4,5,6]) ++ [7,8,9]
[1,2,3,4,5,6,7,8,9]
GHCi> [1,2,3] ++ ([4,5,6] ++ [7,8,9])
[1,2,3,4,5,6,7,8,9]
GHCi> [1,2,3] ++ []
[1,2,3]
GHCi> [] ++ [1,2,3]
[1,2,3]

事實證明，有很多二元運算滿足結合律且具有單位元。根據定義，所有這些運算都提供了么半群的例子。例如，我們說整數在加法下形成一個么半群，其中0是單位元。

Monoid 類

么半群在 Haskell 中非常常見，因此在核心庫中找到它們的型別類並不奇怪。這裡就是它。

class Monoid a where
    mempty  :: a
    mappend :: a -> a -> a

    mconcat :: [a] -> a
    mconcat = foldr mappend mempty

mappend 方法是二元運算，mempty 是它的單位元。第三個方法，mconcat，作為獎勵提供；它會遍歷一個列表並按順序將它的元素mappend在一起。

“mappend”對於如此通用的二元函式來說是一個有點長而且笨拙的名字，對於一個經常用中綴表示的函式來說更是如此。幸運的是，Data.Monoid Data.Monoid 提供了(<>)，這是一個方便的mappend運算子同義詞。在接下來的內容中，我們將交替使用mappend和(<>)。

例如，這是列表的么半群例項。

instance Monoid [a] where
    mempty  = []
    mappend = (++)

請注意，在這種情況下，mconcat = foldr (++) [] 等價於concat，這解釋了該方法的名稱。

可以將么半群視為在某種意義上支援追加的型別，儘管需要一些詩歌許可。Monoid 定義非常通用，並不侷限於資料結構，所以“追加”有時只是一個比喻。

正如我們之前所提到的，數字（即Num 的例項）在加法和乘法下都形成了么半群。這會導致一個尷尬的問題：在編寫例項時選擇哪一個。在這種情況下，沒有充分的理由選擇一種可能性而不是另一種，所以可以透過為每個例項建立一個newtype來避免這種困境。

-- | Monoid under addition.
newtype Sum a = Sum { getSum :: a }

-- | Monoid under multiplication.
newtype Product a = Product { getProduct :: a }

instance Num a => Monoid (Sum a) where
    mempty = Sum 0
    Sum x `mappend` Sum y = Sum (x + y)

instance Num a => Monoid (Product a) where
    mempty = Product 1
    Product x `mappend` Product y = Product (x * y)

以下是Sum和Product的快速演示。

GHCi> import Data.Monoid
GHCi> Sum 5 <> Sum 6 <> Sum 10
Sum {getSum = 21}
GHCi> mconcat [Sum 5, Sum 6, Sum 10]
Sum {getSum = 21}
GHCi> getSum . mconcat . fmap Sum $ [5, 6, 10]
21
GHCi> getProduct . mconcat . fmap Product $ [5, 6, 10]
300

Monoid 定律

所有Monoid 例項必須遵循的定律只是陳述了我們已經知道的屬性：mappend是結合的，mempty是它的單位元。

(x <> y) <> z = x <> (y <> z) -- associativity
mempty <> x = x               -- left identity
x <> mempty = x               -- right identity

練習
Bool 有幾個可能的么半群例項。使用newtype編寫至少兩個，如Sum和Product示例所示。確保驗證你的例項滿足么半群定律。

用途

擁有一個對如此簡單的概念來說名字很長的類有什麼優勢？和往常一樣，關鍵的收益體現在兩個相關的維度：可識別性和通用性。例如，只要看到(<>)被使用，你就知道，無論具體例項是如何定義的，正在進行的操作都是結合的，並且有一個單位元。此外，你還可以知道，如果一個型別存在Monoid 的例項，那麼就可以利用為通用么半群編寫的函式。作為一個這樣的函式的玩具示例，我們可以使用這個函式將三個列表連線起來。

threeConcat :: [a] -> [a] -> [a] -> [a]
threeConcat a b c = a ++ b ++ c

…並將所有(++)替換為(<>)…

mthreeConcat :: Monoid m => m -> m -> m -> m
mthreeConcat a b c = a <> b <> c

…從而使其適用於任何Monoid。當它用於其他型別時，泛化函式將以類似於原始函式的方式執行，如么半群定律所規定。

GHCi> mthreeConcat "Hello" " " "world!"
"Hello world!"
GHCi> mthreeConcat (Sum 5) (Sum 6) (Sum 10)
Sum {getSum = 21}

么半群非常常見，並且具有許多有趣的實際應用。

Writer 函子

型別為Writer w a 的計算會計算出一個型別為a 的值，同時生成型別為w 的額外輸出，它必須是Monoid 的例項，而函子的繫結運算子使用mappend 來累積額外輸出。一個典型的用例是日誌記錄，其中每個計算都會生成一個日誌條目以供日後檢查。在日誌記錄用例中，這意味著在執行一系列計算期間生成的條目會自動合併到一個單獨的日誌輸出中。

Foldable 類

么半群在將類似列表的摺疊泛化到其他資料結構方面發揮著重要作用。我們將在即將到來的關於Foldable 類的章節中詳細研究這一點。

指樹

從資料結構上的操作轉向資料結構的實現，么半群可以用於實現指樹，這是一種高效且通用的資料結構。它的實現利用了么半群值作為樹節點的標籤；只需更改所涉及的Monoid 例項，就可以獲得不同的資料結構（例如序列、優先順序佇列和搜尋樹）。

選項和設定

在完全不同的語境下，么半群可以成為處理應用程式選項和設定的一種便捷方法。兩個例子是 Cabal（Haskell 包管理系統，“包資料庫是么半群。配置檔案是么半群。命令列標誌和命令列標誌集是么半群。包構建資訊是么半群。”）和 XMonad，一個用 Haskell 實現的平鋪視窗管理器（“xmonad 配置鉤子是么半群的。”） 。以下是 XMonad 配置檔案（只是一個 Haskell 程式）中的程式碼片段，展示了么半群鉤子的實際應用 。

-- A ManageHook is a rule, or a combination of rules, for
-- automatically handling specific kinds of windows. It
-- is applied on window creation.

myManageHook :: ManageHook
myManageHook = composeAll
    [ manageConkeror
    , manageDocs
    , manageEmacs
    , manageGimp
    , manageImages
    , manageTerm
    , manageTransient
    , manageVideo
    , manageWeb
    , myNSManageHook scratchpads
    ]

-- manageEmacs, for instance, makes a duplicate of an Emacs
-- window in workspace 3 and sets its opacity to 90%. It
-- looks like this:

-- liftX lifts a normal X action into a Query (as expected by -->)
-- idHook ensures the proper return type
manageEmacs :: ManageHook
manageEmacs =
    className =? "Emacs"
    --> (ask >>= doF . \w -> (copyWindow w "3:emacs"))
    <+> (ask >>= \w -> liftX (setOpacity w 0.9) >> idHook)

-- The hooks are used as fields of the XMonad configuration,
-- which is passed to the IO action that starts XMonad.

myConfig xmproc = defaultConfig
                  { -- Among other fields...
                  , manageHook         = myManageHook
                  } 

-- idHook, (<+>), composeAll and (-->) are just user-friendly
-- synonyms for monoid operations, defined in the
-- XMonad.ManageHook module thusly:

-- | The identity hook that returns the WindowSet unchanged.
idHook :: Monoid m => m
idHook = mempty

-- | Infix 'mappend'. Compose two 'ManageHook' from right to left.
(<+>) :: Monoid m => m -> m -> m
(<+>) = mappend

-- | Compose the list of 'ManageHook's.
composeAll :: Monoid m => [m] -> m
composeAll = mconcat

-- | @p --> x@.  If @p@ returns 'True', execute the 'ManageHook'.
--
-- > (-->) :: Monoid m => Query Bool -> Query m -> Query m -- a simpler type
(-->) :: (Monad m, Monoid a) => m Bool -> m a -> m a
p --> f = p >>= \b -> if b then f else return mempty

一個簡單的 diagrams 例子。它的程式碼是

mconcat  (fmap
  (circle . (/20)) [1..5])
<> triangle (sqrt 3 / 2)
  # lwL 0.01 # fc yellow 
<> circle 0.5 # lwL 0.02
  # fc deepskyblue

diagrams

The diagrams 包提供了一個強大的庫，用於以程式設計方式生成向量影像。在基本層面上，(<>) 經常出現在使用 diagrams 的程式碼中，因為正方形、矩形和其他此類圖形元素具有 Monoid 例項，這些例項用於將它們彼此疊加。在更深層的層面上，大多數圖形元素的操作在內部都是以么半群的形式定義的，並且實現充分利用了它們的數學特性。

同態

給定任意兩個么半群 A 和 B，如果函式 f :: A -> B 保留了么半群結構，則它是么半群同態，因此

f mempty          = mempty
f (x `mappend` y) = f x `mappend` f y

換句話說，f 將 mempty :: A 對映到 mempty :: B，並將 A 的 mappend 結果對映到 B 的 mappend 結果（在使用 f 將 mappend 的引數轉換為 B 值之後）。

例如，length 是 ([a],++) 和 (Int,+) 之間的么半群同態

length []         = 0
length (xs ++ ys) = length xs + length ys

在試圖確定給定函式是否為同態時，不要關注其實際實現；雖然它的定義明確地影響了它是否為同態，但同態是由函式保留對映中涉及的兩個底層結構的操作的能力來定義的，而不是直接與實現細節相關聯。

Chris Kuklewicz 在 Google Protocol Buffers API 文件中識別出了一個有趣的“野外”么半群和同態示例。 根據引用的評論中提供的引文，我們強調，在 (C++) 中，

MyMessage message;
message.ParseFromString(str1 + str2);

... 等同於 ...

MyMessage message, message2;
message.ParseFromString(str1);
message2.ParseFromString(str2);
message.MergeFrom(message2);

... 意味著 ParseFromString 是一個么半群同態。在一個假設的 Haskell 實現中，以下方程式成立

parse :: String -> Message
-- these are just equations, not actual code.
parse []         = mempty
parse (xs ++ ys) = parse xs `mergeFrom` parse ys

（它們不會完全成立，因為解析可能會失敗，但大致如此。）

識別同態可以導致有用的重構。例如，如果 mergeFrom 證明是一個昂貴的操作，那麼從效能的角度來看，可能有利於在解析字串之前將它們連線起來。parse 作為么半群同態，將保證獲得相同的結果。

進一步閱讀

• Dan Piponi (Sigfpe) 關於么半群的文章：一篇部落格文章概述；關於結合性直觀的評論。

• 許多與么半群相關的連結

• 關於手指樹的額外評論（Haskell Cafe）：FingerTrees。

• 關於 Monoid 在 Cabal 中的額外用法評論（Haskell Cafe）：[3]；[4]。

• 關於 diagrams 和么半群：么半群：主題和變奏（函式式珍珠），作者 Brent Yorgey。