浅释Functor、Applicative与Monad

引言

转入Scala一段时间以来,理解Functor、Applicative和Monad等概念,一直是我感到头疼的部分。虽然读过《Functors, Applicatives, And Monads In Pictures》 一文,但深感未得甚解,仍是翻书了然、关书茫然。

于是转而“曲线救国”——选择学习更加纯粹的FP语言Haskell,尝试结合着对范畴论的一点粗鄙理解,再从Haskell与Scala不同编码实现的角度去比较,结果真有柳暗花明又一村的感觉。参考书籍为著名的《趣学Haskell》,与Scala的红皮书相比,其循循善诱的推导过程非常有特色。这份笔记,便撷取了其中我最关心的部分。

当然,限于个人关于范畴学知识的贫瘠,文中错漏之处还待日后逐渐修补完善。

List Comprehension

List Comprehension,非常类似数学中集合的表达形式:[ 元素 | 值域, 可选的过滤条件 ],直观而且高效,所以引起了我的极大兴趣。

[ (a, b, c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 > c^2 ]

换作Scala的语法:

for {
  c <- 1 to 10
  b <- 1 to c
  a <- 1 to b
  if (a^2 + b^2 > c^2)
} yield (a, b, c)

Type Class

定义函数

Type Class,是实现ADT的主要工具,类似于OOP中的Interface,是一组行为(函数)的组合,支持泛型及其约束等。自定义Type Class时,要注意泛型的类型不能关联具体行为,从而影响函数的行为,而和OOP定义接口的原则一样,应体现其行为的抽象共性。这样的泛型函数常见定义形式为:function_name :: (generalized_type_name type_var) => param_1_type -> param_2_type -> return_type

空格、=、->、=>以及::是Haskell的常见分隔符,函数参数之间既没有逗号分配,参数与返回值之间也没有括号分隔。紧跟定义之后的若干行,则是具体的函数体,此处可适用模式匹配。为方便理解,函数体=左边可以理解为调用时的参数结构(当匹配多个变量时需要用括号括起),右边则是返回值。

weekday :: (Integer a) => a -> String
weekday 1 = "Monday"
weekday 2 = "Tuesday"
weekday x = "Not valid value."

换作近似于Scala的语法:

def weekday[A](a: A):String = a match {
  case 1 => "Monday"
  case 2 => "Tuesday"
  case _ => "Not valid value."
}

模式匹配既可换用Guards实现,在内部可以使用关键字let定义表达式、用where定义局部变量,还可以使用case语句实现。

Curried

在函数定义中,理解柯里化Curried的概念是关键,即所有的多参数函数经过Curried之后,都可以表达为接受一个参数,返回一连串单个参数函数的函数。需要与“不全调用的函数”(Partially Function)稍作区别。严格讲,柯里化得到的是一连串单参数的函数,而不全调用是得到“切掉头”之后,以剩余若干个参数为参数的一个函数。这是Haskell用->分隔参数和返回值类型的原因,非常直观。虽与Scala有语法形式上的差异,但在把函数作为一等公民这件事上没有实质区别。同时,在Haskell中提供了λ——lambda表达式作为实现闭包的重要工具:(\param_1 param_2 -> expression),这和Scala中的(param_1, param_2) => { expression }是一致的。有了Curried,便可以象做一次函数的习题一样,将一个函数两边的相同参数约去,得到这样的不全调用函数。

理解了Curried,对mapfilterfold这几个遍历(map over)某种同质数据结构(比如List)的万能工具,便会更容易理解了。

Kind

进一步的,由于Haskell将Type Class的类型构造子也视作函数,从而在Curried基础上引申出另一个概念——Kind,即Type Class的类型。理解这个概念,对理解某个Type Class及其函数的类型大有裨益,尤其在作类型推断时的帮助特别明显。用*表示一个具体类型(与抽象的泛型对应)对应的Kind,则Integer -> String这样的类型的Kind为* -> *。至于Maybe A(同Scala中的Option[A])这样的泛型,其具体实现类型如Maybe String的Kind为*,抽象的Maybe本身Kind为* -> *。同理,Either String Integer的Kind为*Either[String]的Kind为* -> *,Either的Kind为* -> * -> *。所以简单地的来说,可以从左到右把每个*都当作一个类型参数对应的类型,那么每确定一个具体的类型参数,就如同打开了一层套娃,直到只剩最后一个*时才能获得一个具体的类型。

先看一个简单的例子:

class Tofu t where
  tofu :: j a -> t a j

对Type Class Tofu需要填入的类型t的Kind推导过程如下:

  1. j a作为tofu的参数可知,其类型对应的Kind为*
  2. 假设a的Kind为*,则j的Kind为* -> *
  3. t a j作为tofu返回值可知,t将是一个接受aj两个类型参数的类型
  4. 综上,代入a和j的Kind,得到t的Kind为* -> (* -> *) -> *,只有填入符合该Kind约定的类型,才能得到一个实例化的Tofu类型

接着是稍复杂一些的例子:

data Barry t k p = Barry { yabba :: p, dabba :: t k }

对类型Barry的Kind推导过程如下:

  1. yabba :: p可知,类型p的Kind为*
  2. dabba :: t k可知,类型k的Kind为*
  3. 由2可知,类型t的Kind为* -> *
  4. 综上,类型Barry的Kind根据t k p的定义顺序,即为(* -> *) -> * -> * -> *

然后再看看如何将这个类型定义为Functor,即要给Functor填入怎样的一个Barry实现,才算符合Functor的定义。因为Functor希望置入类型的Kind为* -> *,所以在定义时需要利用Curried的原理把Barry中处于前两位的t和k先固定了,留下Barry最右边的p作为对应Functor置入类型Kind左边的那个*,这样才能保证应用Functor得到具体的类型。进而需要思考的是负责map over的函数fmap,需要推断其参数f作用在Barry的哪个类型参数上。由于y由k代入t所得,所以f作用的只能是所有x出现的地方,于是得到如下的推导实现。

instance Functor (Barry t k) where
  fmap f (Barry { yabba = x, dabba = y }) = Barry { yabba = f x, dabba = y }

相较Haskell定义Type Class的语法,Scala稍显繁复,但两者的思考方式都是定义ADT“是什么”而不是“怎么样”。以Either为例,Haskell的定义如下:

data Either e a = Left e | Right a

Scala则需要定义一个trait,然后是若干派生的、对应于具体实现的不同case class或者object,然后要把函数与ADT结构剥离,单独定义其函数原型及相应的解释器:

trait Either[E, A] { ... }
case class Left[E] extends Either[E, None] { ... }
case class Right[A] extends Either[None, A] { ... }

再看个稍复杂些的排序二叉树实现:

data Tree a = Empty | Node a (Tree a) (Tree a)

singleton :: a -> Tree a
singleton x = Node x Empty Empty

insert :: (Ord a) => a -> Tree a -> Tree a
insert x Empty = singleton x
insert x (Node a left right)
  | x == a = Node x left right
  | x < a  = Node a (insert x left) right
  | x > a  = Node a left (insert x right)

let tree = foldr insert Empty [2, 3, 8, 5, 4, 11, 6]

对应的Scala实现(简化为结点值为整数的二叉树):

trait Tree
object Empty extends Tree
case class Node(a: Int, left: Tree, right: Tree) extends Tree

def insert(x: Int, tree: Tree): Tree = tree match {
  case Empty => Node(x, Empty, Empty)
  case Node(a, left, right) => {
    if (x == a) tree
    else if (x < a) Node(a, insert(x, left), right)
    else if (x > a) Node(a, left, insert(x, right))
  }
}

val tree = [2, 3, 8, 5, 4, 11, 6].foldRight(Empty: Tree)((x, tree) => insert(x, tree))

这是书中逆波兰后缀表示法的Scala实现示例:

def calculateRPN(expression: String): Float = {
  expression.split("""\s""")
    .foldLeft(Nil: List[Float])((list, s) => (list, s) match {
      case (x :: y :: ys, "*") => y * x :: ys
      case (x :: y :: ys, "/") => y / x :: ys
      case (x :: y :: ys, "+") => y + x :: ys
      case (x :: y :: ys, "-") => y - x :: ys
      case (x :: xs, "ln") => math.log(x).toFloat :: xs
      case (xs, "sum") => List(xs.sum)
      case (xs, x) => x.toFloat :: xs
    })
    .head
}

val r = calculateRPN(expression = """90 34 12 33 55 66 + * - + -""")

Monoid

Monoid结构对应范畴论中的幺半群,说着挺玄,其实还算简单。只要具备以下2个特征,就可以说它是Monoid。

  • 同一律: 它一定得有个用于占位的初始元素,或者说代表什么也没有的空值。这在范畴论中被称作幺元——Identity,“幺半群”的便来源于此。该群-的某个元素x-与这个这个占位值-作运算,其结果都将等于x。比如,整数-加法-中的-0,整数-乘法-中的-1,List-联结运算-中的-空列表Nil,String-联结运算-中的-空字符串"",逻辑-“与”运算-中的-真值True。

  • 结合律: 它一定得有个可以将该群2个元素结合在一起,得到该群另一个元素的结合函数,形式如X1+X2=X3,这是半群的特征(“一半”合“一半”便等于一个)。比如,整数2 + 整数3 = 整数6,整数2 × 整数3 = 整数6,列表[1,2,3]联结列表[4,5,6]得到列表[1,2,3,4,5,6],字符串"abc"联结字符串"def"得到字符串"abcdef",逻辑值False逻辑值True得到逻辑值False。

据此,我们可以得到如下这样的Monoid定义。identity对应第一个特征——幺元,associate对应第二个特征——结合函数。

class Monoid a where
  identity :: a
  associate :: a -> a -> a

对应的Scala实现:

trait Monoid[A] {
  def identity: A
  def associate(a1: A, a2: A): A
}

由于结合律的存在,所以Monoid的实例都具有可折叠的特性,想想fold一个一长串的列表然后得到一个值的场景。而且只要折叠所用的结合函数不变,使用何种折叠顺序(从左至右、从右至左、分段折叠等等)均不影响最后得到的值,因此Monoid结合律成为实现可并行的Map-Reduce操作的基础。更进一步地,由于多个Monoid实例可以被组装成为一个Monoid,而被组装的每个实例都带有不同的结合函数,所以可以利用这种特性,在进行折叠操作时同时执行多种不同的计算,从而提高并行计算的效率。

在Scala小红书中,有关于Map的一个组装实现:

def mapMergeMonoid[K, V](V: Monoid[V]): Monoid[Map[K, V]] = {
  new Monoid[Map[K, V]] {
    def idenity = Map[K, V] ()
    def associate(a: Map[K, V], b: Map[K, V]) = {
      (a.keySet ++ b.keySet).foldLeft(identity) {
        (acc, k) => acc.updated(k, V.associate(a.getOrElse(k, V.identity),
                                            b.getOrElse(k, V.identity)))
      }
    }
  }
}

Functor

Haskell实现:

class Functor f where
  map :: (a -> b) -> f a -> f b

对应的Scala实现:

trait Functor[F[_]] {
  def map[A, B](f: A => B): F[A] => F[B]
}

范畴——最简单的理解,就是2个不同集合以及集合之间的映射关系构成的整体。比如,如果我们把A看作Integer、B看作String、(f: A => B)看作toString(),那么由这三者即构成一个范畴C1。那么根据Functor的定义,我们通过map可以得到一个新的范畴C2:F[A] => F[B],封装结构F[_]中包裹的元素与范畴C1中一一对应,这便是为什么Picture系列的文章喜欢用盒子来作比喻的原因了。

需要说明的是,我选择了F[A] => F[B]这样的经过Curried的形式来表达函数操作的结果。这是我认为最能直观反映映射关系的形式,在以下Applicative和Monad中也是如此。借助这样的定义,就可以把它们简单理解为如何以不同形式(对应不同的应用条件和场合),在F[A]F[B]之间建立联系,从而完成一个范畴的定义。由于Haskell的语法,我之前会误把f当作传入的一个函数而不是类型(尽管类型构造子确实也是函数),导致经常转不过弯来。

于是根据Scala的定义,Functor适用的场景便是在拥有一个从类型A到类型B的map over函数时,用这个函数将类型F[A]里的元素逐一地映射为类型F[B]的元素。就好比有一筐桔子,我们将其视作食品类型A,再把制作桔灯的流程视作投给map的函数f,于是经过“桔灯函数”对桔子的逐个加工,最后得到一筐属于照明工具类型B的桔灯。两边不仅元素个数相等、顺序相同,而且容纳元素的容器也必须一致,此处都得用“筐”来装。还原到代码本身,封装构造F在传入Functor前便要明确。比如用Option装入类型A的元素,那么经过map后得到的也必须是Option,只是里面装的是B了。同理,A类型的List,经过map后就当且仅当得到List[B]。

那是不是从语法上extends/deriving了一个Functor,它就是真正意义上的Functor了呢?不是的,还需要检验其函数的具体实现是否遵守了Functor的守则。

  • 守则一: 若给map传入的函数f是根直肠子——原样吐出传入的参数的话(这样的函数被叫作identity或者id函数),那么得到的F[B]应和F[A]从内到外都一模一样,类似map(x)(a => a) == x
  • 守则二: 若给map传入的函数f是两个函数的组合(f·g)的话,那么恒有map(f·g) == map(f(map(g)))

在运用这两个守则时,我通常把守则一作为判断一个Functor实现是否确为Functor的检验工具,而把守则二作为实现多个函数组合运算的计算工具,即看作Scala里的g compose f

ghci> fmap (*2) (Just 200)
Just 400

Applicative & Monad

先看看Applicative与Monad的不同定义:

Applicative的定义

Haskell实现:

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

对应的Scala实现:

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]
  def flatMap[A, B](f: F[A => B]): F[A] => F[B]
}

