文章目录

• • 一、代数数据类型（ADT）
  • • 1.1、从代数到类型
    • 1.2、计数
    • 1.3、积类型
    • 1.4、和类型与密封类
    • 1.5、构造代数数据类型
  • 二、模式匹配
  • • 2.1、何为模式
    • 2.2、常见的模式
    • 2.3、处理嵌套表达式
  • 三、增强的模式匹配
  • • 3.1、类型测试 / 类型转换
    • 3.2、面向对象的分解
    • 3.3、访问者设计模式

一、代数数据类型（ADT）

在计算机编程，特别是函数式编程与类型理论中，ADT是一种组合类型（composite type）。例如，一个类型由其他类型组合而成。两个常见的代数类型是“和（sum）”类型与“积（product）”类型。

1.1、从代数到类型

代数，简单理解就是能代表数字的符号，比如 x，y 等。看两个表达式：

x * 1 = z
a + 2 = c

可以看出，第一个表达式中代数 x 与 1 通过乘法得到了一个新的代数 z，第二个表达式中代数 a 与 2 通过加法操作得到了一个新的代数 c。思考一下，如果把两个表达式中的代数与数字换成编程语言中的类型或者值，那么它们之间通过某种操作是否可以得到某种新的类型？

当我们将这些代数或者数字换成类型，那么这种被我们用代数或者数字换成的类型，以及通过这些类型所产生的新类型就叫做代数类型（ADT）。

1.2、计数

每种类型在实例化时，都会有对应的值，比如 Boolean 类型存在两种可能的值：true 或 false。取值种类为 2，就叫做计数。
再比如 Unit 类型，它表示只有一个实例，也就是说只有一种取值，所以采用计数的方式，Unit 对应的就是数字 1。

1.3、积类型

在 ADT 中，积类型的表示形式与乘法相似，我们可以理解为一种组合。比如有一个类型 a，一个类型 b，要组合成一个类型 c 就应该是：

c = a * b

上面说到 Boolean 类型对应的是 2，Unit 类型对应的是 1，那它们组合之后产生的积类型就应该是：

2 * 1 = 2

用实际的代码来表达两种类型的组合就为：

class BooleanProductUnit (a: Boolean, b: Unit){}

这段代码构建了一个名为 BooleanProductUnit 的类，分别存在一个类型为 Boolean 的参数 a 和一个类型为 Unit 的参数 b。再看看这个类对应的实例取值：

val a = BooleanProductUnit (false, Unit)
val b = BooleanProductUnit (true, Unit)

可以看到，BooleanProductUnit 类最多只能有两种取值。应该可以明白，当我们利用类进行组合时，实际上就是一种 product 操作，积类型可以看做同时持有某些类型的类型，比如 BooleanProductUnit 类型就同时持有 Boolean 类型和 Unit 类型。

由于我们可以根据计数来判断某种类型或者某种类的取值，所以计数还能用在编译时期对 when 之类的语句做分支检查。

1.4、和类型与密封类

前面介绍了积类型对应于代数运算中的乘法，那么和类型（sum）顾名思义就对应于代数中的加法。定义一个枚举类 Day：

enum class Day { SUN, MON, TUE, WED, THU, FRI, SAT }

枚举类就是一个和类型。因为在枚举类中每个常量都是一个对象，比如上面例子中的 SUN，它与其他常量一样，只能有一种取值，所以我们将其记为 1。

• 和类型是类型安全的。因为它是一个闭环，比如上面的枚举类 Day，总共有 7 种可能的取值，不可能出现其他取值，所以在使用时不用担心出现非法的情况。
• 和类型是一种 “or” 的关系。而积类型可以拥有好几种类型，比如前面积类型中的 BooleanProductUnit 类型就同时拥有 Boolean 和 Unit，所以积类型是一种 “and” 关系。而和类型一次只能是其中的一个值，不能同时拥有两种类型。

但是和类型在使用时功能比较单一，扩展性不强。我们需要一种在表达上更强大的语法，那就是上一章 2.1 节中提到的密封类。

sealed class Day {
    class SUN : Day()
    class MON : Day()
    class TUE : Day()
    class WED : Day()
    class THU : Day()
    class FRI : Day()
    class SAT : Day()
}

