Functor in Functional Programming

什么是Functor?

先看一段代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
// js
Array(1,2,3)
.map(i => i ** 2)
.map(i => i ** i)
// [1, 16, 81]

// scala
Right(3).map(n => n + " cats!")
// res2: Either[Nothing, String] = Right("3 cats!")

// java
Optional.empty().map(n -> "hi, " + n);
// Optional.empty

这些类型都有map,而且看上去map的作用好像都相同。

事实上,它们确实相同。

不那么准确地说,任何东西只要有map,我们就可以将它视作functor。

要研究functor,我们需要转变一下(命令式)思路。

可以将functor想象成一个容器,容器里放了一些元素。

map并不是对容器进行一次遍历(traverse),而是对容器内的元素做一个变换(transform)。

如果有多个map被串起来了,则会按照先后顺序,进行变换。(这里顺序是很重要的,下面会细说)

Functor的定义

我们可以将functor定义为一个trait:

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

对于一个数据结构,我们只需要让其继承这个trait,并实现map,就可以把它当作functor来用了。

比如:

1
2
3
val listFunctor: Functor[List] = new Functor[List] {
override def map[A, B](as: List[A])(f: A => B): List[B] = as.map(f)
}

functor法则是不言自明的:

1
map(s)(a => a) == s

即,用identity函数映射一个结构s,结果仍然是s。

观察一下,我们可以发现functor能做的事仅有:

  • 将容器内的元素进行变换(transform)

除此之外,都不可以。

比如这些事情,functor都是做不到的:

  1. 改变容器本身:List变成一个SetSome变成一个None
  2. 将元素取出来:Functor[A] 变成 A;
  3. 改变元素:移除List的第一个元素;
  4. 将元素聚合成一个:比如sum起来;
  5. 抛出异常。

非常规functor的例子

Future

Future也有map方法,也是一个functor 。

map会将异步计算应用于Future内的元素,多个map会按照顺序先后执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import scala.concurrent.{Await, Future}
import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.duration._

object FutureUsage extends App {
val future: Future[String] =
Future(0)
.map(_ + 10)
.map(_ * 4)
.map(_ + 2)
.map("The Ultimate Answer to Life, The Universe and Everything is..." + _ + "!")
Await.result(future, 1.second)
// "The Ultimate Answer to Life, The Universe and Everything is...42!"
}

当我们使用Future的时候,其实我们并不清楚Future内部状态。

  • 如果Future已经完成了,那么我们的map就会立刻被调用。

  • 如果Future尚未完成,我们的map会被放到默认的ExecutionContext里的队列中,等着,之后再执行。

对于Future上的map,我们并不知道map何时会执行,我们只知道map执行的顺序

Function(别急,先收起你头上的???)

考虑这种情况,我们有一个f: T => A和一个p: A => B,想要得到一个g: T => B

你一定会说,这个简单,基本的function composition嘛。

这里我们需要换一个视角:

  1. T => A看作SomeFunc[A]
  2. SomeFunc[A]一个A => B
  3. 得到一个SomeFunc[B]

怎么样,我们是不是对SomeFunc进行了一次map
看一段例子,这里我们用到了cats这个库,cats为Scala提供了很多函数式的抽象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import cats.instances.function._
import cats.syntax.functor._

val func1: Int => String =
(x: Int) => x.toString

val func2: String => String =
(y: String) => y + y

// three ways to compose functions
// 1. using map
(func1.map(func2))(2)
// 2. using andThen
(func1.andThen(func2))(2)
// 3. by hand
func2(func1(2))

当我们写下val f = f1.map(f2).map(f3).map(f4)的时候,这一串map就是将一系列的计算’串’在了一起,等到f被调用的时候再执行(和Future一样)。

PS: 这个我们其实叫它Reader Functor(详细内容可以看references中第一篇)。

小结

functor是FP中非常非常基础的抽象,就像monoid一样,看上去对我们日常的编程并没有太大的作用(其实我们可以根据functor构建通用的zipunzip)。不过没关系,之后我们还会研究一些functor的特例,monad和applicative functor,这些是十分实用且普遍的。

PS:你可以在范畴论中找到functor的原型,functor是范畴的态射(morphism of categories),会将一个范畴中的morphism和object映射到另一个范畴中。

References

  1. Functors – Chapter 8 in the Category Theory for Programmers
  2. Functors – Chapter 3 in Scala with Cats
  3. Monad – Chapter 11 in Functional Programming in Scala