发表更新1 小时读完 (大约6844个字)0次访问

「Learn Haskell」#5 函子、应用函子与单子

Functors

函子（Functor）是一个类型类（typeclass），和其他类型类一样，它规定了其实例类必须实现的功能（例如Eq类型类规定了它的实例必须是可以比较是否相等的），Functor规定类它的实例必须是可以进行映射的。Functor要求使用fmap :: (a -> b) -> f a -> f b 函数来实现这个功能，它接收一个a -> b类型的函数、一个内部元素为a类型的函子，返回一个内部元素为b类型的函子

Functor可以比作盒子，那fmap函数就相当于给定一个函数和一个盒子，将盒子中的全部元素都应用这个函数，再返回应用函数后的盒子

函子的实例必须是一个Kind为* -> *的类型构造器，因为它要求其是一个盒子，盒子在接收内容后才会成为一个具体的类型。fmap中的f a和f b也是因为f是一个类型构造器，在接收类型a/b后才会变成一个具体类型（f a和f b）出现在函数类型声明中

Functor的定义是:

1
2
3
4
class Functor f where
    fmap :: (a -> b) -> f a -> f b
    (<$) :: a -> f a -> f b
    (<$) = fmap . const

可以发现Functor不仅需要fmap函数，还需要一个<$函数，它接收一个a类型的变量和一个内容为b类型的函子，返回一个内容为a类型的函子；作用就是将传入的函子中的所有元素都替换为传入的第一个参数，比如：

1
2
ghci> 'a' <$ [1, 2, 3]
"aaa"

但它不是声明一个函子实例必须的，因为它可以使用fmap和const函数复合来实现，其中const的类型签名：

const :: a -> b -> a

即接收两个参数，但始终只返回第一个参数

Functor实例

[]

列表[]是一个函子，它通过map函数来实现fmap的功能：

1
2
instance Functor [] where
    fmap = map

map :: (a -> b) -> [a] -> [b]

map和fmap要求的相同，达成的目的也一致。map接收一个函数和一个列表，它会将列表中的所有元素都应用这个函数后再返回这个列表

Maybe

Maybe也具有kind * -> *，它也是一个函子：

1
2
3
4
5
6
7
8
instance Functor Maybe where
    fmap f Nothing = Nothing
    fmap f (Just x) = Just (f x)

ghci> fmap (*2) Nothing
Nothing
ghci> fmap (*2) (Just 2)
Just 4

Either a

Either的kind是* -> * -> *，显然它不是函子，但是固定了一个传入类型的Either a的kind是* -> *，也是一个函子：

1
2
3
4
5
6
7
8
instance Functor (Either a) where
    fmap f (Left x) = Left x
    fmap f (Right x) = Right (f x)

ghci> fmap (*2) (Left 4)
Left 4
ghci> fmap (*2) (Right 4)
Right 8

因为使用Either时一般用右值表示正常结果，左值表示异常信息，所以使用fmap时只对右值进行操作，如果时左值则保持不变（而且左值此时也作为确定类型确定值存在）

IO

IO也是一个函子，使用fmap对IO中内容应用函数：

1
2
3
4
5
6
7
8
instance Functor IO where
    fmap f action = do
        result <- action
        return (f result)

ghci> fmap ("input: "++) getLine
test
"input: test"

(,) a

(,)表示一个二元组的类型构造器，(,) :: * -> * -> *，而确定了第一个元素的类型后就变成了(,) a，它的kind是* -> *。也是一个函子，进行fmap函数时只对第二个元素应用：

1
2
instance Functor ((,) a) where
    fmap f (x, y) = (x, f y)

只剩一个元素的三元组和四元组也都是函子，fmap也只对最后一个元素应用：

1
2
3
4
5
instance Functor ((,,) a b) where
    fmap f (a, b, c) = (a, b, f c)

instance Functor ((,,,) a b c) where
    fmap f (a, b, c, d) = (a, b, c, f d)

(->) r

->也是一个类型构造器，它的kind：

(->) :: * -> * -> *

一个映射（一元函数）的类型a -> b也可以写成(->) a b，它是由类型a和类型b输入到类型构造器->中后形成的一个具体类型。所以确定了输入类型后的一元函数的类型就是(->) r（其中r是输入的类型）

规定的fmap的类型签名是：

fmap :: (a -> b) -> f a -> f b

