Haskell/Monoid類型類

Monoid類型類 (解答)

高級Haskell

這裡只翻譯了關於 Monoid 的一個有趣的拓展, 關於 Monoid 的基本用法, 請參見Haskell 趣學指南

同態映射

我們定義么半群 (monoid) 同態映射 (homomorphism)為一個形如 f :: (Monoid a, Monoid b) => a -> b 的保留 monoid 結構的函數, 也就是說:

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

舉個例子, length 是 ([],++) 和 (0,+) 這兩個 monoid 間的同態映射

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

Chris Kuklewicz 在 Google Protocol Buffers API 的文檔中發現了自然出現的一個有趣的 monoid 和同態映射的例子^[1]. 基於我們所引用的討論, 我們發現在如下 Python 代碼中,

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

... 等價於...

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

... 意味著 ParseFromString 是一個么半群同態映射. 若使用 Haskell 實現的話, 以下等式應恆成立:

parse :: String -> Message
-- 这些只是用于演示的等式罢了, 实际上并没有这段代码.
parse []         = mempty
parse (xs ++ ys) = parse xs `mergeFrom` parse ys

(因為解析可能出錯, 這個等式其實並不完美, 但就讓我們暫且假定輸入合法吧.)

辨識出同態映射能幫助我們進行重構. 舉個例子, 若 mergeFrom 是一個耗時的運算, 那麼或許為性能考慮我們可以先將字符串拼合再進行解析. 因為 parse 是一個么半群同態映射, 我們得以保證這樣能夠得出同樣的結果.

Monoid類型類

習題解答

高級Haskell

Haskell