跳转到内容

Haskell/Monoids

Edit links
来自 Wikibooks，开放的书籍，为开放的世界
幺半群 (解决方案)
高级 Haskell

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

在本书的早期部分，我们已经对幺半群和 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
练习
  1. Bool 有几种可能的幺半群实例。使用 newtype 编写至少两个这样的实例，如 Sum 和 Product 示例所示。确保验证你的实例满足幺半群定律 [1]。

用途

[编辑 | 编辑源代码]

拥有一个具有浮夸名称的类来表示如此简单的概念有什么优势？与往常一样，在这种情况下，主要收益存在于两个相关的维度：可识别性和通用性。例如，每当你看到使用 (<>) 时，你就会知道，无论特定的实例是如何定义的，所执行的操作都是结合的，并且具有单位元。此外，你还会知道，如果一个类型存在 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实例，即可获得不同的数据结构（例如序列、优先队列和搜索树）。[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
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。
  • 关于 Cabal 中Monoid使用的额外评论（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"
华夏公益教科书