第 9 章：倒计时问题（The countdown problem）
原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 9。维护者已确认本书可翻译并发布用于学习研究。
本章作为本书第一部分的收尾，展示如何利用前面介绍的概念，开发一个高效程序来求解一个简单的数字游戏。我们先定义一些类型和辅助函数，然后用 Haskell 形式化游戏规则，最后给出一个简单的暴力求解方案，并分两步改进其性能。
9.1 引言（Introduction）
Countdown 是英国电视上一个流行的问答节目，自 1982 年开始播出，其中包含一个数字游戏，我们称之为倒计时问题。这个问题的核心如下：
给定一串数字和一个目标数，尝试构造一个表达式，使其值等于目标数。表达式可以从这串数字中取一个或多个数字，并用加法、减法、乘法、除法和括号组合它们。
序列中的每个数字在表达式中最多只能使用一次，而且所有参与计算的数字，包括中间值，都必须是正自然数（1、2、3，等等）。特别是，不允许使用负数、零，以及像 2 / 3 这样的真分数。
例如，假设给定数字序列 1, 3, 7, 10, 25, 50，目标数为 765。一个可能的解由表达式 (1 + 50) * (25 - 10) 给出，下面的简单计算可以验证这一点：
(1 + 50) * (25 - 10)
= { applying + }
51 * (25 - 10)
= { applying - }
51 * 15
= { applying * }
765
事实上，对于这个例子，可以证明共有 780 个不同解。另一方面，如果保持同一个数字序列，但把目标改为 831，则可以证明它没有解。
在电视节目版本中，为了适合人类选手，还采用了一些额外规则。特别是，总会从序列 1-10, 1-10, 25, 50, 75, 100 中选出六个数字，目标数总在 100-999 范围内，并且有 30 秒的时间限制。在开发计算机玩家时，自然可以抽象掉这些限制，因此本章开发的程序都不会强制或依赖这些额外规则。不过注意，我们并不会把正自然数抽象成更丰富的数值域，例如整数或有理数，因为那会改变问题的计算复杂度。
9.2 算术运算符（Arithmetic operators）
首先声明一个表示四种算术运算符的类型，并通过一个简单的实例声明，让这种类型的值可以显示：
data Op = Add | Sub | Mul | Div
instance Show Op where
show Add = "+"
show Sub = "-"
show Mul = "*"
show Div = "/"
接着定义函数 valid，用于判断把某个运算符应用到两个正自然数上是否会得到另一个正自然数；再定义函数 apply，实际执行这种有效应用：
valid :: Op -> Int -> Int -> Bool
valid Add _ _ = True
valid Sub x y = x > y
valid Mul _ _ = True
valid Div x y = x `mod` y == 0
apply :: Op -> Int -> Int -> Int
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y
apply Div x y = x `div` y
例如，Sub 2 3 的应用无效，因为 2 - 3 为负数；而 Div 2 3 无效，因为 2 / 3 是一个有理数。
9.3 数值表达式（Numeric expressions）
现在声明一个数值表达式类型。一个表达式要么是一个整数值，要么是一个运算符作用于两个参数表达式。同时，我们为表达式定义一个简单的美化输出器：
data Expr = Val Int | App Op Expr Expr
instance Show Expr where
show (Val n) = show n
show (App o l r) = brak l ++ show o ++ brak r
where
brak (Val n) = show n
brak e = "(" ++ show e ++ ")"
例如，1 + (2 * 3) 可以表示为 Expr 类型的值，然后以更易读的字符串形式显示：
> show (App Add (Val 1) (App Mul (Val 2) (Val 3)))
"1+(2*3)"
使用这个类型后，可以定义一个函数返回表达式中的值列表，并定义函数 eval 返回表达式的整体值，前提是这个值是正自然数：
values :: Expr -> [Int]
values (Val n) = [n]
values (App _ l r) = values l ++ values r
eval :: Expr -> [Int]
eval (Val n) = [n | n > 0]
eval (App o l r) = [apply o x y | x <- eval l,
y <- eval r,
valid o x y]
注意，eval 中的失败可能性通过返回结果列表来处理：约定单元素列表表示成功，空列表表示失败。例如，对于 2 + 3 和 2 - 3，有：
> eval (App Add (Val 2) (Val 3))
[5]
> eval (App Sub (Val 2) (Val 3))
[]
eval 中的失败也可以用 Maybe 类型处理，但这里更倾向于使用列表类型，因为推导式记法随后能提供一种方便方式来定义 eval 函数。
9.4 组合函数（Combinatorial functions）
现在定义若干有用的组合函数，它们会返回满足特定性质的所有可能列表。函数 subs 返回列表的所有子序列，这些子序列由“排除或包含每个元素”的所有可能组合给出；interleave 返回把一个新元素插入列表的所有可能方式；最后，perms 返回列表的所有排列，也就是元素所有可能的重新排序：
subs :: [a] -> [[a]]
subs [] = [[]]
subs (x:xs) = yss ++ map (x:) yss
where yss = subs xs
interleave :: a -> [a] -> [[a]]
interleave x [] = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = concat (map (interleave x) (perms xs))
例如：
> subs [1,2,3]
[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
> interleave 1 [2,3,4]
[[1,2,3,4],[2,1,3,4],[2,3,1,4],[2,3,4,1]]
> perms [1,2,3]
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
接着，可以定义一个函数返回从列表中作出的所有选择。这里的选择是以任意顺序选取零个或多个元素的所有可能方式，因此只需考虑所有子序列的所有排列：
choices :: [a] -> [[a]]
choices = concat . map perms . subs
例如：
> choices [1,2,3]
[[],[3],[2],[2,3],[3,2],[1],[1,3],[3,1],[1,2],[2,1],
[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
9.5 形式化问题（Formalising the problem）
最后，我们现在可以定义函数 solution，形式化什么叫求解一个倒计时问题实例：
solution :: Expr -> [Int] -> Int -> Bool
solution e ns n =
elem (values e) (choices ns) && eval e == [n]
也就是说，对于给定数字列表和目标数，如果表达式中的值列表是从这些数字中选择出来的，并且该表达式能成功求值得到目标数，那么这个表达式就是一个解。例如，如果 e :: Expr 表示表达式 (1 + 50) * (25 - 10)，那么有：
> solution e [1,3,7,10,25,50] 765
True
solution 的效率可以通过使用函数 isChoice 来改进。这个函数可以直接判断一个列表是否是从另一个列表中选择出来的，而不是通过 choices 间接完成，因为 choices 会返回一个列表的所有可能选择。不过，目前效率还不重要，而且本章后面还会用 choices 定义若干其他函数。
9.6 暴力求解（Brute force solution）
求解倒计时问题的第一种方法是暴力搜索，也就是生成给定数字列表上的所有可能表达式。首先定义函数 split，返回把一个列表拆分为两个非空列表的所有可能方式，并且这两个列表拼接起来能得到原列表：
split :: [a] -> [([a],[a])]
split [] = []
split [_] = []
split (x:xs) = ([x],xs) : [(x:ls,rs) | (ls,rs) <- split xs]
例如：
> split [1,2,3,4]
[([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4])]
使用 split 后，可以定义关键函数 exprs，它返回值列表恰好为给定列表的所有可能表达式：
exprs :: [Int] -> [Expr]
exprs [] = []
exprs [n] = [Val n]
exprs ns = [e | (ls,rs) <- split ns,
l <- exprs ls,
r <- exprs rs,
e <- combine l r]
也就是说，对于空数字列表，没有可能的表达式；对于单个数字，只有一个由该数字组成的表达式。否则，对于包含两个或更多数字的列表，先产生列表的所有拆分，再递归计算每个拆分部分上的所有可能表达式，最后使用四种数值运算符分别组合每一对表达式。这里使用的辅助函数定义如下：
combine :: Expr -> Expr -> [Expr]
combine l r = [App o l r | o <- ops]
ops :: [Op]
ops = [Add,Sub,Mul,Div]
由此可以定义函数 solutions，返回求解一个倒计时问题实例的所有可能表达式。它先生成给定数字列表每种选择上的所有表达式，然后选出那些能成功求值得到目标数的表达式：
solutions :: [Int] -> Int -> [Expr]
solutions ns n =
[e | ns' <- choices ns, e <- exprs ns', eval e == [n]]
9.7 性能测试（Performance testing）
为了测试本章中的倒计时程序，GHCi 解释器的性能有些有限，因此这里改用 GHC 编译器。第一步是把所有必要定义放入一个名为 countdown.hs 的脚本，并加入一个顶层定义 main，它把函数 solutions 应用于一个示例并显示结果：
main :: IO ()
main = print (solutions [1,3,7,10,25,50] 765)
库函数 print 会把可显示类型的值写到屏幕上，而 main 的类型会在第 10 章进一步解释。随后可以在命令提示符中输入 ghc 来执行编译器，并使用 -O2 标志打开编译优化：
$ ghc -O2 countdown.hs
[1 of 1] Compiling Main
Linking countdown ...
最后，运行生成的可执行文件：
$ ./countdown
[3*((7*(50-10))-25), ((7*(50-10))-25)*3, ...]
例如，使用 GHC 7.10.2 在一台 2.8GHz Intel Core 2 Duo、4GB 内存的机器上做一些简单性能测试时，这个示例在 0.108 秒内返回第一个解，在 12.224 秒内返回全部 780 个解；如果把目标改为 831，则会在 12.802 秒内返回空解列表。更一般地说，我们的暴力程序已经足以在电视节目 30 秒的时间限制内求解倒计时问题。但肯定还能做得更好。
9.8 合并生成与求值（Combining generation and evaluation）
函数 solutions 会生成给定数字上的所有可能表达式，但实践中，许多表达式都会求值失败，因为减法和除法对于正自然数并不总是有效操作。例如，可以证明数字 1, 3, 7, 10, 25, 50 上共有 33,665,406 个可能表达式，但只有 4,672,540 个表达式能成功求值，也就是略低于 14%。
基于这个观察，求解倒计时问题的第二种方法，是通过合并表达式生成和表达式求值来改进暴力程序，让这两个任务同时进行。这样，求值失败的表达式会在更早阶段被丢弃；更重要的是，它们不会再被用于生成更多注定求值失败的表达式。首先声明类型 Result，表示能够成功求值的表达式及其整体值组成的配对：
type Result = (Expr,Int)
使用这个类型后，可以定义函数 results，返回所有可能结果，这些结果由值列表恰好为给定列表的表达式构成：
results :: [Int] -> [Result]
results [] = []
results [n] = [(Val n,n) | n > 0]
results ns = [res | (ls,rs) <- split ns,
lx <- results ls,
ry <- results rs,
res <- combine' lx ry]
也就是说，对于空列表，没有可能结果；对于单个数字，只要这个数字本身是正自然数，就有一个由该数字形成的结果。否则，对于两个或更多数字，先产生列表的所有拆分，再递归计算每个拆分部分上的所有可能结果，最后通过下面的辅助函数，使用四种有效的数值运算符组合每一对结果：
combine' :: Result -> Result -> [Result]
combine' (l,x) (r,y) =
[(App o l r, apply o x y) | o <- ops, valid o x y]
使用 results 后，可以定义新的函数 solutions'，返回求解一个倒计时问题实例的所有可能表达式。它先在给定数字的每种选择上生成所有结果，然后选出值等于目标数的表达式：
solutions' :: [Int] -> Int -> [Expr]
solutions' ns n =
[e | ns' <- choices ns, (e,m) <- results ns', m == n]
就性能而言，solutions' [1,3,7,10,25,50] 765 在 0.014 秒内返回第一个解，比 solutions 快 7 倍；在 1.312 秒内返回所有解，快 9 倍。如果把目标改为 831，则会在 1.134 秒内返回空列表，快 11 倍。也就是说，新程序约比原始版本快 10 倍。但借助一些简单的中学代数，我们还可以继续改进。
9.9 利用代数性质（Exploiting algebraic properties）
函数 solutions' 会生成给定数字上所有求值成功的可能表达式，但实践中，许多表达式本质上是相同的，因为数值运算符具有代数性质。例如，表达式 2 + 3 和 3 + 2 本质上相同，因为加法结果不依赖两个参数的顺序；而 2 / 1 和 2 本质上相同，因为任何数除以一都不会改变这个数。
基于这个观察，求解倒计时问题的最后一种方法，是通过利用这些代数性质来减少生成表达式的数量，从而改进第二个程序。特别是，我们会利用下面五个交换律和单位元性质：
x + y = y + x
x * y = y * x
x * 1 = x
1 * y = y
x / 1 = x
先回顾函数 valid，它判断一个运算符应用到两个正自然数上是否会得到另一个正自然数：
valid :: Op -> Int -> Int -> Bool
valid Add _ _ = True
valid Sub x y = x > y
valid Mul _ _ = True
valid Div x y = x `mod` y == 0
为了利用加法和乘法的交换律，只需要求它们的参数按数值顺序排列，也就是 x <= y；为了利用乘法和除法的单位元性质，只需要求相应参数不是单位值，也就是不等于 1。于是可以把定义修改为：
valid :: Op -> Int -> Int -> Bool
valid Add x y = x <= y
valid Sub x y = x > y
valid Mul x y = x /= 1 && y /= 1 && x <= y
valid Div x y = y /= 1 && x `mod` y == 0
例如，使用这个新定义后，Add 3 2 现在无效，因为根据加法交换律，它本质上与 Add 2 3 相同；而 Div 2 1 现在无效，因为根据除法的单位元性质，它本质上就是数字 2 本身。
使用新版 valid 可以得到一个求解倒计时问题的新版 solutions'，这里将其写作 solutions''。这个新函数可以显著减少生成表达式的数量和解的数量。例如，solutions'' [1,3,7,10,25,50] 765 只会生成 245,644 个表达式，其中只有 49 个是解，分别约为使用 solutions' 时数量的 5% 和 6%。
在性能方面，solutions'' [1,3,7,10,25,50] 765 现在会在 0.007 秒内返回第一个解，比 solutions' 快一倍，并在 0.119 秒内返回所有解，快 11 倍；对于目标数 831，空列表会在 0.115 秒内返回，快 9 倍。更一般地说，给定电视节目版倒计时问题中的任意数字，我们最终的程序通常能在不到一秒内返回所有解，并且比原始暴力版本快约 100 倍，改进相当可观。
9.10 章注（Chapter remarks）
Countdown 基于法国电视上的原始节目 Des Chiffres et des Lettres，而倒计时问题本身与名为 krypto 和 four fours 的儿童算术游戏有关。本章基于文献 [13]，其中还包含对本章产生的三个程序的正确性证明。Bird 和 Mu 在文献 [14] 中探索了求解倒计时问题的一些更高级方法。
9.11 练习（Exercises）
-
重新定义组合函数
choices，使用列表推导式，而不是使用组合、concat和map。 -
定义递归函数
isChoice :: Eq a => [a] -> [a] -> Bool，判断一个列表是否是从另一个列表中选择出来的，但不使用组合函数perms和subs。提示：先定义一个函数，用于从列表中移除某个值的第一次出现。 -
如果把函数
split泛化为也返回包含空列表的配对，会对solutions的行为产生什么影响？ -
使用函数
choices、exprs和eval，验证数字1, 3, 7, 10, 25, 50上共有 33,665,406 个可能表达式，并且其中只有 4,672,540 个表达式能成功求值。 -
类似地，验证如果把数值域泛化为任意整数，那么能成功求值的表达式数量会增加到 10,839,369。提示：修改
valid的定义。 -
修改最终程序，使其：
a. 允许在表达式中使用乘方；
b. 如果没有精确解，则产生最接近的解；
c. 使用适当的简单性度量对解排序。
练习 1-3 的解答见附录 A。