Functor-Cats和Cats

明天回学校了,僵硬。

接着之前的内容,之前我们总结了一部分Cats中的内容,接下里就会见识到更多炫酷的词了。

Functor

Functor本身也是很简单的概念,可以简单的看做Categories之间的映射。对于两个范畴\(C\)\(D\),而functor\(F\)\(C\)中的objects映射到\(D\)中。对于\(C\)中的object a,其在\(D\)中的映像为F a。但是,范畴中除了objects还有morphisms。所以F应该还要能映射对应的morphisms。即Functor除了映射objects,他还保留objects之间的连接关系,即

1
2
3
4
-- 如果在cats c中有
f :: a → b
-- 则应该有
F f :: F a → F b

基于这个关系应该还有

1
2
3
h = g . f
-- 则还有
F h = F g . F f

至于\(id_{a}\)还应该有\(F\ id_{a} = id_{F\ a}\)

Functor Laws

为了满足这两点,我们需要一个类型构造器,以及一个函数

1
2
class Functor f where
fmap :: (a → b) → f a → f b
1
2
3
trait Functor[F[_]] {
def map[A, B](f: F[A])(f: A => B):F[B]
}

其还应该满足functor laws,即\(F\ id_{a} = id_{F\ a}\)变成

1
2
def identity[A](fa: F[A]): IsEq[F[A]] =
fa.map(identity) <-> fa

对于

1
2
3
h = g . f
-- =>
F h = F g . F f

就对应

1
2
def composition[A, B, C](fa: F[A], f: A => B, g: B => C): IsEq[F[C]] =
fa.map(f).map(g) <-> fa.map(f andThen g)

不过这些性质的保证并不是编译器保证的,在Cats中,是通过laws中的约束生成单元测试的测试用例保证的。

Some Functors

很多常见的类型都是Functor

Maybe or Option

Haskell中的Maybe或者说Scala中的Option,用来表示返回结果可能有异常。

1
2
3
instance Functor Maybe where
fmap f (Just a) = Just (f a)
fmap _ Nothing = Nothing
1
2
3
4
5
6
implicit val functorForOption: Functor[Option] = new Functor[Option] {
def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa match {
case None => None
case Some(a) => Some(f(a))
}
}
Function?

其实一开始看到FunctorFunction到底有什么关系?一个函数其实是A -> Bkind* → * → *,而我们的functorKind* → *,所以我们先给函数一个参数类型即变成→ B,或者写成(→) A。这样我们就期望他的fmap的类型应该是(b → c) → f b → f c就变成(b → c) → (a → b) → (a → c)这更好就是函数的组合。

可以简单的写成

1
2
instance Functor ((→) a) where 
fmap = (.)
List

List也是一个functor,而且其fmap函数很自然

1
2
3
4
instance Functor List a where
fmap :: (a -> b) -> f a -> f b
fmap _ Nil = Nil
fmap f (Const x t) = Const (f x) (fmap f t)

这里其实可以发现ListMaybe有点像,他们都是一种容器,而fmap函数的类型是(a -> b) -> f a -> f b,我们可以看成(a -> b) -> (f a -> f b),即将一个定义在原范畴的函数映射到新的范畴中。

Cats中就是

1
def lift[A, B](f: A => B): F[A] => F[B] = map(_)(f)
Functor Composition

不同的Functor往往需要组合使用,比如需要对List[Option[Int]]进行操作。对于Haskell来说比较简单,直接多个fmap组合就好了,但是对于Scala就麻烦了很多。

Cats中的解决办法是显示的构造新的functor

1
2
3
4
5
6
7
8
trait ComposedFunctor[F[_], G[_]] extends Functor[λ[α => F[G[α]]]] 
with ComposedInvariant[F, G] { outer =>
def F: Functor[F]
def G: Functor[G]

override def map[A, B](fga: F[G[A]])(f: A => B): F[G[B]] =
F.map(fga)(ga => G.map(ga)(f))
}

然后实现compose

1
2
3
4
5
def compose[G[_]: Functor]: Functor[λ[α => F[G[α]]]] =
new ComposedFunctor[F, G] {
val F = self
val G = Functor[G]
}

Functoriality

接下来会介绍更多像functor的类型。

Bifunctors

如果functor可以看做Cats上的只有一个参数的函数的话,那么我们可以稍微扩展一下,称有两个参数的函数bifunctorbifunctor映射元组(a, b)其中a输入范畴Ab属于范畴B。这部分到是容易理解,但是functor除了要映射object,还要映射morphism,就像这样(f, g) ∘ (f', g') = (f ∘ f', g ∘ g')

