模式匹配，观察者模式和GADT

这是「从函数式角度看设计模式」的第二篇。目的是从和OOP不同的角度重新审视设计模式。

这里讨论的是观察者模式，和它在函数式语言里的等价品，模式匹配（Pattern Matching）。最后也会讨论到GADT（广义代数数据类型）。

Java的模式匹配

考虑一个可以容纳各种数据类型的列表，这里用的是Java语言。

public record Empty() {}

var collection = new LinkedList<>();
collection.add(1);
collection.add("这是字符串");
collection.add(new Empty());

​ 那么，该怎么把东西取出来呢？

在Java17之前，一般需要套好几个if语句，像这样：

var value = collection.getFirst();
if (value instanceof Integer i) { // 注意这个 Integer
    // 取得了数字，进行对应的下一步操作
} else if (value instanceof String s) {
    // 得到字符串时候对应的处理
} else if (value instanceof Empty em) {
    // 拿到`Empty`之后做的操作
} else {
    // 错误处理和其他情况
}

​ 这种写法既冗长啰嗦又容易写错。在早期的Java里，像这里的Integer i，String s，Empty em甚至也不具备，用户必须自己手动拿value强转，甚至连类型保障也没有。

Java17提供了「增强的switch语句」，其实相当于上面语句的语法糖了：

switch (collection.getFirst()) {
    case Integer i -> LogUtils.notice(i.toString());
    case String s -> LogUtils.notice(s);
    case Empty em -> LogUtils.warn("Received an empty element");
    default -> LogUtils.error("unexpected type");
}

不过这个语句也并不是模式匹配，更像是Kotlin的when语句的等价品。实际上可以看做从上到下进行的多个instanceof的检测。

在Java19里，新增了模式匹配的预览，或者叫「Record Patterns」。这样一来，也可以在Java里面对一个类型进行deconstruct来获取里面的子结构了，不过这一特性只能用在record类型上。这里就不多说了。

从观察者模式说起

虽然模式匹配在现代的OOP或者函数式语言里算是基本需求了，但是在不具备这一设施的语言里，又该怎么实现类似的需求呢？

一般来说就是用观察者模式来实现的。例如，在Java里实现一个简单的计算器，大概可以用这样的思路：

interface IExpr {
    public Integer accept(IVisitor visitor);
    public default Integer eval() {
        return this.accept(new IVisitor.Visitor());
    }

    abstract class BinaryExpr implements IExpr {
        @NotNull IExpr left;
        @NotNull IExpr right;
        protected BinaryExpr(IExpr left, IExpr right) {
            this.left = left;
            this.right = right;
        }
    }
    abstract class UnaryExpr implements IExpr {
        @NotNull Integer value;
        protected UnaryExpr(Integer value) {
            this.value = value;
        }
    }
    class Literal extends UnaryExpr {
        public Literal(Integer value) {
            super(value);
        }

        @Override
        public Integer accept(IVisitor visitor) {
            return visitor.visitLiteral(this);
        }
    }
    class Add extends BinaryExpr {
        public Add(IExpr left, IExpr right) {
            super(left, right);
        }

        @Override
        public Integer accept(IVisitor visitor) {
            return visitor.visitAdd(this);
        }
    }
    class Sub extends BinaryExpr {
        public Sub(IExpr left, IExpr right) {
            super(left, right);
        }

        @Override
        public Integer accept(IVisitor visitor) {
            return visitor.visitSub(this);
        }
    }
}

public interface IVisitor {
    Integer visitLiteral(IExpr.Literal e);
    Integer visitAdd(IExpr.Add e);
    Integer visitSub(IExpr.Sub e);

    class Visitor implements IVisitor {
        @Override
        public Integer visitLiteral(IExpr.Literal e) {
            return e.value;
        }
        @Override
        public Integer visitAdd(IExpr.Add e) {
            return e.left.accept(this) + e.right.accept(this);
        }
        @Override
        public Integer visitSub(IExpr.Sub e) {
            return e.left.accept(this) - e.right.accept(this);
        }
    }

    public static void main(String[] args) {
        var expr = new IExpr.Add(new IExpr.Literal(10),new IExpr.Sub(new IExpr.Literal(7), new IExpr.Literal(3)));
        System.out.println(expr.eval());
    }
}

这里虽然每个类里面都有自己的字段，不过姑且是没有mutate它们。

观察者模式的写法千差万别，细节上可能会有不同的写法。不过观察者模式突出的就是一个冗长难写。哪怕用的语言的语法比较简洁，稍微复杂一点的场景都会很难写。另一个问题就是一个visitor只能匹配一层，如果要匹配类似And(Eq(a, b), Ne(a, b))这种嵌套的模式，就需要把多个Visitor串起来，那种写法一定很酸爽。

哪怕用的是Kotlin。

一种想法是把IVisitor和IExpr泛型化，但这样也是用不了的。例如visitAdd之类的方法会报错，因为它们要求的返回值是基类，但是我们想要在Visitor里面实现的本应是针对具体类型的算法。实际上，这里我们刚好触碰到了OOP的类型系统的限制……不过这个话题要等到引入GADT的概念才能得到解决了，当然了，无论Java或者Kotlin都没这玩意。

也许有人会说可以用void取代返回值，然后用副作用来把值传出去，或者用Object类型。有的模式匹配就是这么实现的。但是这种写法其实蛮坏的，因为已经不存在任何可以依赖的编译期类型安全了。

一般来说，如果一个语言有完备的模式匹配语法，那么Visitor模式基本上可以被一行简单的模式匹配所替代。当然，Visitor的可扩展性比起模式匹配还是更好的，具体使用哪一种主要还是取决于使用的语言了。

GADT

