关于haskell:Haskell-Monoid幺半群的介绍

翻译自 https://gist.github.com/cscal…

为什么程序员应该关怀 Monoids？因为 Monoids 是一种在编程中重复呈现的常见模式。当模式呈现时，咱们能够将它们抽象化并利用咱们过来所做的工作。这使咱们可能在通过验证的稳固代码之上疾速开发解决方案。

将 ” 可替换性 ” 增加到 Monoid（Commutative Monoid），你就有了能够并行执行的货色。随着摩尔定律的终结，并行计算是咱们进步处理速度的惟一心愿。

以下是我在学习 Monoids 后学到的。它未必残缺，但心愿可能对于向人们介绍 Monoids 有所帮忙。

Monoid 谱系

Monoid 来自数学，从属于代数构造的谱系。因而，从头开始并逐渐开展到 Monoids 会有所帮忙。实际上，咱们进一步能够推到 ” 群 ”(Groups).

Magma(元群)

Magma 是一个汇合以及一个必须闭合的二元运算：

∀ a, b ∈ M : a • b ∈ M

如果将二元运算利用于汇合的任意 2 个元素时，它会生成汇合的另一个成员，则该二元运算是关闭的。（这里 · 示意二元运算）

Magma 的一个示例是 Boolean 和 AND 运算的汇合。

Semigroup(半群)

Semigroup 是具备一个附加要求的 Magma。二元运算对于汇合的所有成员必须是 ” 可联合 ” 的：

∀ a, b, c ∈ S : a · (b · c) = (a · b) · c

一个 Semigroup 的例子是 ” 非空字符串 ” 和 ” 字符串拼接 ” 运算的汇合。

Monoid(幺半群)

Monoid 是蕴含一个附加条件的 Semigroup。汇合中存在一个 ” 幺元 ”(Neutral Element)，能够应用二元运算将其与汇合的任何成员联合，而产生属于雷同汇合的成员。

e ∈ M : ∀ a ∈ M, a · e = e · a = a

一个 Monoid 的例子是字符串汇合以及 ” 字符串拼接 ” 运算。留神，汇合中增加的空字符串是 ” 幺元 ”，并使 Semigroup 称为 Monoid。

另一个 Monoid 的示例是非负整数和加法运算的汇合。幺元为 0。

Group(群)

一个 Group 是蕴含一个附加条件的 Monoid. 汇合中存在 ” 逆 ”，使得:

∀ a, b, e ∈ G : a · b = b · a = e

其中 e 是幺元.

一个 Group 的例子是整数和加法运算的汇合。“ 逆 ” 是正数，幺元是 0。

通过容许正数，咱们将下面的 Monoid 的第二个示例变成了一个 Group。

援用: Math StackExchange question: What’s the difference between a monoid and a group?

Haskell 中的 Monoids

Monoid typeclass(类型类)

在 Haskell Prelude (基于 GHC.Base)中, Monoid typeclass 定义为:

class Monoid a where
  mempty  :: a
  -- ^ 'mappend' 的幺元
  mappend :: a -> a -> a
  -- ^ 一个 "可联合" 的操作
  mconcat :: [a] -> a

  -- ^ 应用 monoid 来折叠一个列表.
  -- 对于大多数类型，会应用 'mconcat' 的默认定义
  -- 但该函数蕴含在类定义中，所以能够为特定类型提供优化的版本.

  mconcat = foldr mappend mempty

其中 mempty 是幺元, mappend 是二元可组合操作符. 这足以成为 Monoid，但为了不便增加了 mconcat。它有一个默认实现，应用二元运算 mappend 从幺元 mempty 开始折叠列表。

实例能够笼罩这个默认实现，咱们稍后会看到。

Monoid 实例

Monoid ()

一个简略例子是仅蕴含 () 的汇合：

instance Monoid () where
  mempty        = ()
  _ `mappend` _ = ()
  mconcat _     = ()

这里汇合只蕴含一个幺元 ()。所以 mappend 并不真正关怀参数，只会返回 ()。意味着惟一无效的参数始终是 ()，因为咱们的汇合只蕴含 ()。

