Haskell语言学习笔记（8）Monoid

Monoid

class Monoid a where  mempty :: a  mappend :: a -> a -> a  mconcat :: [a] -> aMonoid（幺半群）是个类型类。存在单位元mempty，二元结合操作mappend，以及列表折叠操作mconcat。注：幺半群是群论中的概念。所谓半群是指一个集合，其中存在一种满足结合律的结合运算。所谓幺，是指集合之内存在一个单位元，它与集合中任何元素e结合（包括左结合和右结合）的结果都是e。比如实数的求和以及求积都是幺半群。显然求和运算以及求积运算都满足结合律。求和的单位元是0，求积的单位元是1，因为0+e=e+0=e，而1*e=e*1=e。再比如时钟也是幺半群。
(<>)
(<>) :: Monoid m => m -> m -> m(<>) = mappend
Monoid的法则
mempty <> x = xx <> mempty = x(x <> y) <> z = x <> (y <> z)幺半群满足结合律（半群），存在单位元（幺）。
[a] 是 Monoid
instance Monoid [a] where        mempty  = []        mappend = (++)        mconcat xss = [x | xs <- xss, x <- xs]列表是个幺半群。二元结合操作(++)满足结合律。单位元为空列表[]。
PRelude> [1,2,3] <> [4,5,6][1,2,3,4,5,6]Prelude> "pang" <> mempty"pang"Prelude> mconcat [[1,2],[3,6],[9]][1,2,3,6,9]
Ordering 是 Monoid
data Ordering = LT | EQ | GTinstance Monoid Ordering where        mempty         = EQ        LT `mappend` _ = LT        EQ `mappend` y = y        GT `mappend` _ = GT排序这个幺半群用于实现按字典排序。单位元为相等即EQ。
Prelude> LT <> GTLTPrelude> GT <> LTGTPrelude> mempty <> LTLTPrelude> mempty <> GTGT
Sum 和 Product 都是 Monoid
newtype Sum a = Sum { getSum :: a }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)求和以及求积都是幺半群。显然都满足结合律。求和的单位元为0，求积的单位元为1。
Prelude Data.Monoid> Sum 5 <> Sum 6 <> Sum 10Sum {getSum = 21}Prelude Data.Monoid> getSum . mconcat . fmap Sum $ [5, 6, 10]21Prelude Data.Monoid> Product 5 <> Product 6 <> Product 10Product {getProduct = 300}Prelude Data.Monoid> getProduct . mconcat . fmap Product $ [5, 6, 10]300
Any 和 All 都是 Monoid
newtype Any = Any { getAny :: Bool }newtype All = All { getAll :: Bool }instance Monoid Any where        mempty = Any False        Any x `mappend` Any y = Any (x || y)instance Monoid All where        mempty = All True        All x `mappend` All y = All (x && y)求与以及求或都是幺半群。显然都满足结合律。求与的单位元为True，求或的单位元为False。
Prelude Data.Monoid> Any True <> Any FalseAny {getAny = True}Prelude Data.Monoid> All True <> All FalseAll {getAll = False}Prelude Data.Monoid> getAny . mconcat . map Any $ [False, False, False, True]TruePrelude Data.Monoid> getAll . mconcat . map All $ [False, False, False, True]False
如果 a 是 Monoid，那么 Maybe a 也是 Monoid
instance Monoid a => Monoid (Maybe a) where  mempty = Nothing  Nothing `mappend` m = m  m `mappend` Nothing = m  Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)Maybe a 是幺半群（前提是 a 是幺半群）。单位元是 Nothing。
Prelude Data.Monoid> Nothing <> Just "andy"Just "andy"Prelude Data.Monoid> Just LT <> NothingJust LTPrelude Data.Monoid> Just (Sum 3) <> Just (Sum 4) Just (Sum {getSum = 7})
First 和 Last 都是 Monoid
newtype First a = First { getFirst :: Maybe a }newtype Last a = Last { getLast :: Maybe a }instance Monoid (First a) where        mempty = First Nothing        First Nothing `mappend` r = r        l `mappend` _             = linstance Monoid (Last a) where        mempty = Last Nothing        l `mappend` Last Nothing = l        _ `mappend` r            = r
Prelude Data.Monoid> First (Just 'a') <> First (Just 'b')First {getFirst = Just 'a'}Prelude Data.Monoid> Last (Just 'a') <> Last (Just 'b')Last {getLast = Just 'b'}Prelude Data.Monoid> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]  Just 9Prelude Data.Monoid> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]  Just 10