发表更新14 分钟读完 (大约2148个字)0次访问

「Learn Haskell」#6 半群与幺半群

Semigroup

半群（semigroup）是一个集合$S$，它需要指定一个二元运算符$\oplus$，并且满足

$$
a\oplus b \in S\quad a, b\in S
$$

以及结合（associative）律：

$$
(a\oplus b)\oplus c = a\oplus (b\oplus c)
$$

这个二元运算符在Haskell的Semigroup中被定义为<>函数：

1
2
3
4
5
6
7
8
9
10
class Semigroup a where
    (<>) :: a -> a -> a 

    sconcat :: NonEmpty a -> a 
    sconcat (a :| as) = go a as where 
        go b (c:cs) = b <> go c cs 
        go b []     = b
    
    stimes :: Integarl b => b -> a -> a 
    stimes = ...

除此之外还有sconcat和stimes函数，都给出了默认实现。对于列表，<>相当于(++)，stimes相当于concat . replicate：

1
2
3
4
5
6
ghci> [1, 2] <> [3, 4]
[1,2,3,4]
ghci> sconcat $ fromList [[1, 2], [3, 4]]
[1,2,3,4]
ghci> stimes 3 [1, 2]
[1,2,1,2,1,2]

Semigroup Law

  • (x <> y) <> z = x <> (y <> z)

补：NonEmpty

NonEmpty表示非空列表，定义是：

1
data NonEmpty a = a :| [a] deriving (Eq, Ord)

使用一个元素和一个列表用:|连接就可以生成一个NonEmpty类型的列表

Data.List.NonEmpty模块中实现了很多普通列表有的函数，需要qualified import后调用，使用fromList、toList函数可以在普通列表和非空列表之间转换

1
2
3
4
5
6
7
8
ghci> import qualified Data.List.NonEmpty as NE
ghci> arr = NE.fromList [1, 2, 3]
ghci> arr
1 :| [2,3]
ghci> NE.head arr 
1
ghci> NE.tail arr 
[2,3]

Monoid

幺半群（Monoid）是一个有单位元素$e$的半群，即$e$满足：

$$
e\oplus x = x\oplus e = x
$$

1
2
3
4
5
6
7
8
class Semigroup a => Monoid a where 
    mempty  :: a 
    
    mappend :: a -> a -> a 
    mappend = (<>)

    mconcat :: [a] -> a 
    mconcat = foldr mappend mempty

可以看出Monoid要求了三个函数，其中最少只需要mempty，它直接返回一个值，表示单位元素。mappend即Semigroup中的<>运算符，mconcat也提供了默认实现

实例

[a]

因为Monoid的实例是一个具体类型，而不是像Functor等一样等类型构造器，所以[]并不是Monoid的实例，但是具体类型[a]是一个幺半群：

1
2
3
4
5
6
instance Semigroup [a] where 
    (<>) = (++)

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

列表的单位元素(mempty)就是空列表[]，运算符就是合并列表(++)，mconcat也用列表推导重新实现提高效率

1
2
3
4
5
6
7
8
ghci> mempty :: [Int] 
[]
ghci> [1, 2] <> [3, 4]
[1,2,3,4]
ghci> [1, 2] `mappend` [3, 4]
[1,2,3,4]
ghci> mconcat [[1,2], [3,4]]
[1,2,3,4]

Ordering

1
2
3
4
5
6
7
instance Semigroup Ordering where
    LT <> _ = LT
    EQ <> y = y
    GT <> _ = GT

instance Monoid Ordering where
    mempty = EQ

主要可以用于比较字典序：

1
2
ghci> mconcat (zipWith compare "abcd" "acbd")
LT

Sum & Product

对于数字，加法和乘法都满足结合律，所以对于Num，有两种实现Monoid的方式，但是不能为同一类型设置两种实例方式，所以Data.Monoid中提供了两个包装器————Sum和Product：

1
2
newtype Sum a = Sum {getSum :: a} deriving (...)
newtype Product a = Product {getProduct :: a} deriving (...)

它们使用Sum或Product来包装起一个数字，可以通过getSum或getProduct来获取其中的值

对于加法，二元操作为(+)，单位元素为0；对于乘法，二元操作为(*)，单位元素为1:

1
2
3
4
5
6
7
8
9
10
11
instance Num a => Semigroup (Sum a) where
    (<>) = coerce ((+) :: a -> a -> a)

instance Num a => Monoid (Sum a) where
    mempty = Sum 0

instance Num a => Semigroup (Product a) where
    (<>) = coerce ((*) :: a -> a -> a)

instance Num a => Monoid (Product a) where
    mempty = Product 1
1
2
3
4
5
6
7
8
ghci> Sum 5 <> Sum 6 <> Sum 10
Sum {getSum = 21}
ghci> getSum . mconcat . fmap Sum $ [5, 6, 10]
21
ghci> Product 5 <> Product 6 <> Product 10
Product {getProduct = 300}
ghci> getProduct . mconcat . fmap Product $ [5, 6, 10]
300

