我所理解的monad(4):函子(functor)是什么

大致介绍了幺半群(monoid)后,我们重新回顾最初引用wadler(haskell委员会成员,把monad引入haskell的家伙)的那句话:

一个单子(Monad)说白了不过就是自函子范畴上的一个幺半群而已 

现在我们来解读这句话中包含的另一个概念:自函子(Endofunctor),不过我们先需要一些铺垫:

首先,什么是函子(Functor)?

乍一看名字,以为函子(functor)对函数(function)是一种封装,实际没有关系,尽管他们都是表示映射,但两者针对的目标不一样。

函数表达的映射关系在类型上体现在特定类型(proper type)之间的映射,举例来说:

// Int => String
scala> def foo(i:Int): String = i.toString

// List[Int] => List[String]
scala> def bar(l:List[Int]): List[String] = l.map(_.toString)

// List[T] => Set[T]
scala> def baz[T](l:List[T]): Set[T] = l.toSet

而函子,则是体现在高阶类型(确切的说是范畴,可把范畴简单的看成高阶类型)之间的映射(关于高阶类型参考: scala类型系统:24) 理解 higher-kinded-type),听上去还是不够直观,函子这个术语是来自群论(范畴论)里的概念,表示的是范畴之间的映射,那范畴又与类型之间是什么关系?

把范畴看做一组类型的集合

假设这里有两个范畴:范畴C1 里面有类型String 和类型 Int;范畴C2 里面有 List[String]List[Int]

函子表示范畴之间的映射

从上图例子来看,这两个范畴之间有映射关系,即在C1里的Int 对应在C2里的List[Int],C1里的String对应C2里的List[String],在C1里存在Int->String的关系态射(术语是morphism,我们可理解为函数),在C2里也存在List[Int]->List[String]的关系态射。

换句话说,如果一个范畴内部的所有元素可以映射为另一个范畴的元素,且元素间的关系也可以映射为另一个范畴元素间关系,则认为这两个范畴之间存在映射。所谓函子就是表示两个范畴的映射。

怎么用代码来描述函子?

从上图的例子,我们已经清楚了functor的含义,即它包含两个层面的映射:

1) 将C1中的类型 T 映射为 C2 中的 List[T] :  T => List[T]
2) 将C1中的函数 f 映射为 C2 中的 函数fm :  (A => B) => (List[A] => List[B])

要满足这两点,我们需要一个类型构造器

trait Functor[F[_]] {

    def typeMap[A]: F[A]

    def funcMap[A,B](f: A=>B): F[A]=>F[B] 
}

我们现在可以把这个定义再简化一些,类型的映射方法可以不用,并把它作为一个type class

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

现在我们自定义一个My[_]的类型构造器,测试一下这个type class:

scala> case class My[T](e:T)

scala> def testMap[A,B, M <: My[A]](m:M, f: A=>B)(implicit functor:Functor[My]) = {
 |          functor.map(m,f)
 |      }

scala> implicit object MyFunctor extends Functor[My] {
 |          def map[A,B](fa: My[A], f:A=>B) = My(f(fa.e))
 |      }

//对 My[Int], 应用函数 Int=>String 得到 My[String]
scala> testMap(My(200), (x:Int)=>x+"ok")
res9: My[String] = My(200ok)

不过大多数库中对functor的支持,都不是通过type class模式来做的,而是直接在类型构造器的定义中实现了map方法:

scala> case class My[A](e:A) {
     |     def map[B](f: A=>B): My[B] = My(f(e))
     | }

scala> My(200).map(_.toString)
res10: My[String] = My(200)

这样相当于显式的让My同时具备了对类型和函数的映射(A->My[A]A=>B -> My[A]=>My[B];在haskell里把这两个行为也叫提升(lift),相当于把类型和函数放到容器里),所以我们也可以说一个带有map方法的类型构造器,就是一个函子。

范畴与高阶类型

我们再来思考一下,如果忽略范畴中的关系(函数),范畴其实就是对特定类型的抽象,即高阶类型(first-order-type或higher-kinded-type,也就是类型构造器),那么对于上面例子中的”范畴C2″,它的所有类型都是List[T]的特定类型,这个范畴就可以抽象为List高阶类型。那对于”范畴C1″呢?它又怎么抽象?其实,”范畴C1″的抽象类型可以看做是一个Identity类型构造器,它与任何参数类型作用构造出的类型就是参数类型:

scala> type Id[T] = T

是不是很像单位元的概念?在shapeless里已经提起过

这么看的话,如果范畴也可以用类型(高阶)来表达,那岂不是只用普通函数就可以描述它们之间的映射了?别急,先试试,方法里是不支持类型构造器做参数的:

scala> def foo(cat: Id) = print(cat)
    <console>:18: error: type Id takes type parameters

方法中只能使用特定类型(proper type)做参数。

我所理解的monad(4):函子(functor)是什么》上有3条评论

  1. aaron

    这样看来范畴 C2 代表的高阶类型应该就是 List[T], 相当于带有模板参数的类型,理论上来说应该可以被用作函数参数呀?

    回复
  2. 王涛

    您好,我最近在学习函数式相关的东西,但是发现好多概念完全不知所云, 对着方面挺感兴趣的,但是自己的计算机理论基础较差,也没个方向,从哪里开始学起呢? 有没有好的书籍或者网站推荐一下 : )

    回复
    1. hongjiang 文章作者

      我会推荐你看一下《Scala函数式编程》,可能刚开始会有点费劲,有些高阶内容也不用完全理解,看过之后会让你对函数式领域的概念大致有所了解。

      最好的方式是有东西(不管是工作中的任务,还是学术上的研究)能让你持续参与,持续思考,并能得到反馈。

      回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注