此外，为了提高效率，mconcat 函数被笼罩从而疏忽汇合中的元素列表，因为它们都是()，因而它只返回()。请留神，如果此处省略了 mconcat，因为 mappend 的实现，默认实现将产生雷同的后果。

Monoid () 用例

用这个 Monoid 自身做不了做多少事件。

n :: ()
n = () `mappend` ()

ns :: ()
ns = mconcat [(), (), ()]

Monoid [a]

任意列表的 Monoid：

instance Monoid [a] where
  mempty  = []
  mappend = (++)
  mconcat xss = [x | xs <- xss, x <- xs]

mappend 是 ” 拼接 ” 运算，这意味着幺元 mempty 只能是空列表，[]。

着重要意识到 mconcat 从汇合中获取一份 ” 元素 ” 的列表，这里是 ” 列表的列表 ”。因而，它须要一个 ” 列表的列表 ”，因而参数名称为 xss。

我狐疑 List Comprehensions 比 foldr 更无效，否则没有理由实现 mconcat。

如果咱们想一下，foldr 将反复用 2 个列表调用的 mappend，因为对每个迭代返回的两头列表中的元素进行反复解决，因而效率不高。

应用 List Comprehension 将是一个低级操作，很可能只拜访每个子列表的每个元素一次。

Monoid [a] 用例

as :: [Int]
as = [1, 2, 3]

bs :: [Int]
bs = [4, 5, 6]

asbs :: [Int]
asbs = mconcat [as, bs] -- [1, 2, 3, 4, 5, 6]

(Monoid a, Monoid b) => Monoid (a, b)

任意 Monoid 的 2 元组的 Monoid：

instance (Monoid a, Monoid b) => Monoid (a,b) where
  mempty = (mempty, mempty)
  (a1,b1) `mappend` (a2,b2) = (a1 `mappend` a2, b1 `mappend` b2)

起初，mempty 的定义仿佛令人困惑。乍一看，该定义可能会被误会为递归定义。

实际上这个元组中的第一个 mempty 是 a 类型的 mempty。第二个 mempty 是 b 类型的 mempty。

设想一下 a 是 () 而 b 是 [Int]。那么 mempty 将是 ((), [])，即第一个是 () 的 mempty，第二个是 [Int] 的 mempty。

mappend 的实现非常简单。它为 a 和 b 执行一个 mappend，返回一个 (a, b) 的 2 元组。因为 a 和 b 都是 Monoids，所以 Magmas 和 Monoids 的闭合束缚得以连续。

Monoid (a, b) 用例

p1 :: ((), [Int])
p1 = ((), [1, 2, 3])

p2 :: ((), [Int])
p2 = ((), [4, 5, 6])

p1p2 :: ((), [Int])
p1p2 = mconcat [p1, p2] -- ((), [1, 2, 3, 4, 5, 6])

Monoid b => Monoid (a -> b)

“ 承受一个或多个参数, 返回 Monoid, 的任意函数 ” 的 Monoid：

instance Monoid b => Monoid (a -> b) where
  mempty _ = mempty
  mappend f g x =  f x `mappend` g x

这个定义如何解决带有多个参数的函数并不显著。可能须要给点揭示。

函数注解是 右联合，即它们在右侧联合:

f :: Int -> (Bool -> String) -- 不必要的括号
f s1 s2 = s1 ++ s2

Int -> (Bool -> String) 等价于 Int -> Bool -> String，这就是咱们不蕴含括号的起因。” 右联合性 ” 提醒了这一点。

记住 String 等价于 [Char]，咱们晓得 f 最终会返回一个 Monoid，因为咱们曾经在下面看到了 Monoid [a]。

但没那么快。咱们首先必须依照 Monoid 实例中定义的 a -> b 来合成注解：

Int -> (Bool -> String)
 a  ->       b

这里 b 必须是 Monoid. 得益于 Monoid (a -> b)，它是的。

当初查看 b，咱们失去：

(Bool -> String)
(a   ->    b)

因而，从新利用 Monoid (a -> b) 能解决具备多个参数的函数，例如：