Monad的定义

Haskell实现:

class Monad f where
  pure :: a -> f a
  (>>=) :: f a -> (a -> f b) -> f b

Monad对应的Scala实现:

trait Monad[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]
  def flatMap[A, B](f: A => F[B]): F[A] => F[B]
}

Applicative与Monad的不同运用场景

从定义上看,Applicative与Monad都有一个完全相同的pure函数(实际对Monad而言,更常见的函数名是return),用于把一个普通的值包装成一个Applicative或者Monad(即Functor中提到的那个封装结构F[_])。

此处先参考一个阐述Applicative与Monad区别的帖子:Haskell引入Applicative有什么意义?

在Applicative中,f (a -> b) -> f a -> f b意思是说,即便我们这个容器f里是一个函数,我们还是可以将其应用到f a类型上,计算a类型的值与应用这个函数两个过程是分离的。
Applicative需要满足的约束比Monad的弱,Applicative的<*>更接近计算(computation)的简单组合,而Monad的>>=有更多的计算结果的依赖。
Monad的>>=会根据左边的comuptation的结果来确定后续的计算,因此>>=右边的computation和左边的computation是有依赖关系的。而Applicative的<*>则不关心左边computation的结果,其两边的computation是相互独立的,因此具有更好的组合性。

所以,尽管Applicative与Monad都是一组函数构成的组合,它们强于Functor之处在于,计算可以直接隔着那层容器应用到容器里的元素上。但是Applicative是一组没有相互依赖关系的计算构成的函数组合,计算没有先后次序之分,是context free的;Monad则是后一计算依赖前一计算构成的函数组合,计算有先后次序之分,是context sensitive的。二者分别用天平一样的<*>和灌肠一样的>>=作为组合方法的函数名,可谓形象之至。