其中的f是函子，而在这个实例中(->) r就是函子，将其带入f可以得到：

fmap :: (a -> b) -> ((-> r) a) -> ((-> r) b)

把其中的(->)换成中缀可以得到：

fmap :: (a -> b) -> (r -> a) -> (r -> b)

传入两个函数，一个类型为a -> b，一个类型为r -> a，返回一个函数，类型为r -> b。
不难推测这个fmap是将这两个函数复合了，先对输入对r应用第二个函数产生类型a的结果，然后在应用第一个函数产生类型b的结果，所以(->) r定义的fmap是：

1
2
instance Functor ((->) r) where
    fmap f g = (\x -> f (g x))

所以(->) r的fmap其实就是函数复合(.)：

1
2
instance Functor ((->) r) where
    fmap = (.)
1
2
3
4
5
6
7
8
ghci> :t fmap (*3) (+100)  
fmap (*3) (+100) :: (Num a) => a -> a  
ghci> fmap (*3) (+100) 1  
303  
ghci> (*3) `fmap` (+100) $ 1  
303  
ghci> (*3) . (+100) $ 1  
303

Functor Laws

所有的函子都应该满足两个定律。这两个定律不是Haskell强制要求的，但应该确保一个函子满足这两个定律：

  1. fmap id = id（其中id为函数(\x -> x)）：即对一个函子fmap id，那它应该返回本身（fmap id a = id a = a，a为一个函子），比如： 
    1
    2
    3
    4
    ghci> fmap id [1, 2, 3]
    [1,2,3]
    ghci> fmap id (Just 2)
    Just 2
  2. fmap (f . g) = fmap f . fmap g：即函子的fmap支持结合律
    fmap (f . g) a = fmap f . fmap g $ a = fmap f (fmap g a)，其中a为一个函子
    fmap (f . g) (Just x) = fmap f (fmap g (Just x)) = fmap f (Just (g x)) = Just (f (g x)) 
    1
    2
    ghci> fmap ((*3) . (+100)) (Just 1)
    Just 303

满足第一个定律的函子一定满足第二个定律，所以只要检查函子是否满足第一个定律即可

Intuition

对于函子和fmap，有两种理解方法

  1. 函子是一种容器（container）；fmap接收一个函数和一个容器，在容器内部应用这个函数，返回应用后的新容器
  2. 函子是一种计算上下文（context）；fmap是柯里化的，把其类型签名看作

    fmap :: (a -> b) -> (f a -> f b)

    接收一个函数返回另一个函数，传入函数g :: a -> b，fmap将其转换为新的函数

    fmap g :: f a -> f b

    使普通的函数g可以在计算上下文f中使用，这种转换也被称为提升（lift）

常用函数

<$>

<$>函数是fmap的中缀形式（它看着类似$，f $ 3将f应用在单个值3上，而f <$> [1, 2, 3]将f应用在一个函子上，也就是应用在一个函子内部的所有值上）：

1
2
3
4
ghci> fmap (*2) (Just 2)
4
ghci> (*2) <$> Just 2
4

$>

$>函数包含在Data.Functor模块中

($>) :: Functor f => f a -> b -> f b

Functor定义时要求了<$函数，将函子内部的元素全部替换为指定的某个值，而$>正好将<$函数的两个参数反了过来，相当于flip (<$)：

1
2
3
4
ghci> 'a' <$ [1, 2, 3]
"aaa"
ghci> [1, 2, 3] $> 'a'
"aaa"

void

void函数也包含在Data.Functor模块中

void :: Functor f => f a -> f ()

void函数把一个函子内部的全部元素都变成空（()），void x相当于() <$ x：

1
2
3
4
ghci> void [1, 2, 3]
[(), (), ()]
ghci> void (Just 2)
Just ()

Applicative Functor

应用函子（Applicative Functor）是函子的升级版，它包含在Control.Applicative模块中。

fmap进行的操作是将一个普通一元函数应用在一个函子内部。而如果要将一个包含函数的函子应用在另一个函子上，fmap就处理不了了，但是应用函子的方法可以处理。应用函子的定义：

1
2
3
class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

应用函子要求实现两个函数：

  • pure :: a -> f a，不难理解，pure接收一个值，并将其放在默认的上下文/容器中。对于列表，pure = []；对于Maybe，pure = Just
  • <*> :: f (a -> b) -> f a -> f b，类似于fmap :: (a -> b) -> f a -> f b，但不同的是<*>的第一个参数的类型是f (a -> b)不是a -> b。所以<*>的第一个参数是在上下文中的函数，而不是一个普通函数。换句话说，<*>接收一个装有函数的函子和另一个函子，应用函数后返回新的函子。

