Monoid
class Monoid a whereMonoid(幺半群)是个类型类。存在单位元mempty,二元结合操作mappend,以及列表折叠操作mconcat。
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
注:幺半群是群论中的概念。所谓半群是指一个集合,其中存在一种满足结合律的结合运算。所谓幺,是指集合之内存在一个单位元,它与集合中任何元素e结合(包括左结合和右结合)的结果都是e。比如实数的求和以及求积都是幺半群。显然求和运算以及求积运算都满足结合律。求和的单位元是0,求积的单位元是1,因为0+e=e+0=e,而1*e=e*1=e。再比如时钟也是幺半群。
(<>)
(<>) :: Monoid m => m -> m -> m
(<>) = mappend
Monoid的法则
mempty <> x = x幺半群满足结合律(半群),存在单位元(幺)。
x <> 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 | GT排序这个幺半群用于实现按字典排序。单位元为相等即EQ。
instance Monoid Ordering where
mempty = EQ
LT `mappend` _ = LT
EQ `mappend` y = y
GT `mappend` _ = GT
Prelude> LT <> GTLTPrelude> GT <> LTGTPrelude> mempty <> LTLTPrelude> mempty <> GTGT
Sum 和 Product 都是 Monoid
newtype Sum a = Sum { getSum :: a }求和以及求积都是幺半群。显然都满足结合律。求和的单位元为0,求积的单位元为1。
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)
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 }求与以及求或都是幺半群。显然都满足结合律。求与的单位元为True,求或的单位元为False。
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)
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) whereMaybe a 是幺半群(前提是 a 是幺半群)。单位元是 Nothing。
mempty = Nothing
Nothing `mappend` m = m
m `mappend` Nothing = m
Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)
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` _ = l
instance 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
Min 和 Max 都是 Monoid
newtype Min a = Min { getMin :: a }
newtype Max a = Max { getMax :: a }
instance (Ord a, Bounded a) => Monoid (Min a) where
mempty = maxBound
mappend = coerce (min :: a -> a -> a)
instance (Ord a, Bounded a) => Monoid (Max a) where
mempty = minBound
mappend = coerce (max :: a -> a -> a)
Prelude Data.Semigroup> Min 3 <> Min 5Min {getMin = 3}Prelude Data.Semigroup> Max 3 <> Max 5Max {getMax = 5}Prelude Data.Semigroup> getMin . mconcat . map Min $ [1,2,3] :: Int1Prelude Data.Semigroup> getMax . mconcat . map Max $ [1,2,3] :: Int3
元组是 Monoid
instance (Monoid a, Monoid b) => Monoid (a,b) where元组是幺半群,前提是其成员都是幺半群。
mempty = (mempty, mempty)
(a1,b1) `mappend` (a2,b2) =
(a1 `mappend` a2, b1 `mappend` b2)
Prelude Data.Semigroup> mconcat $ map (\x -> (Min x, Max x)) [1..10] :: (Min Int, Max Int)(Min {getMin = 1},Max {getMax = 10})