All & Any

和数字一样，布尔值也有两种实现Monoid的方式，因此Data.Monoid模块中也提供了两个包装器，分别实现了这两种Monoid：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
newtype All = All { getAll :: Bool } deriving (...)

instance Semigroup All where
        (<>) = coerce (&&)

instance Monoid All where
        mempty = All True


newtype Any = Any { getAny :: Bool } deriving (...)

instance Semigroup Any where
        (<>) = coerce (||)

instance Monoid Any where
        mempty = Any False
1
2
3
4
5
6
7
8
ghci> getAll (All True <> mempty <> All False)
False
ghci> getAll (mconcat (map (\x -> All (even x)) [2,4,6,7,8]))
False
ghci> getAny (Any True <> mempty <> Any False)
True
ghci> getAny (mconcat (map (\x -> Any (even x)) [2,4,6,7,8]))
True

Monoid a => Maybe a

如果a是一个(幺)半群，那么Maybe a也是一个幺半群，单位元就是Nothing：

1
2
3
4
5
6
7
instance Semigroup a => Semigroup (Maybe a) where
    Nothing <> b       = b
    a       <> Nothing = a
    Just a  <> Just b  = Just (a <> b)

instance Semigroup a => Monoid (Maybe a) where
    mempty = Nothing
1
2
3
4
5
6
ghci> Nothing <> Just "andy"
Just "andy"
ghci> Just LT <> Nothing
Just LT
ghci> Just (Sum 3) <> Just (Sum 4) 
Just (Sum {getSum = 7})

First & Last

对于Maybe也有两种实现Monoid的方法，即<>操作每次恒取左边和每次恒取右边（在没有Nothing的情况下），所以Data.Monoid模块中也提供了两个新的包装器：First和Last：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
newtype First a = First { getFirst :: Maybe a } deriving (...)

instance Semigroup (First a) where
    First Nothing <> b = b
    a             <> _ = a

instance Monoid (First a) where
    mempty = First Nothing


newtype Last a = Last { getLast :: Maybe a } deriving (...)

instance Semigroup (Last a) where
    a <> Last Nothing = a
    _ <> b            = b

instance Monoid (Last a) where
    mempty = Last Nothing
1
2
3
4
5
6
7
8
ghci> getFirst (First (Just "hello") <> First Nothing <> First (Just "world"))
Just "hello"
ghci> getLast (Last (Just "hello") <> Last Nothing <> Last (Just "world"))
Just "world"
ghci> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]  
Just 9
ghci> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]  
Just 10

Min & Max

对于有界的类型，也有两种实现Monoid的方式，每次二元操作都取最小或最大。Data.Semigroup模块中提供了两个包装其器：Min和Max：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
newtype Min a = Min { getMin :: a } deriving (...)

instance Ord a => Semigroup (Min a) where
    (<>) = coerce (min :: a -> a -> a)

instance (Ord a, Bounded a) => Monoid (Min a) where
    mempty = maxBound


newtype Max a = Max { getMax :: a } deriving (...)

instance Ord a => Semigroup (Max a) where
    (<>) = coerce (max :: a -> a -> a)

instance (Ord a, Bounded a) => Monoid (Max a) where
    mempty = minBound
1
2
3
4
5
6
7
8
ghci> Min 3 <> Min 5
Min {getMin = 3}
ghci> Max 3 <> Max 5
Max {getMax = 5}
ghci> getMin . mconcat . map Min $ [1,2,3] :: Int
1
ghci> getMax . mconcat . map Max $ [1,2,3] :: Int
3

元组

当元组内的所有元素都是幺半群时，整个元组也是一个幺半群：

1
2
3
4
5
6
instance (Semigroup a, Semigroup b) => Semigroup (a, b) where
        (a,b) <> (a',b') = (a<>a',b<>b')
        stimes n (a,b) = (stimes n a, stimes n b)

instance (Monoid a, Monoid b) => Monoid (a,b) where
        mempty = (mempty, mempty)
1
2
ghci> mconcat $ map (\x -> (Min x, Max x)) [1..10] :: (Min Int, Max Int)
(Min {getMin = 1},Max {getMax = 10})

Monoid Laws

  • mempty <> x = x
  • x <> mempty = x
  • (x <> y) <> z = x <> (y <> z)

Monoidal classes

Applicative、Monad、Arrow都有有幺半群性质的子类型类，分别是Alternative、MonadPlus、ArrowPlus

Alternative

1
2
3
4
5
6
7
8
9
10
class Applicative f => Alternative f where
    -- | The identity of '<|>'
    empty :: f a
    -- | An associative binary operation
    (<|>) :: f a -> f a -> f a

    some :: f a -> f [a]
    some v = (:) <$> v <*> many v
    many :: f a -> f [a]
    many v = some v <|> pure []

