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