Int -> (String -> (Int -> String))
 a  -> (b)
 a  -> (a'-> (     b'))
 a  -> (a'-> (a'' ->   b'')

这里 b 是 Monoid, 因为 b' 是 Monoid, 也因为 b'' 是 String 是 Monoid, 还因为 String 是 [Char] 并且咱们之前看到所有列表都是 Monoids。

再看定义：

instance Monoid b => Monoid (a -> b) where
  mempty _ = mempty
  mappend f g x =  f x `mappend` g x

如愿地 mempty 的定义当初更有意义了。mempty 属于 a -> b 类型，这就是它接管单个参数的起因。它疏忽参数并简略地返回类型为 b 的 mempty。

对于 Bool -> String 类型的函数，mempty 是 []，即 Monoid [a] 的 mempty。

对于类型为 Int -> Bool -> String 的函数，mempty 是递归的，即它首先以 Bool -> String 类型返回本身，因此会返回 []。

留神 a 在这里是无关紧要的。事实上，函数的所有输出类型都是无关紧要的。这里惟一重要的是返回值的类型。这就是为什么只有 b 必须是 Monoid。

因而，以下函数类型将具备 mempty 最终返回 []，因为它们都返回 String：

Int -> String
Int -> Int -> String
Int -> Bool -> Int -> Double -> String

相似地，mappend 将单个参数利用于全副两个函数，而后调用 b 的 mappend。

对于类型为 String -> String 的函数，mappend 应用输出 String 调用全副两个函数，而后为 Monoid [a] 的 String 调用 mappend，即 (++)。

对于类型为 String -> String -> String 的函数，mappend 应用 第一个 输出参数 String 调用全副两个函数，而后为 String -> String 调用 mappend，它是 Monoid (a -> b)，即它自身。

再接着，应用 第二个 输出参数 String 调用全副两个函数，而后对类型为 Monoid [a] 的 String 调用 mappend，也即调用 (++)。

Monoid (a -> b) 用例

import Data.Monoid ((<>))

parens :: String -> String
parens str = "(" ++ str ++ ")"

curlyBrackets :: String -> String
curlyBrackets str = "{" ++ str ++ "}"

squareBrackets :: String -> String
squareBrackets str = "[" ++ str ++ "]"

pstr :: String -> String
pstr = parens <> curlyBrackets <> squareBrackets

astr :: String
astr = pstr "abc"

留神 <> 操作符在 pstr 中应用。这个操作符是从 Data.Monoid 导入的，是 mappend 操作的别名(中断)。

如果你回顾 Monoid 的 class 定义，你会看到 mappend 的类型是 a -> a -> a。

因为 parens 和 curlyBrackets 都具备类型 -> String -> String，因而 parens <> curlyBrackets 将具备 String -> String 类型，parens <> curlyBrackets <> squareBrackets 也将具备该类型。

pstr 将接管 String 并将其利用于 parens、curlyBrackets 和 squareBrackets 拼接这些调用的后果。

因而，astr 是(abc){abc}[abc]。

如果要利用的函数数量很大，应用 <> 办法会变得繁琐。这就是 Monoid class 为什么有个辅助函数 mconcat。

咱们能够这样重构代码：

pstr :: String -> String
pstr = mconcat [parens, curlyBrackets, squareBrackets]

astr :: String
astr = pstr "abc"

Monoid \<number-type\>

回顾 Monoid 的定义，咱们必须抉择可联合的二元运算，但对于数字，它能够是加法或者是乘法。

如果咱们抉择加法，那就会错过乘法，反之亦然。

不巧的是，每种类型只能有 1 个 Monoid。

解决这个问题的办法是创立一个新类型，其中 蕴含 一个用于加法的 Num 和另一种用于乘法的类型。

这些类型能够在 Data.Monoid 中找到：

{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import GHC.Generics

newtype Sum a = Sum {getSum :: a}
        deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)

newtype Product a = Product {getProduct :: a}
        deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)

当初咱们能够为每个创立 Monoids。

Monoid Sum(和)

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Coerce

instance Num a => Monoid (Sum a) where
  mempty = Sum 0
  mappend = coerce ((+) :: a -> a -> a)

mempty 是 0 包裹在 Sum 中。