使用密封类，或者说和类型最大的好处就是，当我们使用 when 表达式时不用去考虑非法的情况了，也就是可以省略 else 分支。比如下面的代码：

    fun schedule(day: Day) {
        when (day) {
            is Day.SUN -> fun1()
            is Day.MON -> fun2()
            is Day.TUE -> fun3()
            is Day.WED -> fun4()
            is Day.THU -> fun5()
            is Day.FRI -> fun6()
            is Day.SAT -> fun7()
        }
    }

这段代码就是一个 ADT 与 when 表达式结合的例子。可以看到，这里面我们不用额外写一个 else 来表示默认的选项，因为它是类型安全的。

1.5、构造代数数据类型

如何构造一个代数数据类型，比如我们现在需要根据相应的条件来分别计算出圆形、长方形、三角形的面积。首先，找到它们的共同点，即它们都是几何图形（Shape），然后就可以利用密封类来进行抽象：

sealed class Shape {
    class Circle(val radius: Double) : Shape()
    class Rectangle(val width: Double, val height: Double) : Shape()
    class Triangle(val base: Double, val height: Double) : Shape()
}

现在我们就将这些图形抽象成了 ADT，整个 Shape 就是一个和类型，其中的 Circle、Rectangle、Triangle 就是通过将基本类型 Double 构造成类而组合成的积类型。

ADT 最大的好处就是可以很放心地去使用 when 表达式，现在就利用 when 表达式来定义一个计算各个图形面积的方法：

    fun getArea(shape: Shape): Double = when (shape) {
        is Shape.Circle -> Math.PI * shape.radius * shape.radius
        is Shape.Rectangle -> shape.width * shape.height
        is Shape.Triangle -> shape.base * shape.height / 2.0
    }

可以看到，通过 ADT 和 when 表达式，代码非常简洁，如果用 Java 实现，则需要写一堆 if-else 表达式，而且还要考虑非法的情况，可读性较差。

二、模式匹配

2.1、何为模式

在第一章中第二节介绍了“表达式”的概念。一个数字、一个对象的实例，或者说，凡是能够求出特定值得组合我们都能称其为表达式。

我们说的模式，其本质上就是这些表达式，模式匹配所匹配的内容其实就是表达式。所以，当我们构造模式时就是在构造表达式。

2.2、常见的模式

我们了解到模式匹配中的模式其实就是表达式。本节会通过 when 表达式来讲解几种常见的模式匹配。

1、常量模式

常量模式很简单，与我们所熟知的 if-else 或者 switch-case 语句几乎没什么不同，就是比较两个常量是否相等。

    fun constantPattern(a: Int) = when (a) {
        1 -> "It is 1"
        2 -> "It is 2"
        else -> "It is other number"
    }

2、类型模式

类型模式其实就是上面 1.5 中介绍过的例子。

sealed class Shape {
    class Circle(val radius: Double) : Shape()
    class Rectangle(val width: Double, val height: Double) : Shape()
    class Triangle(val base: Double, val height: Double) : Shape()
}

    fun getArea(shape: Shape): Double = when (shape) {
        is Shape.Circle -> Math.PI * shape.radius * shape.radius
        is Shape.Rectangle -> shape.width * shape.height
        is Shape.Triangle -> shape.base * shape.height / 2.0
    }

3、逻辑表达式模式

在使用 when 进行匹配时，还有一种比较常见的匹配，那就是匹配逻辑表达式。

    //例1
    fun logicPattern(a: Int) = when {
        a in 2..11 -> "$a >1 and <10"
        else -> ">10"
    }

    //例2
    fun logicPattern(a: String) = when {
        a.contains("a") -> "str contains a"
        else -> "str no contains a"
    }

例 1 中，我们匹配一个数是否在某个数值区间。
例 2 中，我们匹配了某个字符串是否包含另一个字符串。

注意，这里的 when 后面并没有带参数，在这两个例子中，when 表达式的各个分支执行的就是类似于 if 表达式进行判等的操作。

2.3、处理嵌套表达式

首先我们来定义一个结构：

• Num 类表示某个整数的值；
• Operate 类是一个树形结构，用了表示一些复杂的表达式，其中 opName 属性表示常见的操作符，比如 “+” “-” “*” “/”。

    sealed class Expr {
        data class Num(val value: Int) : Expr()
        data class Operate(val opName: String, val left: Expr, val right: Expr) : Expr()
    }