Applicative Functor实例

Maybe

Maybe是一个应用函子：

1
2
3
4
instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something
  • pure函数：将一个值放在默认的上下文中，而对于Maybe，默认的上下文就是Just，所以pure x = Just x
  • <*>函数：将装有函数的函子中的函数应用另一个函子中
    • 第一个参数是Nothing，即第一个函子不包含函数，那返回的结果就也会是Nothing
    • 第一个参数是装有函数f的函子Just f，将其中的函数f应用在函子something中，只需要将f提取出来使用fmap应用在函子something中即可

实际应用的例子：

1
2
3
4
5
6
7
8
ghci> Just (+3) <*> Just 9
Just 12
ghci> pure (+3) <*> Just 9
Just 12
ghci> (+3) <$> Just 9
Just 12
ghci> Nothing <*> Just 9
Nothing

第一个例子，Just (+3)是一个包含函数(+3)的函子，将其应用在函子Just 9中，将Just (+3)中的函数(+3)提取出来，应用在Just 9中，得到了Just 12

第二个例子，可以发现，在这里pure (+3)和Just (+3)等效，因为pure将函数(+3)放在默认上下文中，也就是Just中了

而<*>能做的不止这些，他可以连续传入更多函子作为参数，比如：

1
2
3
4
ghci> pure (+) <*> Just 3 <*> Just 9
Just 12
ghci> pure (\x y z -> x + y + z) <*> Just 3 <*> Just 4 <*> Just 5
Just 12

<*>函数一样是默认左结合的，pure (+) <*> Just 3 <*> Just 9相当于(pure (+) <*> Just 3) <*> Just 9，而pure (+) <*> Just 3将(+)应用在Just 3上，得到的就是Just (+3)一个包含函数的函子，又将其通过<*>应用在了Just 9上，得到了Just 12:

1
2
3
4
5
  pure (\x y z -> x + y + z) <*> Just 3 <*> Just 4 <*> Just 5
= (pure (\x y z -> x + y + z) <*> Just 3) <*> Just 4 <*> Just 5
= (Just (\y z -> 3 + y + z) <*> Just 4) <*> Just 5
= Just (\z -> 3 + 4 + z) <*> Just 5 = Just (+7) <*> Just 5
= Just 12

所以可以使用类似pure f <*> x <*> y <*> …来将一个普通多元函数f应用在多个函子上。

而且pure f <*> x实际上先将普通函数f放在上下文中，然后执行<*>时再将其提取出来执行fmap，所以它就相当于将普通函数应用在函子x上，即fmap f x，也可以写成f <$> x。所以常用的写法就是：

f <$> x <*> y <*> ...

[]

列表也是一个应用函子：

1
2
3
instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]
  • pure函数：对于列表而言，一个值的最小上下文就是只包含这个值的列表[x]
  • <*>函数：列表的<*>函数是通过列表推导来实现的。因为不同于Maybe的Just只包含一个值，列表可以包含很多值，第一个传入的列表中可能会包含很多函数，第二个传入的列表也会包含很多值，所以就需要先从第一个列表中取出一个函数然后依次应用在第二个列表的每个值中，再取出第一个列表中的第二个函数应用在第二个列表的每个值中……最终返回得到的所有结果的列表

使用例子：

1
2
3
4
ghci> [(+3), (*2)] <*> [1, 2]
[4,5,2,4]
ghci> [(+), (*)]  <*>  [1, 2]  <*>  [3, 4]  
[4, 5, 5, 6, 3, 4, 6, 8]

IO

1
2
3
4
5
6
instance Applicative IO where
    pure = return
    a <*> b = do
        f <- a
        x <- b
        return (f x)

也不难理解，pure函数直接将传入的值return，相当于放在了IO的上下文中。而<*>函数先将两个IO中内容提取出来，然后应用函数后return，形成新的IO函子

1
2
3
4
ghci> (++) <$> getLine <*> getLine
Line1
Line2
"Line1Line2"

(->) r

(->) r同样也是一个应用函子，和函子的分析一样，先来分析它的<*>函数的类型签名：

<*> :: f (a -> b) -> f a -> f b

