Haskell/Monoid類型類

這裡只翻譯了關於 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

Monoid類型類  >> Applicative類型類  >> 箭頭  >> 理解箭頭  >> Foldable類型類  >> Traversable類型類  >> 延續過渡風格(CPS)  >> 可變對象  >> 拉鏈  >> 適用函子  >> 獨異點  >> Lens 和引用  >> 並行


Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads
高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能


庫參考 >> 普通實務 >> 特殊任務

  1. Haskell Café