现在根据不同的条件返回相应的结果，首先判断 expr 是否是 Num 类型，如果是就直接返回，否则就进入到下一条判断。分别有两个 else if，如果都不满足，else 就返回 expr 本身。

可以看出，这段代码如果用 Java 来写，将会更加复杂，因为 else if 中的条件还需要做一大堆类型转换的语句才能执行，Kotlin 中能这样写是因为它支持 Smar Casts（3.1 中会介绍）。

    fun simplifyExpr(expr: Expr): Expr = if (expr is Expr.Num) {
        expr
    } else if (expr is Expr.Operate   //如果满足条件 expr 会自动转换为 Expr.Operate 类型
            && expr.opName == "+"   //expr 转换为 Expr.Operate 后就可以调用 opName 属性了
            && expr.left is Expr.Num  //如果满足条件 expr.left 会自动转换为 Expr.Num 类型
            && expr.left.value == 0) {  //expr.left 转换为 Expr.Operate 后就可以调用 opName 属性了
        expr.right
    } else if (expr is Expr.Operate
            && expr.opName == "+"
            && expr.right is Expr.Num
            && expr.right.value == 0) {
        expr.left
    } else expr

可以发现，if-else 语句在处理复杂的嵌套表达式并不简洁，可读性差，首先可以发现要返回 expr.right 需要满足的条件：

• expr is Expr.Operate
• expr.opName == “+”
• expr.left is Expr.Num
• expr.left.value == 0

返回 expr.left 需要满足的条件：

• expr is Expr.Operate
• expr.opName == “+”
• expr.right is Expr.Num
• expr.right.value == 0

下面使用 when 表达式来改写。

    fun simplifyExpr(expr: Expr): Expr = when (expr) {
        is Expr.Num -> expr
        is Expr.Operate -> when (expr) {
            Expr.Operate("+", Expr.Num(0), expr.right) -> expr.right
            Expr.Operate("+", expr.left, Expr.Num(0)) -> expr.left
            else -> expr
        }
    }

三、增强的模式匹配

3.1、类型测试 / 类型转换

类型测试与类型转换工作流程：首先会对类型进行测试，判断所给的值是何种类型，然后再进行类型转换。比如：

expr instanceof Expr.Operate && (Expr.Operate)expr.name.equals("+")

在 Kotlin 中，本身就支持 Smart Casts，所以并不需要做类型转换，只需要实现类型测试就可。

expr.left is Expr.Num && expr.left.value = 0

只需要先判断 expr.left 类型是否为 Expr.Num，接着 Kotlin 会自动帮我们转换为 Expr.Num 类型。

3.2、面向对象的分解

在前面几节，我们在利用模式匹配时都会存在一个问题，就是需要不断的去判定给定的对象是什么类型，比如上面的：expr.left is Expr.Num，然后根据特定的对象类型去访问其内部属性。如果是 Java 的话，还需要进行强制转换，然后才能实现对特定对象的操作。

解决这个问题，我们可以在父类定义一系列方法，通过调用方法来判断是否为数值，然后在子类中实现这些方法，就可以在不同的子类来做相应的操作，就可以不用再重复多次的写判断类型的代码，比如这里的 isZero 方法用来判断某个表达式是否为 0，isAddZero 方法用来判断操作符是否是 “+” 并且 left 属性或 right 是否其中一个为 0。这种思路就叫面向对象的分解。

    sealed class Expr {
        abstract fun isZero(): Boolean
        abstract fun isAddZero(): Boolean
        abstract fun left(): Expr
        abstract fun right(): Expr
        data class Num(val value: Int) : Expr() {
            override fun isZero(): Boolean = this.value == 0
            override fun isAddZero(): Boolean = false
            override fun left(): Expr = throw Throwable("no element")
            override fun right(): Expr = throw Throwable("no element")
        }

        data class Operate(val opName: String, val left: Expr, val right: Expr) : Expr() {
            override fun isZero(): Boolean = false
            override fun isAddZero(): Boolean = this.opName == "+" && (this.left.isZero() || this.right.isZero())
            override fun left(): Expr = this.left
            override fun right(): Expr = this.right
        }
    }