其中f为(->) r，将其代入并替换为中缀：

<*> :: (r -> a -> b) -> (r -> a) -> (r -> b)

可以看出它接收两个函数f :: r -> a -> b、g :: r -> a，返回另一个函数h :: (r -> b)

那么返回的函数的输入为r，输出为b，所以先对输入应用函数g得到a，然后在对r和a应用f得到b，所以推测<*>函数的操作就是：

\x -> f x (g x)

于是：

1
2
3
instance Applicative ((->) r) where
    pure x = (\_ -> x)
    f <*> g = \x -> f x (g x)

将一个值放在函数的上下文中，最小上下文就应该返回这个值本身，所以pure函数定义为(_ -> x)，即无论输入什么，都返回x

应用函子的<*>函数接收两个函子，返回一个新的函子。对于(->) r，它接收两个函数，返回一个新的函数。具体例子：

1
2
ghci> (+) <$> (+3) <*> (*100) $ 5
508

执行这句时发生了什么？：

1
2
3
4
5
6
7
8
  (+) <$> (+3) <*> (*100) $ 5
= ((+) <$> (+3)) <*> (*100) $ 5
= ((+) . (+3)) <*> (*100) $ 5 = (\a -> (+) ((+3) a)) <*> (*100) $ 5
= (\a b -> (a + 3 + b)) <*> (*100) $ 5
= (\x -> x + 3 + ((*100) x)) $ 5
= (\x -> x + 3 + x * 100) $ 5
= 5 + 3 + 5 * 100 = 508
= (5 + 3) + (5 * 100)

所以就相当于先对输入分别执行(+3)和(*100)，然后将两个结果执行了(+)

同样：

1
2
ghci> (\x y z -> [x,y,z]) <$> (+3) <*> (*2) <*> (/2) $ 5  
[8.0,10.0,2.5]

先对5分别执行(+3)、(*2)、(/2)，然后将得到的三个结果传入(\x y z -> [x,y,z])得到了最终的结果

1
2
  f <$> g <*> h <*> i
= (\x -> f (g x) (h x) (i x))

ZipList

普通列表实现的<*>函数是将每个函数应用在所有值上，但还有一种实现方法是将每个函数应用在对应值上，因为同一个类型不能存在同一函数的两种实现形式，所以引入了一个新的列表ZipList，包含在Control.Applicative模块中

1
2
3
instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

但是ZipList并不是Show的实例，所以不能直接显示出来，要使用getZipList来获取它内部的列表：

1
2
3
4
ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100..]  
[101,102,103]
ghci> getZipList $ (,,) <$> ZipList "dog" <*> ZipList "cat" <*> ZipList "rat"  
[('d','c','r'),('o','a','a'),('g','t','t')]

Applicative Functor Laws

应用函子一般有四个定律，都是保证pure的正确性的：

  1. Identity law：pure id <*> v = v
  2. Homomorphism：pure f <*> pure x = pure (f x)
  3. Interchange：u <*> pure v = pure ($ v) <*> u
  4. Composition：u <*> (v <*> w) = pure (.) <*> u <*> v <*> w

Intuition

理解应用函子的方式也是将其看作是计算上下文（context），比如要计算：
$$
[[\ \ g\ x_1\ x_2\ \cdots\ x_n\ \ ]]
$$

其中$x_i$的类型是$f\ t_i$，$f$是应用函子（看作上下文）。而函数$g$的类型是：

$$
t_1\to t_2\to\cdots\to t_n\to t
$$

所以双括号（idiom brackets）的作用是将一个普通函数应用在包含在上下文中的参数上。$g\ x_1$可以通过fmap来执行，将$g$提升（lift）到$x_1$的上下文中，然后应用在$x_1$上。但是fmap返回的结果是一个函子，换句话说，$g\ x_1$结果的类型是：

$$
f\ \ (t_2\to t_3\to\cdots\to t_n\to t)
$$

但是fmap并不能将上下文中的函数应用在上下文中的参数上，于是应用函子的<*>函数提供了这个方法，所以计算$[[\ g\ x_1\ x_2\ \cdots\ x_n\ ]]$，只需要：

g <$> x1 <*> x2 <*> ... <*> xn

而pure函数的作用就是将一个不在上下文中的值（函数或参数）提升到上下文中，但不进行其他操作。比如参数$x_2$如果不在上下文中，需要用pure提升到上下文中才能按上面计算：

