Monadic Function_Haskell笔记12
感谢支持ayqy个人订阅号,每周义务推送1篇(only unique one)原创精品博文,话题包括但不限于前端、Node、Android、数学(WebGL)、语文(课外书读后感)、英语(文档翻译) 如果觉得弱水三千,一瓢太少,可以去 http://blog.ayqy.net 看个痛快
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 rliftM 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 rliftM3 :: 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 NothingNothing> 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 IntWriterT (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 xNothing >>= _ = 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)9 reserved5 reserved0 discarded2 discarded1 discarded3 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 -> bfoldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
例如:
> foldl (\a x -> a + x) 0 [1..10]55
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 = foldlMfoldlM 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 bfoldr 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 t1z0 :: 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 bf 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 055
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)) 74.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的函数,组合顺序也是从右向左
更多相关文章
- 我在一个构造方法中写了30个参数,老板看了想骂人
- 函数式编程中如何处理副作用?
- Java线程池-当任务渐增时的处理-各个参数的含义
- JVM 常用配置参数(Java 8)
- 构造方法的参数太多,如何解决?
- 从代码的改进,看参数行为化与Lambda
- 帆软报表自定义函数-取json数据
- PHP-FPM参数调优
- springboot 读写 session 交互参数