代数类型

发布于 2023/06/27 - 修改于 2023/06/27 - 大约需要 4 分钟 - 1696 字

缘起

重读范畴论，看到了代数类型的内容，记录一下。这篇博客其实已经是去年五月份起草的，一直没发表，因为感觉内容不严谨，加上又在忙自己的研究。想了想还是把它发出来，分享一下。

内容不严谨，可能会修改，代码均为Scala 3，术语尽量使用术语在线的翻译。

代数类型

众所周知，范畴论是关于范畴的理论，所考察的内容是对象（object）以及态射（morphism）。

首先我们有一个特殊的对象，每一个对象到它都有且仅有一个态射。这个对象就是终对象，在Scala中可以是Unit，而态射就是def f[T] : T => Unit = _ => ()。当然，这个对象也可以是None，因为他们是同构的：

def f: Unit => None.type = _ => None
def g: None.type => Unit = _ => ()
// 伪代码
(f compose g)(None) === identity(None)
(g compose f)(())   === identity(())

其次我们有另一个特殊的对象，它到每一个对象都有且仅有一个态射。这个对象就是始对象，在Scala中就是Nothing，而态射就是def absurd[T]: Nothing => T = ???。

之后我们有两个构造。一个是积，另一个是余积。

积的模式涉及三个对象a、b、c，以及两个态射，分别从c到a和从c到b。在Scala中，积就是积类型(A, B)，态射就是_._1和_._2。
余积的模式涉及三个对象a、b、c，以及两个态射，分别从a到c和从b到c。在Scala中，余积就是和类型A | B，态射就是identity，或者说asInstanceOf[A]和asInstanceOf[B]。

可以看到，积就相当于乘法，类型也被称为积类型；而余积相当于加法，类型也被成为和类型。这也是为什么我们称之为代数类型。但这是为什么呢？

让我们回想一下加法和乘法的定义。

对于加法，是在一个集合上的二元运算，任意两个元素都能进行这个运算，结果唯一，运算结果封闭，符合交换律、结合律，并且存在幺元，使得任何其他元素与之进行运算都能得到本身。

对于乘法，与加法类似。不同之处在于乘法还有零元，使得任何其他元素与之进行运算都会得到零元。

让我们回到范畴论中。我们将二元运算从加法与乘法替换为余积和积，集合从自然数改为类型，相等改为同构。于是我们可以看到，余积和积都符合交换律与结合律：A | (B | C) 与(A | B) | C显然同构，其余不赘述。

在积中，终对象相当于积的单位元，因为(A, Unit)或者(Unit, A)都与A本身同构。初对象相当于积的零元，因为(A, Nothing)或者(Nothing, A)都和初对象同构。

相对应的，初对象就相当于余积的零元，因为Nothing | A与A同构。

所谓代数，研究的是各种抽象化的结构，而不仅是数；既然类型也符合这一结构，自然也可落入这一领域。

递归

所有的数据结构，基本上都是和类型或积类型。当然还有另一类：递归类型。

最常见的例子大概就是：

enum List[A] {
    case Nil
    case Cons(hd: A, tail: List[A])
}

一提到递归，我们就自然想到不动点了。函数中的递归是这么表示的：

// 不动点函数
def fix[A, B](f: (A => B) => (A => B)): A => B = (x: A) => f(fix(f))(x)

// 使用例
def sum(f: Int => Int): Int => Int = (x: Int) => if x == 0 then x else x + f(x - 1)
fix(sum)(100) // 5050

类似地，类型的递归可以定义为：

enum Mu[F[_]] {
  case In(i: F[Mu[F]])
}

import Mu._

不动点中的函数f就变为了函子F。所以回到之前列表的例子，其实可以表示为\([A] = \mu L_A\)，而\(L_A = 1 \oplus A \otimes Id\)，其中1、A、Id都是函子，而对于函子X和Y，\(X \oplus Y\)和\(X \otimes Y\)亦是函子。1和A分别是Const[Unit,_]和Const[A, _]，和类型和积类型的函子定义如下：

enum EitherF[F[_]: Functor, G[_]: Functor, X] {
  case LeftF[F[_]: Functor, G[_]: Functor, X](f: F[X]) extends EitherF[F, G, X]
  case RightF[F[_]: Functor, G[_]: Functor, X](g: G[X]) extends EitherF[F, G, X]
}
import EitherF._

given productF[F[_], G[_]](using
    ff: Functor[F],
    fg: Functor[G]
): Functor[ProductF[F, G, _]] with {
  def map[A, B](fa: ProductF[F, G, A])(f: A => B): ProductF[F, G, B] =
    ProductF(ff.map(fa.f)(f), fg.map(fa.g)(f))
}

given eitherF[F[_], G[_]](using
    ff: Functor[F],
    fg: Functor[G]
): Functor[EitherF[F, G, _]] with {
  def map[A, B](fa: EitherF[F, G, A])(f: A => B): EitherF[F, G, B] = fa match {
    case LeftF(a)  => LeftF(ff.map(a)(f))
    case RightF(b) => RightF(fg.map(b)(f))
  }
}

如此递归的定义可以有以下的转换：

def catamorphism[A, F[_]](f: F[A] => A)(using ff: Functor[F]): Mu[F] => A =
  _ match {
    case In(fMuF) => f(ff.map(fMuF)(catamorphism(f)))
  }

def anamorphism[A, F[_]](f: A => F[A])(using ff: Functor[F]): A => Mu[F] =
  a => In(ff.map(f(a))(anamorphism(f)))

于是我们便可以用如下方法表示自然数和列表。

type NatF = EitherF[Const[Unit, _], Id, _]
type NAT = Mu[NatF]

val zero: NAT = In(LeftF(Const.empty))
val one: NAT = In(RightF(In(LeftF(Const.empty))))
def succ(n: NAT): NAT = In(RightF(n))

def nat2int: NAT => Int = catamorphism(n =>
  n match {
    case LeftF(_)  => 0
    case RightF(i) => i + 1
  }
)

type ListF = [A] =>> EitherF[Const[Unit, _], ProductF[Const[A, _], Id, _], _]
type LIST = [X] =>> Mu[ListF[X]]

def nil[A]: LIST[A] = In(LeftF(Const.empty))
def cons[A](hd: A, tl: LIST[A]): LIST[A] = In(RightF(ProductF(Const(hd), tl)))

def length[A]: LIST[A] => NAT = catamorphism(list =>
  list match {
    case LeftF(_)                 => zero
    case RightF(ProductF(hd, tl)) => succ(tl)
  }
)

总结

听上去好像很玄乎，看上去好像很神奇，实在是我还没有研究透彻，解释不清。日后若有机会，再来修订。

范畴论