这里 coerce 用于平安地将 Sum a 强制转换为它的 “Representational type”，例如 Sum Integer 将被强制转换为 Integer 并应用适当的 + 运算。

ScopedTypeVariables pragma 容许咱们将 a -> a -> a 中的 a 等同于 instance 的范畴，从而等同于 Num a 中的 a。

Monoid Sum 用例

sum :: Sum Integer
sum = mconcat [Sum 1, Sum 2] -- Sum 3

Monoid Product(积)

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Coerce

instance Num a => Monoid (Product a) where
        mempty = Product 1
        mappend = coerce ((*) :: a -> a -> a)

mempty 是 0 包裹在 Product 中。

这里 coerce 用于平安地将 Product a 强制转换为它的 Representational type，例如 Product Integer 将被强制转换为 Integer 并应用适当的 * 运算。

ScopedTypeVariables pragma 容许咱们将 a -> a -> a 中的 a 等同于 instance 的范畴，从而等同于 Num a 中的 a。

Monoid Product 用例

product :: Product Integer
product = mconcat [Product 2, Product 3] -- Product 6

Monoid Ordering(排序)

在看这个 Monoid 之前，让咱们回顾一下排序和比照：

data Ordering = LT | EQ | GT

在应用 class Ord 中的 compare 时用到此类型，例如：

compare :: a -> a -> Ordering

其应用示例：

compare "abcd" $ "abed" -- LT

当初 Data.Ord 中有一个很棒的辅助函数用于比拟，称为 comparing：

comparing :: (Ord a) => (b -> a) -> b -> b -> Ordering
comparing p x y = compare (p x) (p y)

该辅助函数在比拟 之前 对每个元素利用一个函数。这对于元组之类的货色十分有用：

comparing fst (1, 2) (1, 3) -- EQ
comparing snd (1, 2) (1, 3) -- LT

当初对于 Monoid：

-- lexicographical ordering
instance Monoid Ordering where
  mempty         = EQ
  LT `mappend` _ = LT
  EQ `mappend` y = y
  GT `mappend` _ = GT

这个实现看起来很随便。为什么有人会以这种形式实现 Monoid Ordering？

好吧，如果你想在 sortBy 追加一部分比照，那么你须要这个实现。

看一下 sortBy:

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

请留神，第一个参数与 compare、comparing fst、comparing snd 和 comparing fst `mappend` comparison snd 的类型雷同。

为什么？因为 mappend 的类型是 a -> a -> a，这里的 a 是 (a, b) -> (a, b) -> Ordering。

所以咱们能够联合或 mappend 比拟函数，咱们将有一个整体的比拟函数。

请记住，Monoid (a -> b) 要求 b 也是 Monoid。

因而，如果咱们心愿可能 mappend 咱们的比拟函数，咱们必须将 Ordering 设置为 Monoid，就像在下面做的那样。

然而咱们依然没有答复为什么它有这个看似奇葩的定义。

好吧，评论有点线索，即“字典程序”。这实质上意味着“字母程序”或“左优先”，即如果最右边是 GT 或 LT，那么所有对于左边的比拟都不再失效。

然而，如果最右边的是 EQ，那么咱们须要向右看以确定组合比拟的最终后果。

这正是该实现所做的。这里再次增加一些额定的正文来阐明这一点：

-- 字典序
instance Monoid Ordering where
  mempty         = EQ -- EQ 直到右边或直到左边, 对最终后果没有影响
  LT `mappend` _ = LT -- 如果右边是 LT 则疏忽右侧
  EQ `mappend` y = y  -- 如果右边是 EQ 则用右侧
  GT `mappend` _ = GT -- 如果右边是 GT 则疏忽右侧

花点工夫来好好了解这一点。一旦你这样做了，这将更容易了解：

sortBy (comparing fst <> comparing snd) [(1,0),(2,1),(1,1),(2,0)]
-- [(1,0),(1,1),(2,0),(2,1)]

要了解它是如何工作的，你必须记住 Monoid (a -> b)。

咱们是在对 (a, b) -> (a, b) -> Ordering 类型的函数做 mappend. 一旦这两个函数都执行实现，咱们就将依照咱们的“字典程序”返回的两个 Ordering 值做 mappend。