让我们具体定义bifunctor

1
2
3
4
5
6
7
class Bifunctor f where
bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
bimap g h = first g . second h
first :: (a -> c) -> f a b -> f c b
first g = bimap g id
second :: (b -> d) -> f a b -> f a d
second = bimap id
1
2
3
4
@typeclass trait Bifunctor[F[_, _]] { self =>
def bimap[A, B, C, D](fab: F[A, B])(f: A => C, g: B => D): F[C, D]
def leftMap[A, B, C](fab: F[A, B])(f: A => C): F[C, B] = bimap(fab)(f, identity)
}

对于Haskell中的firstsecond或者Scala中的leftMap可以看做按住其中一个范畴的内容不变,只映射另一个。

Product and Coproduct Bifunctors

一个容易想到的例子就是category的`productcoproduct也是bifunctors

我们可以看两个例子。

一个product的例子就是Tuple2[A, B]Haskell里面就是(,)

1
2
instance Bifunctor (,) where
bimap f g (x, y) = (f x, g y)
1
2
3
4
val tuple2Bifunctor = new Bifunctor[Tuple2] {
def bimap[A, B, C, D](fab: Tuple2[A, B])(f: A => C, g: B => D): Tuple2[C, D] =
(f(fab._1), g(fab._2))
}

一个coproduct的例子是Either

1
2
3
instance Bifunctor Either where
bimap f _ (Left x) = Left (f x)
bimap _ g (Right y) = Right (g y)
1
2
3
4
5
6
7
val eitherBifunctor = new Bifunctor[Either] {
def bimap[A, B, C, D](fab: F[A, B])(f: A => C, g: B => D): F[C, D] =
fab match {
case Right(x) => Right(g(x))
case Left(y) => Left(f(y))
}
}

composition of bifunctor

bifunctor的组合也和functor的很相似

1
2
3
4
5
6
7
8
9
10
trait ComposedBifunctor[F[_, _], G[_, _]]
extends Bifunctor[λ[(A, B) => F[G[A, B], G[A, B]]]] {
def F: Bifunctor[F]
def G: Bifunctor[G]

override def bimap[A, B, C, D](fab: F[G[A, B], G[A, B]])(f: A => C, g: B => D): F[G[C, D], G[C, D]] = {
val innerBimap: G[A, B] => G[C, D] = gab => G.bimap(gab)(f, g)
F.bimap(fab)(innerBimap, innerBimap)
}
}

Covariant and Contravariant Functors

其实另外一个bifunctor的例子就是function。我们如果想利用两个functor组合的实现bifunctor,我们需要给第一个参数作为类型变量实现functor,为此我们定义type Op r a = a -> r,这样为了实现(b → c) → f b → f c,实际的类型就是(b -> c) -> (b -> r) -> (c -> r)。这种函数是无法通过组合来实现的,所以为了能够把前面的那个箭头反过来,我们本来想实现一个\(C \times C \rightarrow D\),转而实现\(C^{op} \times C \rightarrow D\)

因为我们定义了两种functor。对于一个functor,如果他在映射过程中保留原箭头的方向,即对于\(f: A \rightarrow B\),都有\(F(f): F(A) \rightarrow F(B)\)我们就称其为Covariant Functor。而如果其反转了映射的方向,我们就称其为Contravariant Functors。其实换个角度看对于functor\(C\)映射到D,那么contravariant functor其实就是从\(C^{op}\)映射到D\(C^{op}\)正好是\(C\)的对偶,所有的object都一直,只不过箭头的方向都反过来。

我们看看cats中的contravariant functor

1
2
3
@typeclass trait Contravariant[F[_]] extends Invariant[F] { self =>
def contramap[A, B](fa: F[A])(f: B => A): F[B]
}

其实只看这个函数签名,感觉很奇怪,不妨看一个例子。

1
2
3
4
5
6
trait Order[A] { outer =>
def compare(x: T, y: T): Int
def on[U](f: U => T): Ordering[U] = new Ordering[U] {
def compare(x: U, y: U) = outer.compare(f(x), f(y))
}
}

这部分是Scala.math.Order的代码,这里面的on函数就体现了contravariant

1
2
3
def contramap[A, B](fa: Order[A])(f: B => A): Order[B] = new Order[B] {
def compare(x: B, y: B): Int = fa.compare(f(x), f(y))
}

所以,对于函数来说,其第参数逆变,在结果协变。

Profunctors

再回到函数,既然我们已经意识到了函数比较特殊,和bifunctor不太一样,我们就换个定义方法。我们定义profunctor为从\(C\)\(D\)functor

\[H_F \colon D^{op}\times C \to Set\]

对应到Haskell

1
2
3
4
5
6
7
class Profunctor p where
dimap :: (a -> b) -> (c -> d) -> p b c -> p a d
dimap f g = lmap f . rmap g
lmap :: (a -> b) -> p b c -> p a c
lmap f = dimap f id
rmap :: (b -> c) -> p a b -> p a c
rmap = dimap id
1
2
3
4
5
6
7
8
9
@typeclass trait Profunctor[F[_, _]] { self =>
def dimap[A, B, C, D](fab: F[A, B])(f: C => A)(g: B => D): F[C, D]
// 在第一参数上逆变
def lmap[A, B, C](fab: F[A, B])(f: C => A): F[C, B] =
dimap(fab)(f)(identity)
// 在第二个参数上协变
def rmap[A, B, C](fab: F[A, B])(f: B => C): F[A, C] =
dimap[A, B, A, C](fab)(identity)(f)
}

其中p是一个有两个类型参数的类型。

然后我们实现函数即->

1
2
3
4
instance Profunctor (->) where
dimap ab cd bc = cd . bc . ab
lmap = flip (.)
rmap = (.)
1
2
3
4
val function1Profunctor = new Profunctor[? => ?] {
def dimap[A, B, C, D](fab: A => B)(f: C => A)(g: B => D) =
x => g(fab(f(x)))
}

subtyping and functor

subtyping中我们也谈variance,包含这么三种情况。

\(invariance: A = B \rightarrow F[A] = F[B]\)

\(covariance: A <: B \rightarrow F[A] <: F[B]\)

\(contravariance: A >: B \rightarrow F[A] <: F[B]\)

其实这里就能看出subtyping中的variance其实就是functor的原因。有时候会遇到这种代码

1
2
3
4
5
trait TT[+T] {
def show(t: T) = println(t)
}

// error: covariant type T occurs in contravariant position in type T of value t

这是很常见(?)的错误。

show

一个常见的例子是Show

假设

1
2
3
class A
class B extends A
val showA: Show[A] = Show.show(a => "a!")

这样对于B,我们就有

1
2
val showB1: Show[B] = showA.contramap(b => b: A)
val showB2: Show[B] = Contravariant[Show].narrow[A, B](showA)

首先一个直观的解释show可以看做A => String,即将任意类型映射成String。因此,他在类型参数A上是逆变的就很好理解了。从实现上,由于我们知道给一个A怎么转化成String,那对于给定的B,我们只要类型转化成A,那结果也一定是成立的。

另一个有意思的地方在Cats中实现了narrow

1
def narrow[A, B <: A](fa: F[A]): F[B] = fa.asInstanceOf[F[B]]

确实是直接用的强制类型转换,不过因为有B <: A的限制,所以并不会运行时出错。

Invariant

我们重新整理一下Catsfunctor中实现的内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
trait Invariant[F[_]] {
def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]
}

trait Contravariant[F[_]] extends Invariant[F] {
def contramap[A, B](fa: F[A])(f: B => A): F[B]
override def imap[A, B](fa: F[A])(f: A => B)(fi: B => A): F[B] =
contramap(fa)(fi)
}

// functor 其实就是 covariant functor
trait Functor[F[_]] extends functor.Invariant[F] {
def map[A, B](fa: F[A])(f: A => B): F[B]
def imap[A, B](fa: F[A])(f: A => B)(fi: B => A): F[B] =
map(fa)(f)
}

trait Bifunctor[F[_, _]] {
def bimap[A, B, C, D](fab: F[A, B])(f: A => C, g: B => D): F[C, D]
}

trait Profunctor[F[_, _]] {
def dimap[A, B, C, D](fab: F[A, B])(f: C => A)(g: B => D): F[C, D]
}

最后还剩下Invariant

Invariant的核心是

1
def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]

这个其实也很奇怪,为什么A => BB => A的都需要呢?其实原因很简单,因为类型参数即出现在应该协变的地方,又出现在应该逆变的地方。

有两个常见的例子,第一个就是higher order abstract syntax

1
2
3
data ExpF a 
= App a a
| Lam (a -> a)

这里的a就很明显同时出现在两种地方。

另一个例子就是很多mutable的数据类型上,比如C#IEnumerable是协变的,但是IList就是不变的。

引用

  1. Invariant
  2. cats
  3. Category Theory for Programmers
  4. profunctor