前述帖子中的代码,就用Maybe这种容器很形象地说明了Applicative与Monad二者的区别:

data Maybe a = Nothing | Just a

instance Functor Maybe where
  fmap f Nothing = Nothing
  fmap f (Just a) = Just (f a)

instance Applicative Maybe where
  pure = Just
  Nothing <*> x = Nothing
  (Just f) <*> x = fmap f x

instance Monad Maybe where
  return = Just
  Nothing >>= f = Nothing
  (Just a) >>= f = case f a of
                   Nothing -> Nothing
                   Just r -> Just r

先看一些比较简单的例子:

ghci> Just (+3) <*> Just 9
Just 12

ghci> [(*0), (+100), (^2)] <*> [1, 2, 3]
[0, 0, 0, 101, 102, 103, 1, 4, 9]

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

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

pure f <*> xs等价于fmap f xs,而pure f就是[f],所以[f] <*> xs可将左边的每个函数套用至右边的每个值。于是再定义一个fmap的中缀版<$>

(<$>) :: (Functor f) => (a -> b) -> f a -> f b
f <$> x = fmap f x

然后是<$>的简单示例:

ghci> (++) <$> ["ha", "heh", "hmm"] <*> ["?", "!", "."]
["ha?", "ha!", "ha.", "heh?", "heh!", "heh.", "hmm?", "hmm!", "hmm."]

基于以上结构,分别定义了Applicative下的函数aif,以及Monad下的函数mif:

aif :: Applicative f => f Bool -> f a -> f a -> f a
aif ab at ae = cond <$> ab <*> at <*> ae
  where cond b t e = if b then t else e

mif :: Monad m => m Bool -> m a -> m a -> m a
mif mb mt me = do
  b <- mb
  if b then mt else me

最后,以下的代码因计算步骤之间是否相互依赖,而出现了完全不同的结果:

ghci> aif (Just True) (Just 2) Nothing
Nothing

ghci> mif (Just True) (Just 2) Nothing
Just 2

aif是Applicative,所以<*>会把abatae依次组合进行运算,于是当aeNothing时,最终的计算结果便是Nothing了。再看mif,>>=会根据左边计算的结果来选择mt或是me,而do第一步对mb计算得到的是True,因此最终得到Just 2

对应的Scala版本如下:

还有一篇关于Monad和Applicative运用的文章:Free Monad and Applicative in Scala

浅释Functor、Applicative与Monad

上一篇:解决log4j:WARN No appenders could be found for logger (org.springframework.web.context.ContextLoader)警告信息的问题


下一篇:土旦:移动端 Vue+Vant 的Uploader 实现 :上传、压缩、旋转图片