如果用一种纯函数的语法，上面那一串模式匹配可以用下面的写法来代替，当然，这里是JVM上的一种更好的语言。

class Pair[A, B](val fst: A, val snd: B)
  enum IExpr[A] {
    case Num(val value: Int) extends IExpr[Int]
    case Bool(val value: Boolean) extends IExpr[Boolean]
    case Add(val left: IExpr[Int], val right: IExpr[Int]) extends IExpr[Int]
    case Sub(val left: IExpr[Int], val right: IExpr[Int]) extends IExpr[Int]
    case And(val left: IExpr[Boolean], val right: IExpr[Boolean]) extends IExpr[Boolean]
    case Or(val left: IExpr[Boolean], val right: IExpr[Boolean]) extends IExpr[Boolean]
//    case Eq(val left: IExpr[A], val right: IExpr[A]) extends IExpr[A]
//    case Ne(val left: IExpr[A], val right: IExpr[A]) extends IExpr[A]
    case Not(val value: IExpr[Boolean]) extends IExpr[Boolean]
  }

def eval[A](expr: IExpr[A]): A = expr match {
    case IExpr.Num(v) => v
    case IExpr.Bool(v) => v
    case IExpr.Add(a, b) => eval(a) + eval(b)
    case IExpr.Sub(a, b) => eval(a) - eval(b)
    case IExpr.And(a, b) => eval(a) && eval(b)
    case IExpr.Or(a, b) => eval(a) || eval(b)
//    case IExpr.Eq(a, b) => eval(a).equals(eval(b))
//    case IExpr.Ne(a, b) => ! eval(a).equals(eval(b))
    case IExpr.Not(v) => !(eval(v))
    case _ => throw IllegalStateException("Unknown type")
  }

val exp1 = IExpr.Not((IExpr.And(IExpr.Bool(false), IExpr.Bool(true))))
val exp2 = IExpr.Add(IExpr.Num(3), IExpr.Num(5))

看起来很舒服的样子。不过，如果把注释掉的那4行放回去，IDE会立刻报错。错误内容大概是，要求的类型是A但是给的却是Boolean。实际上，就是前面提到的问题了。

同样道理，在混合了各种子结构的表达式例如下面这一行代码里，编译也会不通过：

val exp = IExpr.Not(IExpr.Ne(IExpr.Bool(false), IExpr.Eq(IExpr.Add(IExpr.Num(3), IExpr.Num(5)), IExpr.Sub(IExpr.Num(10), IExpr.Num(2)))))

这里就要引入GADT——也就是把构造函数的返回类型改了。具体的详解可以参考这篇文章：https://www.zhihu.com/question/67043774。

于是我们就可以在函数式的语言里写一个这样的Evaluator，可以处理不仅仅是加减乘除也包括布尔值比较的运算：

{-# LANGUAGE GADTs #-}

data Expr a where
    IntLit   :: Int  -> Expr Int
    BoolLit   :: Bool -> Expr Bool
    Add :: Expr Int -> Expr Int -> Expr Int
    Sub :: Expr Int -> Expr Int -> Expr Int
    And :: Expr Bool -> Expr Bool -> Expr Bool
    Or :: Expr Bool -> Expr Bool -> Expr Bool
    Eq  :: Eq a => Expr a -> Expr a -> Expr Bool
    Ne  :: Eq a => Expr a -> Expr a -> Expr Bool
    Not  :: Expr Bool -> Expr Bool

eval :: Expr a -> a
eval (IntLit n) = n
eval (BoolLit b) = b
eval (Add a b) = eval a + eval b
eval (Sub a b) = eval a - eval b
eval (And a b) = eval a && eval b
eval (Or a b) = eval a || eval b
eval (Eq a b) = eval a == eval b
eval (Ne a b) = eval a /= eval b
eval (Not v) = not $ eval v


main = do
    let exp = Not (Ne (BoolLit False) (Eq (Add (IntLit 3) (IntLit 5)) (Sub (IntLit 10) (IntLit 2)))) in
        print . eval $ exp

​ 这里的好处是显而易见的：每一个表达式的类型都是由子结构决定的，同时这样的类型又形成了一棵树。把Eq改为Add，或者把Add的子元素由一个Expr Bool类型改为Expr Int，都会立刻在IDE里面画下红线——不需要运行，编译器已经报错了。

小结

其实Visitor，PM和GADT根据具体场景也分别有不同的用处，这里也只是稍微展示一下它们之间的相关性。

这里用的例子是一个简单的编程语言解释器，在这种情况下GADT的优点很明显，配合语法糖的话用户甚至可以在写表达式的时候就得到免费的错误检测。当然了，不是所有语言都有这个功能。

复杂的工业级编译器流水线，更强调的是不同的功能和流程阶段的分离，在这种情况下，PM和GADT提供的好处可能就不那么明显了。反过来说，Visitor能够提供对逻辑的分离和对接口的抽象，这是简易的PM无法提供的。虽说PM也可以通过各种办法增加灵活性，但这时候又等于像是，重新发明Visitor了。

反而可能是在一般的互联网应用，比如说前后端软件的开发上，GADT和PM能够提供更显而易见的好处，包括数据结构的解构和对抽象数据的建模和检验，也可以降低面向复杂建模的情况下的业务代码复杂度。

前面提到的参数化和泛型化的Visitor，虽然看起来像是编译方面的内容，但是也更多可能是传统互联网应用的需求。编译过程中，解释器里面的模式匹配函数，其实被拆分成了好几个管线，构建AST的部分是由parser，比如递归下降算法或者parsec，来承担的。对于构建出来的AST来说，简单的ADT（在OOP里面可以用interface来建模）比起参数化和泛型化的数据结构来说，约束更少，灵活度也更高。