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" 是一個有點長而且笨拙的名字，用於一個如此通用的二元函式，更不用說一個經常被用作中綴運算子的函數了。幸運的是，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 的額外輸出，其中 w 必須是 Monoid 的例項，並且函子的繫結運算子使用 mappend 來累積額外輸出。一個典型的用例是日誌記錄，其中每個計算都會生成一個日誌條目供以後檢查。在日誌記錄用例中，這意味著在多個計算過程中生成的條目都會自動組合成一個單獨的日誌輸出。

Foldable 類

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

手指樹

從資料結構的操作轉向資料結構的實現，么半群可用於實現**指樹**（finger tree），這是一種高效且通用的資料結構。其實現利用么半群值作為樹節點的標籤；只需改變涉及的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

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。

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

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