β

Monadic Function_Haskell笔记12

黯羽轻扬 22 阅读

liftM

liftM :: Monad m => (a1 -> r) -> m a1 -> m r

从类型声明来看,这不就是 Functor fmap 嘛:

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

只是把context换成了 Monad 而已,此外没什么区别。并且对于遵守Functor laws和Monad laws的类型,这两个函数是 完全等价 的,例如:

> liftM (+1) (Just 1)
Just 2
> fmap (+1) (Just 1)
Just 2

liftM 的具体实现如下:

liftM   :: (Monad m) => (a1 -> r) -> m a1 -> m r
liftM f m1              = do { x1 <- m1; return (f x1) }

等价于:

liftM' f m = m >>= \x -> return (f x)

注意,这个实现并不依赖 Functor 的特性,仅靠 Monad 具有的行为就可以完成(并且如果遵守Monad laws的话,就与 fmap 完全等价,仅将函数应用到具有context的值上,不做任何多余的事情),从这个角度看, Monad Functor 更强大

已经证明了 Monad Functor 强,那 Applicative 呢?

Applicative 最关键的是这个东西:

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

实际上用 Monad 也能实现,叫做 ap

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

很容易搞定:

mf `ap'` m = do
  f <- mf
  x <- m
  return (f x)

所以, Monad 还比 Applicative 强大 。更进一步的,如果要实现自定义 Monad ,可以先实现 return >>= ,然后就很容易实现 Applicative (令 <*> = ap pure = return )和 Functor (令 fmap = liftM

我们知道有 liftA2 (直到 liftA3 ),用来应对“多参”函数:

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

实际上也有对应的 liftM2 (直到 liftM5 ):

liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r

例如:

> liftM2 (+) (Just 1) (Just 1)
Just 2
> liftM3 (\x y z -> x + y + z) (Just 1) (Just 2) (Just 3)
Just 6

fmap 推及 liftM ,再到 liftM5 就很容易理解了

join

可能会面临monadic value的value还是monadic value的场景,例如:

Just (Just 1)

那么如何取出内层的monadic value呢?可以用 join 函数:

join :: Monad m => m (m a) -> m a

试玩一下:

> join (Just (Just 1))
Just 1
> join Nothing
Nothing
> join (Just (Just (Just 1)))
Just (Just 1)

注意,类型上要求内层和外层的 Monad 相同(都是 m ),所以 join (Just [1]) 之类的是无法正常工作的

从上面 Maybe 的示例来看, join 好像没什么实际意义,再看看其它 Monad

> join [[1, 2], [3], [4, 5]]
[1,2,3,4,5]
> join (writer (writer (1, "a"), "b")) :: Writer String Int
WriterT (Identity (1,"ba"))

有点join(连接)的意思了 ,取出内层monadic value之后似乎还做了运算。猜测是这样:

join' mm = do
  m <- mm
  m

等价于:

join'' mm = mm >>= (\m -> m)
-- 即
join'' mm = mm >>= id

那内层List是被谁连接起来的呢?因为List的 >>= 实现是List Comprehension:

xs >>= f             = [y | x <- xs, y <- f x]

所以在List的场景,等价于:

joinList xss = xss >>= (\xs -> xs)
joinList' xss = [y | x <- xss, y <- id x]

Writer 的场景与List类似,运算都是由 >>= 完成的,而 Maybe 不带运算也是因为其 >>= 实现:

(Just x) >>= k      = k x
Nothing  >>= _      = Nothing

join 中的 k 就是 id ,所以仅原样取出内层 Maybe

P.S.另外, 一个有趣的东西

m >>= f = join (fmap f m)

也就是说 >>= 等价于用转换函数( f :: a -> m b )对monadic value( m )做映射,得到一个monadic monadic value,再通过 join 取出内层monadic value就是最终结果:

> fmap (\x -> return (x + 1)) (Just 1) :: Maybe (Maybe Int)
Just (Just 2)
> join (Just (Just 2))
> Just 2
> Just 1 >>= (\x -> return (x + 1))
Just 2

实际上, 这个等价关系提供了另一种实现 >>= 的思路 ,只要实现 join 就好了。这在实现自定义Monad instance的时候尤其好用,如果不知道该如何实现 >>= 才能保证Monad laws,不妨换个角度,考虑去实现能把嵌套的monadic value打平的 join

filterM

类似于普通的 filter

filter :: (a -> Bool) -> [a] -> [a]

filterM 长这样:

filterM :: Applicative m => (a -> m Bool) -> [a] -> m [a]

注意,predicate函数( a -> m Bool )的 Bool 返回值具有context了,这有什么作用?

允许在过滤过程中加入context,并且会被保留到结果( m [a] )中。例如:

> graterThan2 = filterM (\x -> if (x > 2) then writer (True, [show x ++ " reserved"]); else writer (False, [show x ++ " discarded"])) [9, 5, 0, 2, 1, 3] :: Writer [String] [Int]
> fst . runWriter $ graterThan2
[9,5,3]
> mapM_ putStrLn (snd . runWriter $ graterThan2)
 reserved
 reserved
 discarded
 discarded
 discarded
 reserved

在对List进行过滤的同时,利用 Writer Monad 记录了操作日志,尤其是 被丢掉的元素也记下了相关信息 (例如 0 discarded ),很有意思

还有 更有趣的用法

powerset :: [a] -> [[a]]
powerset = filterM (\x -> [True, False])

定义了一个奇怪的函数,接受一个数组,返回一个二维数组,试玩一下:

> powerset [1, 2, 3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

从作用上来看是个求幂集(集合的所有子集组成的集合,包括空集和自身)的函数,考虑一下 filterM 是如何做到的?

predicate函数 \x -> [True, False] 同时返回了多个结果:保留和丢掉。又是List的 non-deterministic语境的应用

[a]代表同时有好多结果的computation(non-deterministic computation)

non-deterministic计算能够产生多个结果,因此,对 powerset 场景而言,求幂集的一种有效方式是:遍历集合中的每个元素,进行两种操作(保留它和丢掉它),并把操作结果收集起来

再看 filterM 的实现:

filterM          :: (Applicative m) => (a -> m Bool) -> [a] -> m [a]
filterM p        = foldr (\ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x)) (pure [])

(摘自 Control.Monad

foldr 遍历数组,初始值为 pure [] ,累加函数(accumulator)是 \ x -> liftA2 (\ flg -> if flg then (x:) else id) (p x) ,对当前元素用 liftA2 做映射,视 p x 的结果返回 x: id (保留的话,把当前元素插入到结果集;丢掉的话,结果集保持原状)

看起来比较迷惑 ,补全参数后,实际上是这样:

\ x ma -> liftA2 (\ flg a -> if flg then (x: a) else id a) (p x) ma

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b 接受一个二元函数,其参数顺序是当前元素和累加结果(分别对应上面的 x ma ma 的初始值是 pure [] ), liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c 能够把一个二元函数应用到两个monadic value(分别是 p x ma )上,再返回一个monadic value。最后,这些monadic value被 foldr 通过 mappend 折叠起来得到最终结果

P.S.没错, foldr 的实现用到了 foldMap :: Monoid m => (a -> m) -> t a -> m ,具体见 Data.Foldable

foldM

foldl 对应的monadic版本叫 foldM

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b

例如:

> foldl (\a x -> a + x) 0 [1..10]

P.S.一个小细节, foldl foldr 的累加函数的参数顺序是相反的,前者是 a v ,后者是 v a

如果希望给 foldl 添上一个计算语境(比如可能会失败的语境),用 foldM 能够轻松搞定:

> foldM (\a x -> if (a > 99) then Nothing; else Just (a + x)) 0 [1..10]
Just 55
> foldM (\a x -> if (a > 99) then Nothing; else Just (a + x)) 0 [1..100]
Nothing

这个场景假定求和超过 99 的话,认为大数溢出,计算失败

猜一下 foldM 的实现:

foldM' acc a xs = foldl (\ma v -> ma >>= (\a -> acc a v)) (return a) xs

关键点在于 维护累加值的context ,参与运算(喂给 acc )时去掉,遍历时添上。标准(库)答案是这样的:

foldM          = foldlM
foldlM f z0 xs = foldr f' return xs z0
  where f' x k z = f z x >>= k

等等, f z x >>= k 发生了什么?

f是累加函数
z0是初始值
xs是Foldable实例
z是累加值
x是当前元素
k是?像是return,接受普通值,返回具有context的值

一步步看,其中 f' 的类型是:

f' :: Monad m => t -> (a -> m b) -> a -> m b

foldr 的类型是:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

最难以捉摸的是:

(foldr f') :: (Foldable t, Monad m) => (a -> m b) -> t t1 -> a -> m b

这一步发生了什么?

如果只喂给 foldr 一个参数,要求是个二元函数 a -> b -> b ,要求第二个参数和返回值类型相同,所以应该 换个姿势看 f'

f' :: Monad m => t -> (a -> m b) -> (a -> m b)

此时 b 相当于 a -> m b ,对应到 foldr 中:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
--  (a -> b -> b)被f'填上了,剩下b -> t a -> b,把b替换成a -> m b
foldr f' :: Foldable t => (a -> m b) -> t a -> (a -> m b)
-- 即
(foldr f') :: (Foldable t, Monad m) => (a -> m b) -> t t1 -> a -> m b

接下来喂给它3个参数,分别是:

return :: (a -> m b)
xs :: t t1
z0 :: a

顺利返回 m b

P.S.之所以能进行这样巧妙的变换,是因为Haskell函数默认的柯里化特性,只有填满参数,才返回值。所以:

f' :: Monad m => t -> (a -> m b) -> a -> m b
-- 等价于
f' :: Monad m => t -> (a -> m b) -> (a -> m b)

理解起来也很容易, f' :: Monad m => t -> (a -> m b) -> (a -> m b) 接受两个参数,返回一个 a -> m b 的函数(之前是接受3个参数,返回一个 m b 值)

类似的,可以这样做:

f :: (Num b, Monad m) => b -> (t -> t1 -> m b) -> t -> t1 -> m b
f a b c d = b c d >>= \v -> return (v + a)

foldr f 对应的类型为:

foldr f :: (Foldable t, Num b, Monad m) => (t1 -> t2 -> m b) -> t b -> t1 -> t2 -> m b

试玩:

> foldr f (\x y -> return (x + y)) [1..10] 0 0

P.S.受标准答案的启发,可以换一下参数顺序,减少一层lambda:

foldM'' acc a xs = foldr (\v ma -> ma >>= acc v) (return a) xs

组合

我们知道函数可以组合:

(.) :: (b -> c) -> (a -> b) -> a -> c

f . g . h 就是从右向左组合,例如:

> ((+1) . (/2) . (subtract 1)) 7
.0

monadic function也是function,自然也能组合(实际上之前已经见过了)

在Monad laws中有提到过一个东西,叫做 Kleisli composition

-- | Left-to-right Kleisli composition of monads.
(>=>)       :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g     = \x -> f x >>= g
(<=<)       :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(<=<)       = flip (>=>)

<=< 就是 . 的monadic版本,作用也类似:

> Just 7 >>= (return . (+1) <=< return . (/2) <=< return . (subtract 1))
Just 4.0

用来组合一系列 Monad m => a -> m a 的函数,组合顺序也是从右向左

作者:黯羽轻扬
原文地址:Monadic Function_Haskell笔记12, 感谢原作者分享。