今天白天停电，所以看了一下设计模式，看到Vistor的时候突然想起Expression Problem，Vistor模式可以在OO里放弃数据类型的扩展来得到方法扩展，还是不能解决Expression Problem。
最近Reddit Haskell上也有讨论Expression Problem，最吸引我的是codata和OCaml的polymorpic variants，已经遇到很多次了。
下面是一年前在QQ空间里的一篇关于Expression Problem笔记。
昨天看完了Channel 9上关于Expression Problem的两个视频（1，2），记一下笔记什么的。
“The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).” — Philip Wadler
简单讲就是定义一个数据类型，然后在不用重新编译原有代码和保证静态类型安全的前提下，添加新的方法和数据类型。
因为静态类型安全，所以下面都是在编译期进行类型检查的语言。
基本的OO（不用超复杂的设计模式）里声明好接口，然后就可以写各种类来实现这个接口，所以数据扩展很容易，但是想添加方法的话，必须要修改接口。
interface Expr {
int eval();
}
class Const implements Expr {
int i;
Const(i) { this.i = i; }
int eval() { return i; }
}
class Add implements Expr {
Expr e1, e2;
Add(Expr e1, Expr e2) {
this.e1 = e1;
this.e2 = e2;
}
int eval() {
return e1.eval() + e2.eval();
}
}现在要添加减法，没问题：
class SubAdd implements Expr {
Expr e1, e2;
Sub(Expr e1, Expr e2) {
this.e1 = e1;
this.e2 = e2;
}
int eval(){
return e1.eval() - e2.eval();
}
}现在要添加prettyPrint方法，必须修改借口，还有修改各个子类。
interface Expr {
int eval();
String prettyPrint();
}
...基本的函数式编程里面可以很容易对方法进行扩展，而基本的OO对数据扩展很容易。
FP里声明了（代数）数据类型之后，就可以对这个数据类型随意写函数，但是一旦修改了数据，相关的函数都要修改。
data Expr = Const Int
| Add Expr Expr
eval (Const i) = i
eval (Add e1 e2) = eval e1 + eval e2上面这个Expr类型有两种情况，Const表示常熟和Add表示加法，eval计算一个Expr返回Int。 加个prettyPrint方法，没问题：
prettyPrint (Const i) = show i
prettyPrint (Add e1 e1) = prettyPrint e1 ++ " + " prettyPrint e2但是要增加其他情况（例如Sub）就要改Expr的声明，eval 和 prettyPrint 也要修改了。
Haskell可以用type clas解决Expression Problems。
先声明我们的表达式：
class Expr a然后有加法和常数：
data Const = Const Int
data Add a = Add a a现在Const和Add是不同的类型，它们的共性就是它们都是表达式，所以声明为Expr的实例：
instance Expr Const
instance (Expr a) => Expr (Add a)然后把eval也分一个type class里：
class (Expr a) => Evaluable a where
eval :: a -> Int只有Expr才能被计算，所以声明里有(Expr a) 的约束，然后每个Evaluable的实例都要现实eval方法：
instance Evaluable Const where
eval (Const i) = i
instance (Evaluable a) => Evaluable (Add a) where
eval (Add e1 e2) = eval e1 + eval e2现在要添加数据类型就只要声明成Expr的实例，实现已有的方法：
data Sub a = Sub a a
instance (Expr a) => Expr (Sub a)
instance (Evaluable a) => Evaluable (Sub a) where
eval (Sub e1 e2) = eval e1 - eval e2想要添加方法就再声明新的type class然后实现各个类型的实例：
class (Expr a) => PrettyPrintable a where
prettyPrint :: a -> String
instance PrettyPrintable Const where
prettyPrint (Const i) = show i
instance (PrettyPrintable a) => PrettyPrintable (Add a) where
prettyPrint (Add e1 e2) = "(" ++ prettyPrint e1 ++ " + "
++ prettyPrint e2 ++ ")"
instance (PrettyPrintable a) => PrettyPrintable (Sub a) where
prettyPrint (Sub e1 e2) = "(" ++ prettyPrint e1 ++ " - "
++ prettyPrint e2 ++ ")"搞定。
虽然type class和接口像，都声明了要实现的方法。用Java模仿上面Haskell的做法就是声明多个接口，然后每个类都实现…糟糕，原有的类要实现新的接口就要重新编译了。
也许泛型和无敌的设计模式来拯救OO了，只是我还不会。
继续回到Haskell，上面解法够方便，但是现在的Const、Sub、Add是不同的类型，不能放到列表里，因列表必须同质，难道要用Tuple模拟异质列表？
我知道的一个方法就是用ExistentialQuantification（存在量化？）
data ExprBox = forall a . Expr a => MkExpr aMkExpr可以接受任意Expr的实例，然后得到ExprBox类型的东西。 然后就可以放一个列表里了：
exprList = [MkExpr (Const 1), MkExpr (Add (Const 1) (Const 2))]但是这基本是没有用的…因为没有办法把里面的Expr取出来。
我想对列表里的每一个ExprBox的Expr取出来，eval之：
data ExprBox = forall a . (Evaluable a) => MkExpr {unBox :: a}
instance Expr ExprBox
instance Evaluable ExprBox where
eval (MkExpr e) = eval e还要prettyPrint的话，就要增加新的约束：
data ExprBox = forall a . (Evaluable a, PrettyPrintable a)
=> MkExpr {unBox :: a}
instance Expr ExprBox
instance Evaluable ExprBox where
eval (MkExpr e) = eval e
instance PrettyPrintable ExprBox where
prettyPrint (MkExpr e) = prettyPrint e这样下去，约束类型的列表就越来越长了，所以又可以写新的type class，包含前面的约束，也是不好扩展的方法，还更麻烦了。