其中empty是幺半群中的单位元素，<|>是幺半群中的二元运算符。some和many是两个函数（意义还不懂）

Alternative实例

[]
1
2
3
instance Alternative [] where
    empty = []
    (<|>) = (++)

和Monoid一样，单位元素是空列表，二元运算是列表合并

1
2
3
4
5
6
ghci> [1,2,3] <|> empty <|> [4,5]
[1,2,3,4,5]
ghci> some []
[]
ghci> many []
[[]]
Maybe
1
2
3
4
instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

Maybe作为Alternative的单位元素是Nothing，二元运算是始终取左边（当左边不为Nothing时）

1
2
3
4
5
6
ghci> Nothing <|> Just 1 <|> Just 2 
Just 1 
ghci> some Nothing
Nothing 
ghci> many Nothing 
Just []
ZipList
1
2
3
instance Alternative ZipList where
   empty = ZipList []
   ZipList xs <|> ZipList ys = ZipList (xs ++ drop (length xs) ys)
1
2
3
4
<>getZipList $ ZipList [1,2] <|> ZipList [3,4,5,6]
[1,2,5,6]
<>getZipList $ ZipList [1,2,3,4] <|> ZipList [3,4,5,6]
[1,2,3,4]

Alternative Laws

  • Monoid laws: 
    1
    2
    3
    empty <|> x = x 
    x <|> empty = x 
    (x <|> y) <|> z = x <|> (y <|> z)
  • Left zero law：empty <*> f = empty
    以上的定律是都满足都，下面的定律只有部分满足：
  • Right zero law：f <*> empty = empty （大部分包括Maybe、[]满足，IO不满足）
  • Left distribution：(a <|> b) <*> c = (a <*> c) <|> (b <*> c) （Maybe、[]满足，IO及大部分parsers不满足）
  • Right distribution：a <*> (b <|> c) = (a <*> b) <|> (a <*> c) （大部分不满足，但Maybe满足）
  • Left catch：(pure a) <|> x = pure a （Maybe、IO、parsers满足，但[]不满足）

常用函数

  • asum :: (Foldable t, Alternative f) => t (f a) -> f a，相当于foldr (<|>) empty： 
    1
    2
    3
    4
    ghci> asum [Nothing, Just 5, Just 3]
    Just 5
    ghci> asum [[2],[3],[4,5]]
    [2,3,4,5]
  • guard :: (Alternative f) => Bool -> f ()： 
    1
    2
    guard True  = pure ()
    guard False = empty

MonadPlus

1
2
3
4
5
6
class (Alternative m, Monad m) => MonadPlus m where
   mzero :: m a
   mzero = empty

   mplus :: m a -> m a -> m a
   mplus = (<|>)

MonadPlus实例

[]、Maybe都是MonadPlus的实例，mzero和mplus都由Alternative实现

MonadPlus Laws

  • Monoid laws
  • Left zero：mzero >>= f = mzero
  • Right zero：m >> mzero = mzero

常用函数

  • msum = asum
  • mfilter： 
    1
    2
    3
    mfilter p ma = do
        a <- ma
        if p a then return a else mzero

ArrowPlus

ArrowZero和ArrowPlus分别为Arrow设置了Monoid中的单位元素和二元运算符，使之成为了一个幺半群：

1
2
3
4
5
class Arrow arr => ArrowZero arr where
    zeroArrow :: b `arr` c

class ArrowZero arr => ArrowPlus arr where
    (<+>) :: (b `arr` c) -> (b `arr` c) -> (b `arr` c)

Reference

目录

#0 | 总章        
#1 | 基础语法与函数   
#2 | 高阶函数与模块   
#3 | 类型与类型类    
#4 | 输入输出与文件   
#5 | 函子、应用函子与单子
#6 | 半群与幺半群    
#7 | 一些其它类型类   
#A | Haskell与范畴论   

「Learn Haskell」#6 半群与幺半群

https://blog.tonycrane.cc/p/d4bb2633.html

作者

TonyCrane

发布于

2021-07-17

更新于

2021-07-25

许可协议

#
BiliBili主页

最新文章

归档

标签

AtCoder1
CSP-S2
CTF16
Cpp67
Haskell11
Linux1
Luogu5
NOIp33
Python1
RISC-V1
Rust2
SPOJ1
Writeup11
bfs1
blog2
bug2
dsu on tree1
git1
github3
hexo1
manim3
markdown3
mkdocs1
python5
spike1
图论2
学习2
左偏树1
差分约束1
并查集1
数据结构4
数论3
最大流1
最短路2
杂谈2
树状数组1
游记1
状态压缩1
生活3
笔记30
算法32
线段树1
网络流22
范畴论1
莫队5
计算几何1
费用流10
随笔3
题解36

分类

×