跳转到内容

Haskell/Monoids

Edit links
来自维基教科书，开放的书本，开放的世界
幺半群 (解决方案)
高级 Haskell

幺半群
Applicative 函子
可折叠
可遍历
箭头教程
理解箭头 75% developed
延续传递风格
拉链 75% developed
镜头
共函子 0% developed
值递归 (MonadFix)
有副作用的流
可变对象 50% developed
并发 0% developed
模板 Haskell 0% developed
类型族 0% developed

在本书的早期部分，我们已经对幺半群和 Monoid 类型类做了一些间接的提及（最值得注意的是在讨论 MonadPlus 时）。这里我们将对它们进行更详细的介绍，并展示它们为何有用。

什么是幺半群？

[edit | edit source]

将数字加起来的运算有一些非常基本的性质，我们在将数字加起来的时候甚至不会去想它们。其中之一是结合律：当加三个或多个数字时，我们对这些数字进行分组的方式并不重要。

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 类

[edit | edit source]

幺半群在 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 定律

[edit | edit source]

所有Monoid 实例必须遵循的定律只是陈述了我们已经知道的属性：mappend是结合的，mempty是它的单位元。

(x <> y) <> z = x <> (y <> z) -- associativity
mempty <> x = x               -- left identity
x <> mempty = x               -- right identity
练习
  1. Bool 有几个可能的幺半群实例。使用newtype编写至少两个，如Sum和Product示例所示。确保验证你的实例满足幺半群定律[1]。

用途

[edit | edit source]

拥有一个对如此简单的概念来说名字很长的类有什么优势？和往常一样，关键的收益体现在两个相关的维度：可识别性和通用性。例如，只要看到(<>)被使用，你就知道，无论具体实例是如何定义的，正在进行的操作都是结合的，并且有一个单位元。此外，你还可以知道，如果一个类型存在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 实例，就可以获得不同的数据结构（例如序列、优先级队列和搜索树）。[2]
选项和设置
在完全不同的语境下，幺半群可以成为处理应用程序选项和设置的一种便捷方法。两个例子是 Cabal（Haskell 包管理系统，“包数据库是幺半群。配置文件是幺半群。命令行标志和命令行标志集是幺半群。包构建信息是幺半群。”）和 XMonad，一个用 Haskell 实现的平铺窗口管理器（“xmonad 配置钩子是幺半群的。”） [3]。以下是 XMonad 配置文件（只是一个 Haskell 程序）中的代码片段，展示了幺半群钩子的实际应用 [4]。
-- 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 实例，这些实例用于将它们彼此叠加。在更深层的层面上，大多数图形元素的操作在内部都是以幺半群的形式定义的，并且实现充分利用了它们的数学特性。

同态

[edit | edit source]

给定任意两个幺半群 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 文档中识别出了一个有趣的“野外”幺半群和同态示例。 [5] 根据引用的评论中提供的引文，我们强调，在 (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 作为幺半群同态，将保证获得相同的结果。

进一步阅读

[edit | edit source]
  • 关于手指树的额外评论（Haskell Cafe）：FingerTrees。
  • 关于 Monoid 在 Cabal 中的额外用法评论（Haskell Cafe）：[3]；[4]。

注释

  1. ↑ 稍后你会发现，其中两个实例已经在 Data.Monoid 中定义。
  2. ↑ 这篇博客文章，基于 Ralf Hinze 和 Ross Patterson 的论文，包含了关于幺半群如何在手指树中使用的简明易懂的解释。
  3. ↑ 引文来源（Haskell Cafe 邮件列表）：[1]，[2]。
  4. ↑ 代码片段取自 HaskellWiki 中 Ivy Foster 的示例配置 和 XMonad 的 XMonad.ManageHook 模块（截至版本 0.11）。
  5. ↑ 来源（Haskell Cafe）
取自 "https://wikibooks.cn/w/index.php?title=Haskell/Monoids&oldid=3675677"
华夏公益教科书