g <$> x1 <*> pure x2 <*> ... <*> xn

常用函数

liftA & liftA2 & liftA3

liftA :: Applicative f => (a -> b) -> f a -> f b

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d

不难推测liftA就是fmap，liftA2 f x1 x2相当于f <$> x1 <*> x2，liftA3 f x1 x2 x3相当于f <$> x1 <*> x2 <*> x3

<* & *>

类型类似函子的<$和$>：

(<*) :: Applicative f => f a -> f b -> f a

(*>) :: Applicative f => f a -> f b -> f b

<*接收两个函子，如果两个函子中又一个为空，就返回空，否则返回的类型与第一个函子相同。*>反过来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ghci> Just 3 <* Just 4
Just 3
ghci> Just 3 *> Just 4
Just 4
ghci> Nothing <* Just 3
Nothing
ghci> Nothing *> Just 3
Nothing
ghci> [1, 2, 3] <* [3, 4]
[1,1,2,2,3,3]
ghci> [1, 2, 3] *> [3, 4]
[3,4,3,4,3,4]
ghci> [] <* [1, 2, 3]
[]
ghci> [] *> [1, 2, 3]
[]

<**>

(**) :: Applicative f => f a -> f (a -> b) -> f b

接收的参数是<*>反转过来的，即先接收一个参数函子，然后接收一个函数函子，在将其应用返回。但是和flip(<*>)不同，它先取参数函子的每个参数，然后再取函数函子中的函数逐个应用：

1
2
3
4
5
6
ghci> [(+1), (+2), (+3)] <*> [1, 2]
[2,3,3,4,4,5]
ghci> [1, 2] <**> [(+1), (+2), (+3)]
[2,3,4,3,4,5]
ghci> flip(<*>) [1, 2] [(+1), (+2), (+3)]
[2,3,3,4,4,5]

when & unless

when :: Applicative f => Bool -> f () -> f ()

传入的第一个是一个结果为Bool类型的测试，如果测试为True，则调用第二个参数，否则返回pure ()。（when函数在上文IO操作中使用过）

unless则与when相反，测试为True返回pure ()

sequenceA

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

应用在列表上时，它的类型相当于：

[f a] -> f [a]

所以在列表上它的使用方法：

1
2
3
4
5
6
7
8
9
10
ghci> sequenceA [Just 3, Just 2, Just 1]  
Just [3,2,1]  
ghci> sequenceA [Just 3, Nothing, Just 1]  
Nothing  
ghci> sequenceA [(+3),(+2),(+1)] 3  
[6,5,4]  
ghci> sequenceA [[1,2,3],[4,5,6]]  
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]  
ghci> sequenceA [[1,2,3],[4,5,6],[3,4,4],[]]  
[]

它在对同一个参数应用不同函数时很有用：

1
2
3
4
ghci> map (\f -> f 7) [(>4), (<10), odd]  
[True,True,True]  
ghci> sequenceA [(>4), (<10), odd] 7  
[True,True,True]

Monad

单子（Monad）是对Applicative Functor的扩展（但是诞生比Applicative早），Functor的<$>函数实现了将普通函数应用在上下文值上，Applicative的<*>函数将上下文中函数应用在上下文值上。而Monad提供了一个函数>>=（bind），将一个接收普通值返回上下文值的函数应用在上下文值上：

1
2
3
4
5
6
class Applicative m => Monad m where
    (>>=) :: m a -> (a -> m b) -> m b
    (>>) :: m a -> m b -> m b
    return :: a -> m a
    m >> n = m >>= \_ -> n
    return = pure
  • return函数：和pure一样，只是有另一个名字
  • >>函数：提供了默认的实现方法，它的作用和Applicative的*>函数一样
  • >>=函数（bind）：比Applicative升级的函数，第一个参数是一个单子，第二个参数是一个接收值返回单子的函数，将这个函数应用在第一个参数单子中的值上，并返回得到的新单子

Monad实例

Maybe

Maybe是一个单子实例，Applicative已经为它实现了return，因此只需要>>=函数：

1
2
3
instance Monad Maybe where
    (Just x) >>= f = f x 
    Nothing  >>= _ = Nothing

根据定义就很容易实现Maybe的>>=函数了，而且也很好理解