这意味着比照 fst 相较于比照 snd 更优先，这就是为什么所有 (1, x) 都将在所有 (2, y) 之前，即便当 x > y 时也是如此。

咱们能够做一个不同的比拟，咱们只关怀比拟 snd：

sortBy (comparing snd) [(1,0),(2,1),(1,1),(2,0)]
-- [(1,0),(2,0),(2,1),(1,1)]

这里 fst 术语不可预测的程序，而 snd 是升序的。

为了好玩，咱们能够别离管制升序和降序。首先让咱们定义一些辅助函数：

asc, desc :: Ord b => (a -> b) -> a -> a -> Ordering
asc = comparing
desc = flip . asc

当初咱们能够对 fst 降序和 snd 升序排序：

sortBy (desc fst <> asc snd) [(1,0),(2,1),(1,1),(2,0)]
-- [(2,0),(2,1),(1,0),(1,1)]

优化 Monoid Ordering

示例排序都只应用大量的比照。事实上，大多数排序只会应用大量的比拟。

即便如此，即便第一个返回 LT 或 GT，也必须执行 mappend。当只有很大量的比拟时，这仿佛没什么大不了的。但它可能叠加成为一个大列表。

咱们心愿咱们的比照走的是“短路”，这通常用布尔二元运算 && 和 || 来实现。

Monoid Ordering 的以后定义不可能走短路，因为它依赖于默认的 mconcat 实现，该实现应用拜访每个列表元素的 foldr 函数。

如果咱们编写本人的 Moniod Ordering 并实现一个提前返回后果的 mconcat，咱们将有一个更高效的排序。

import Prelude hiding (Monoid, mempty, mappend, mconcat)
import Data.List
import Data.Maybe
import Control.Arrow

instance Monoid Ordering where
  mempty         = EQ
  LT `mappend` _ = LT
  EQ `mappend` y = y
  GT `mappend` _ = GT
  mconcat = find (/= EQ) >>> fromMaybe EQ

这个实现容许咱们重构咱们之前的排序：

sortBy (mconcat [desc fst, asc snd]) [(1,0),(2,1),(1,1),(2,0)]
-- [(2,0),(2,1),(1,0),(1,1)]

后果雷同，但任何时候 dest fst 返回了 LT 或 GT，那么 asc snd 将被跳过。

留神：咱们的实现依赖 Data.List、Data.Maybe 和 Control.Arrow，如果在规范中实现它们会不必要地耦合 Data.Monoid。这个限度能够通过编写一个专用的函数来克服（不是很 “Don’t repeat yourself”）。

然而，笼罩规范实现的最大问题是咱们必须遮蔽 所有 Monoid 定义。

这些是针对边缘状况进行优化的一些相当大的毛病。但它同样是一个很好的练习。此外，如果咱们尝试排序的列表很大，那么它可能是值得的。

援用:

• The Monoid Instance for Ordering
• Monoids in Haskell

可替换 Monoid (Abelian Monoid)

如结尾所述，如果咱们向 Monoid（或 Group）再增加一个束缚，咱们能够并行执行操作。

该束缚是 ” 可替换性 ”。

∀ a, b ∈ M : a · b = b · a

通过施加该束缚，咱们能够按 任何 程序解决列表。这能够交由编译器并行化，借助类库甚至分发给其余机器。

这是定义：

class Monoid m => CommutativeMonoid m

没有写函数可能看起来很奇怪，但它的接口与 Monoid 雷同，只是要求二元操作反对交换律。

可怜的是，在 Haskell 中没有方法要求这些束缚。

Num a => CommutativeMonoid (Sum a)

这是定义：

instance Num a => CommutativeMonoid (Sum a)

Sum（或 Product）应用 CommutativeMonoid 而不是 Monoid 的起因：

1. 更好地传播如何应用 Monoid
2. 调用 须要 一个 CommutativeMonoid 的函数

论断

Monoids 是拼接类似事物的弱小形象，这些形象能够在编程中重复地出现。

心愿这对 Monoids 是一个好介绍。还有很多其余类型的 Monoid，然而一旦你有了大抵的理解，钻研这些其余特化的 Monoid 应该会容易很多。