可以看到，上面的代码除了定义了需要用来判断的方法 isZero、isAddZero 外，还定义了 left、right方法，这是因为通过调用 isZero 或者 isAddZero 来判断，Smart Casts 将不再起作用，即编译器不会自动判断然后转成相应的类型，编译器只知道该类型为 Expr，所以还需要定义 left、right 方法来获取相应的类型 Num，然后才能调用相应的方法。

现在来实现 simplifyExpr 方法，将最内层的 Expr.Num(0) 返回出来。

    fun simplifyExpr(expr: Expr): Expr = when {
        expr.isAddZero() && expr.right().isAddZero() && expr.right().left().isZero() -> expr.right().left()
        else -> expr
    }

        val expr = Expr.Operate("+", Expr.Num(0), Expr.Operate("+", Expr.Num(0), Expr.Num(1)))
        println(simplifyExpr(expr)) //打印结果为 Num(value=0)

通过面向对象分解的方式，我们确实将代码简化了。但是问题也很明显，如果业务复杂，我们就需要定义很多的方法来做判断，这将整个类的结构变得非常臃肿，几乎全是一些方法的实现。另外，如果需要添加一个子类，还得将这些方法再全部实现一遍，还可能导致之前的子类中的方法还需要重新实现，代价很高。接着看 3.3。

3.3、访问者设计模式

首先我们另外定义了一个类 Visitor。该类起到一个访问的作用，用它来访问我们需要进行操作的类（这里简称目标类）。

    class Visitor {
        fun matchZero(): Boolean = false
        fun matchZero(expr: Expr.Num): Boolean = expr.value == 0

        fun matchAddZero(): Boolean = false
        fun matchAddZero(expr: Expr.Operate): Boolean = when (expr) {
            Expr.Operate("+", Expr.Num(0), expr.right) -> true
            Expr.Operate("+", expr.left, Expr.Num(0)) -> true
            else -> false
        }

        fun doSimplifyExpr(expr: Expr.Num): Expr = expr
        fun doSimplifyExpr(expr: Expr.Operate, v: Visitor): Expr = when {
            (expr.right is Expr.Num && v.matchAddZero(expr) && v.matchAddZero())
                    && (expr.right is Expr.Operate && expr.right.left is Expr.Num)
                    && v.matchZero(expr.right.left) -> expr.right.left
            else -> expr
        }
    }

接下来我们需要在每个子类中定义相应的方法，并使用参数的方式将访问者对象注入。

    sealed class Expr {
        abstract fun isZero(v: Visitor): Boolean
        abstract fun isAddZero(v: Visitor): Boolean
        abstract fun simplifyExpr(v: Visitor): Expr
        abstract fun left(): Expr
        abstract fun right(): Expr
        data class Num(val value: Int) : Expr() {
            override fun isZero(v: Visitor): Boolean = v.matchZero(this)
            override fun isAddZero(v: Visitor): Boolean = v.matchAddZero()
            override fun simplifyExpr(v: Visitor): Expr = v.doSimplifyExpr(this)
            override fun left(): Expr = throw Throwable("no element")
            override fun right(): Expr = throw Throwable("no element")
        }

        data class Operate(val opName: String, val left: Expr, val right: Expr) : Expr() {
            override fun isZero(v: Visitor): Boolean = v.matchZero()
            override fun isAddZero(v: Visitor): Boolean = v.matchAddZero(this)
            override fun simplifyExpr(v: Visitor): Expr = v.doSimplifyExpr(this, v)
            override fun left(): Expr = this.left
            override fun right(): Expr = this.right
        }
    }

接下来就可以调用了。

    fun simplifyExpr(expr: Expr, visitor: Visitor): Expr = when {
        expr.isAddZero(visitor) && expr.right().isAddZero(visitor) && expr.right().left().isZero(visitor) -> expr.right().left()
        else -> expr
    }

        val expr = Expr.Operate("+", Expr.Num(0), Expr.Operate("+", Expr.Num(0), Expr.Num(1)))
        println(simplifyExpr(expr, Visitor())) //打印结果为 Num(value=0)

采用访问者模式的好处是，我们将类中方法的实现放到了外部，这样使得类的结构看上去比较简洁。