1
2
3
4
5
6
7
8
ghci> Just 1 >>= \x -> Just (x + 1)
Just 2
ghci> Just 1 >>= \x -> return (x + 1)
Just 2
ghci> Nothing >>= \x -> Just (x + 1)
Nothing
ghci> Just 1 >>= \x -> Just (x + 1) >> Nothing >>= \y -> Just (y + 1)
Nothing

最后一个例子中出现了>> Nothing，这时Nothing前的部分全都相当于没用，因为>>操作符的左右两边只要有一个出现Nothing，那整体就会是Nothing。这个特性可以用于在中途随时判断失误，只要有一处失误，结果就会是Nothing

[]

列表也是一个单子：

1
2
instance Monad [] where
    xs >>= f = concat (map f xs)

将这个函数应用在xs的每个值上，将返回的所有列表平铺成一个列表：

1
2
3
4
ghci> [3,4,5] >>= \x -> [x,-x]  
[3,-3,4,-4,5,-5]  
ghci> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)  
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

IO

IO也是一个单子，但是实现方法比较深奥（逃

(->) r

(->) r也是一个单子，和Functor、Applicative一样，先分析它的>>=类型签名：

(>>=) :: (-> r) a -> (a -> (-> r) b) -> (-> r) b

(>>=) :: (r -> a) -> (a -> r -> b) -> (r -> b)

也可以看出来，它接收两个函数f :: r -> a、g :: a -> r -> b，然后返回一个新的函数h :: r -> b

那么函数h接收一个类型为r的参数，返回一个类型为b的值。所以先对输入应用f得到类型为a的中间值，然后再将这个值和输入参数一起传入函数g得到结果。所以函数h的定义应该是：

\x -> g (f x) x

1
2
instance Monad ((->) r) where
    f >>= g = \x -> g (f x) x
1
2
3
4
ghci> (+3) >>= (+) $ 1
5
ghci> (+) <$> (+3) <*> id $ 1
5

do-notation

Haskell的do语句为链式的>>=应用提供了类似命令式（imperative style）的语法糖。比如a >>= \x -> b >> c >>= \y -> d：

1
2
3
4
a >>= \x ->
b >>
c >>= \y ->
d

其中有abcd四个值，可以看出a中内容绑定到了x上，c中内容绑定到了y上。使用do语句来表示这个操作可以写成：

1
2
3
4
5
do { x <- a 
   ;      b 
   ; y <- c 
   ;      d 
   }

其中的大括号和分号可以省略不写（挤在一行时不能省略）。do语句也只是一个语法糖，它可以递归地转换成普通的Monad操作语句：

  • do e：e
  • do { e; ... }：e >> do { … }
  • do { v <- e; ... }：e >>= \v -> do { … }
  • do { let ...; ... }：let … in do { … }

ApplicativeDo

比如如下一个do语句：

1
2
3
4
do x <- a 
   y <- b 
   z <- c 
   return (f x y z)

它可以转化成：

a >>= \x -> b >>= \y -> c >>= \z -> return (f x y z)

但是经过观察可以发现，整个语句实际上将函数f应用在了三个上下文中的值上，所以仅用Applicative的<$>和<*>完全可以实现：

f <$> a <*> b <*> c

而且在运行的时候Applicative的效率会比Monad高，所以Haskell会将do语句尽可能优先转换为Applicative的表示方法然后再计算

Monad Laws

  1. Left identity： return a >>= k = k a
  2. Right identity：m >>= return = m
  3. Associativity：(m >>= g) >>= h = m >>= (\x -> g x >>= h)

前两个定律很好理解：

  • 将a注入上下文之后绑定（bind）给函数k(:: a -> m a)，相当于直接将a直接传入函数k
  • 将已经包含在上下文中的值绑定给return函数，相当于保持不变

第三个定律是结合律，把它写成更像结合律的表示方法是：

(m >>= (\x -> g x)) >>= h = m >>= (\x -> g x >>= h)

组合运算符（>=>）形式

Control.Monad模块中还定义了函数>=>（Kleisli-composition operator）：

1
2
3
infixr 1 >=>
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g

使用>=>运算符可以将两个用于绑定的函数结合在一起。用它表示的Monad定律更加清晰直观：

  1. Left identity：return >=> f = f
  2. Right identity：f >=> return = f
  3. Associativity：(f >=> g) >=> h = f >=> (g >=> h)

do-notation形式

