我所理解的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)做参数。