Monoid(幺半群)
A class for monoids (types with an associative binary operation that has an identity) with various general-purpose instances.
Monoid，幺半群，顾名思义，指的是有幺元(单位元，Identity)的半群(semigroup)，而半群的定义如下:
Any semigroup $S$ may be turned into a monoid simply by adjoining an element $e$ not in $S$ and defining \(e*e = e \textit{ and } e*s = s = s*e \textit{ for all } s \in S.\)
From Wiki-Monoid。
Monoid typeclass
Haskell中，Monoid的定义：
class Monoid m where
-- * Minimal complete definition.
mempty :: m
mappend :: m -> m -> m
mempty是一个不接受任何参数的函数，可以看作是一个多态的(polymorphic)的常数，表示一个特定 monoid 的 Identity。mappend是一个满足结合律的二元运算。
Monoid的实例类型是不接受任何参数的类型构造子，Monoid类型类的实例类型的 mempty和mappend的实现必须遵守以下的 Monoid Laws:
mappend mempty x = x
mappend x mempty = x
mappend x (mappend y z) = mappend (mappend x y) z
mconcat = foldr mappend mempty
monoid的结构非常: 一个集合, 一个满足结合律(结果跟运算顺序无关)的封闭二元运算(mappend), 一个单位元(mempty)。这使得monoid称为一种很广泛的代数结构。
Monaids for addition and multiplication
数域上的加法和乘法都能构成幺半群，Haskell中，用到了Sum和Product类型类来辅助实现这两种代数结构。
-- | Monoid under addition.
newtype Sum a = Sum { getSum :: a }
deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)
instance Num a => Monoid (Sum a) where
mempty = Sum 0
mappend = (+) :: a -> a -> a
-- | Monoid under multiplication.
newtype Product a = Product { getProduct :: a }
deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)
instance Num a => Monoid (Product a) where
mempty = Product 1
mappend = (*) :: a -> a -> a
semigroup与并行计算
半群要求运算符合结合律，这一特点很适合用来做并行计算。基于此实现一个 parallel folding：
parFold :: Monoid a => (a -> a -> a) -> [a] -> a
parFold _ [] = mempty
parFold _ [x] = x
parFold xs = (ls `par` rs) `pseq` (ls `mappend` rs) where
(ls', rs') = splitAt (len `div` 2) xs where len = length xs
ls = parFold mappend ls'
rs = parFold mappend rs'
parFold函数采取了并行策略，而正是因为有Monoid这一代数数据类型的约束，parFold的正确性得到了保证。
代数数据类型的意义
再深入一些，monoid 所体现的是Haskell强大的抽象能力。 举个例子，要做尾递归优化，譬如说下面这个函数
sum [] = 0
sum (x:xs) = x + sum xs
其实是可以写成循环的，但是这么写，就不是一个尾递归函数。那要怎么办呢？需要加一个acc参数把他写成为递归的，但是实际上这么做是把右结合的加法改成了左结合的加法。
那Haskell怎么知道加法可以这么做呢？当然可以hardcode。
那自定义的运算又如何取得相同的效果？这时就需要Monoid这个 type class，将一个类型行声明为Monoid的instance，实现相应的mappend，GHC就能依此自动地采取一些优化策略。
而关于这个类型的mappend函数的信息（如运算满足结合律），难以通过常规的程序分析得到。
Haskell中，很多抽象就是这么一点一点搞出来的。它不像我们写C++和C#，每一个抽象背后的代码都十分底层无比复杂。Haskell喜欢在一个抽象里面，改一点点东西做成一个新的抽象， 当得到了大量的抽象之后，就突然发现它可以用来解决现实问题了。所以才会看到 Haskell 中有大量的这些平时估计直接用不到的东西。函数式和OO是反的，面向对象是自顶向下的 设计，函数式是自底向上的设计，是组合子逻辑，先定义最基本的操作，然后不断组合，不断堆积以满足你的所有需要。