Monad的这三个定律还可以使用do语句来描述：

  1. Left identity： 
    1
    2
    3
    do { x' <- return x;
         f x'             =   do { f x } 
       }
  2. Right identity： 
    1
    2
    3
    do { x <- m; 
         return x         =   do { m }
       }
  3. Associativity： 
    1
    2
    3
    4
    5
    do { y <- do { x <- m;       do { x <- m;              do { x <- m;
                   f x                do { y <- f x;            y <- f x;
                 }           =             g y         =        g y
         g y                             }                    }
       }                            }

Intuition

Monad也可以很自然地看成Applicative的升级版，比如Applicative的操作全部是固定的，而Monad的操作可以在中途突然改变

同时Monad也完成了Functor和Applicative无法完成的操作。比如要用fmap和实现>>=函数（即达成操作 m a -> (a -> m b) -> m b），先假设 f :: a -> m b，那么fmap f的类型就会是 m a -> m (m b)，将m a应用在fmap f上会得到结果m (m b)，而不是m b。但是目前只可以使用pure将一个值装入上下文中（a -> m a），而没有一个函数可以从上下文中提取值（m a -> a）。那么就需要定义一个新的函数来实现这个操作的效果（m (m b) -> m b）。因此Monad的另一个等效的定义方法是：

1
2
3
4
5
class Applicative m => Monad' m where
    join :: m (m a) -> m a 
    
    (>>=) :: m a -> (a -> m b) -> m b 
    x >>= f = join $ fmap f x

但是定义>>=函数会更为直观方便，所以Haskell采用了用>>=函数定义Monad的方法

同时Haskell还提供了join函数的定义：

1
2
join :: Monad m => m (m a) -> m a 
join x = x >>= id

常用函数

liftM & ap

liftM :: Monad m => (a -> b) -> m a -> m b

ap :: Monad m => m (a -> b) -> m a -> m b

所以liftM其实就是fmap、ap就是<*>，但是老版本的GHC定义Monad并没有Functor、Applicative的约束，所以实现了liftM、ap，并且保留了这个名字

因此一个单子也可以通过pure = return、(<*>) = ap直接成为应用函子的实例

sequence

sequence :: Monad m => [m a] -> m [a]

sequence的作用显而易见，而且在IO部分也使用到了。但是这个版本是在GHC.Base模块中定义的，还有一个更广泛的使用Traversable的定义在Data.Traversable模块中

replicateM

replicateM :: Applicative m => Int -> m a -> m [a]

mapM & forM

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

forM :: Monad m => [a] -> (a -> m b) -> m [b]

forM的用法在IO部分已经说过，mapM和forM都在Data.Traversable模块中有广泛版本

还有一些其他的函数：filterM、zipWithM、foldM、forever，通过名字就可以看出用法，是将原来仅使用与列表的函数提升至可以适用于所有单子

并且在函数名后加下划线，比如sequence_、mapM_，会忽略返回值（最终结果为m ()）

=<< & >=> & <=<

（>=>操作符在上面Monad Laws部分已经给出了定义）

  • x >>= f = f =<< x
  • f >=> g = g <=< f

MonadFail

MonadFail定义在Control.Monad.Fail模块中：

1
2
class Monad m => MonadFail m where
    fail :: String -> m a

它只要求在Monad的基础上实现fail函数，接收一个字符串返回一个单子。这会使在do语句中产生错误时直接变为错误值（空值）使最终的返回值为错误值

MonadFail实例

1
2
3
4
5
6
7
8
instance MonadFail Maybe where
    fail _ = Nothing

instance MonadFail [] where
    fail _ = []

instance MonadFail IO where
    fail = failIO

Maybe和[]的fail函数都与第一个参数无关，直接返回空值（Nothing、[]）；而IO的fail函数直接使用failIO，实现方法也是深奥（接着逃

1
2
3
4
5
6
7
exampleFail :: Maybe Char 
exampleFail = do
    (x:xs) <- Just ""
    return x 

ghci> exampleFail
Nothing

在这个例子的do语句中，在提取Just “”中的值时用了模式匹配，但是因为其内容为空字符串，x:xs匹配会出现错误，这时就会触发fail函数直接返回Nothing

MonadFail Law

  • fail s >>= m = fail s

Reference

目录

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

「Learn Haskell」#5 函子、应用函子与单子

https://blog.tonycrane.cc/p/290ecb74.html

作者

TonyCrane

发布于

2021-07-09

更新于

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

分类

×