Haskell编程解决九连环3-详细的步骤

摘要

在本系列的上一篇文章《Haskell 编程解决九连环（2）— 多少步骤？》中，我们通过编写 Python 和 Haskell 的代码解决了关于拆解九连环最少需要多少步的问题。在本文中我们将更进一步，输出所有的详细步骤。每个步骤实际上是一个装上或者拆下一个圆环的动作。关于步骤动作的定义请参见本系列的第一篇文章《Haskell 编程解决九连环（1）— 数学建模》。
维基百科上关于九连环的条目中有拆解 n 连环所需的步数，在本文中我们将要通过编程计算来得出与下表中数字相对应的详细步骤动作，特别的，当连环的数目 n = 9 时，结果应该是 341 条动作。

定理与推论

定理与推论是我们编程实现的基础和指导，再次将它们罗列如下。

定理 1 ：takeOff(1)的解法步骤序列为 [OFF 1]，putOn(1) 的解法步骤序列为 [ON 1]。
定理 2 ：takeOff(2)的解法步骤序列为 [OFF 2, OFF 1]，putOn(2) 的解法步骤序列为 [ON 1, ON 2]。
定理 3 ：当 n>2 时，takeOff(n)的解法由以下步骤组成：1) takeOff(n-2) 2) OFF n 3) putOn(n-2) 4) takeOff(n-1)；而 putOn(n) 由以下步骤组成 1) putOn(n-1) 2) takeOff(n-2) 3) ON n 4) putOn(n-2)。
推论 1 ：takeOff(n)的解法步骤序列和 putOn(n) 的解法步骤序列互为逆反序列。
推论 2 ：takeOff(n)的解法步骤序列和 putOn(n) 的解法步骤序列含有的步骤数目相等。
推论 3 ：对于任何整数 m, n，如果m>n，那么第m 环的状态（装上或是卸下）不影响 takeOff(n) 或者 putOn(n) 的解，同时解决 takeOff(n) 或者 putOn(n) 问题也不会改变第 m 环的状态。

照例，我们从一个命令式语言的实现开始。这有助于熟悉命令式编程语言的小伙伴们理解。也为随后的的 Haskell 实现设定结果规范。

Python 实现

因为涉及到大量的输入输出，这次我们试着构造一个完整的程序。在该程序中提供了主函数入口，使得下面的代码不仅能在交互式环境中运行和测试，也可以在操作系统的命令行环境直接调用。

#!/usr/bin/python
import itertools

def printAction(stepNo, act, n):                       # (1)
    print('{:d}: {:s} {:d}'.format(stepNo, act, n))

def takeOff(n, stepCount):                             # (2)
    if n == 1:
        printAction(next(stepCount), 'OFF', 1)
    elif n == 2:
        printAction(next(stepCount), 'OFF', 2)
        printAction(next(stepCount), 'OFF', 1)
    else:
        takeOff(n - 2, stepCount)
        printAction(next(stepCount), 'OFF', n)
        putOn(n - 2, stepCount)
        takeOff(n - 1, stepCount)
        
def putOn(n, stepCount):
    if n == 1:
        printAction(next(stepCount), 'ON', 1)
    elif n == 2:
        printAction(next(stepCount), 'ON', 1)
        printAction(next(stepCount), 'ON', 2)
    else:
        putOn(n - 2, stepCount)
        printAction(next(stepCount), 'ON', n)
        takeOff(n - 2, stepCount)
        putOn(n - 1, stepCount)

if __name__ == "__main__":                          # (3)
    n = int(input())                                # (4)
    takeOff(n, itertools.count(start = 1))          # (5)

这里我们不再赘述关于递归的基本条件或者递归的拆分算法部分。有兴趣的读者可以参阅本系列的前两篇文章。有一些新出现的东西值得关注。首先命令式语言并不禁止任何函数具有副作用，我们能很容易地在任何地方做输入输出。在代码中大家也可以看到函数的申明没有任何的区别，但是我们能够在迭代或是递归的过程中打印相应的结果。下面我们沿着在代码中标注的序号做一些解释。

1. 虽然本文的目的是展示 Haskell 代码的优美，但是我也喜欢 Python，并不打算故意写出丑陋的 Python 代码。把重复出现的代码提炼成一个函数在所有编程语言里都是一个好习惯。参数 stepNo 是一个整型值，就是当前输出动作在整个解序列中的序号。该函数的输出可能是“10: ON 6”或者“123: OFF 9”。
2. 输出详细步骤的要求让我们不得不关注于不同的动作，根据定理我们选择了 takeOff 和putOn的交叉递归，这是比较简单直接的方案。由于我们选择了在递归的过程中逐步输出的方案，步数的计数器（stepCount）需要被传入并且向下传递。
3. 这是 Python 中主函数的入口，当我们在操作系统层面上将这段代码作为一个独立的程序运行时，启动的进程将从这个入口进入并开始执行代码。
4. 从标准输入设备读取一行输入，并转化为一个整数。这里没有考虑输入检验的部分。通常在产品代码里，对输入有效性的检验是必不可少的。在这里有一个立即可见的风险，如果用户输入一个负数的话，这段程序将会陷入无穷的递归直至栈溢出。
5. 调用 takeOff 用于输出拆解 n 连环的所有步骤。这里我们使用了 itertools 里现成的 count 类作为我们的步骤计数器的实现，这里设定的起始值为 1，那么对于 9 连环，输出的所有步骤将会带有顺序的计数编号 1 到 341。

将以上代码存成一个文本文件并命名为 Main.py，就可以将其作为一个独立的 Python 程序来启动运行。
下面我们在操作系统的命令行（Windows 上可以是 CMD，Linux 中是 shell）中测试运行一下，输出结果应该类似于：

c:\LearnHaskell\9ring>echo 5 | Main.py
1: OFF 1
2: OFF 3
3: ON 1
4: OFF 2
5: OFF 1
6: OFF 5
7: ON 1
8: ON 3
9: OFF 1
10: ON 1
11: ON 2
12: OFF 2
13: OFF 1
14: OFF 4
15: ON 1
16: ON 2
17: OFF 1
18: OFF 3
19: ON 1
20: OFF 2
21: OFF 1

c:\LearnHaskell\9ring>Main.py
9
1: OFF 1
2: OFF 3
3: ON 1
4: OFF 2
5: OFF 1
.....................
336: ON 2
337: OFF 1
338: OFF 3
339: ON 1
340: OFF 2
341: OFF 1

c:\LearnHaskell\9ring>

首先我们以命令 echo 输出 5 通过管道喂给我们的程序，得到拆解 5 连环的 21 步解法。然后我们直接运行 Main.py，程序启动后暂停等待用户输入，键入 9 然后回车，程序将会输出拆解 9 连环的所有 341 个步骤。大家也可以通过输出转向将详细解法存成一个文本文件，就像这样 echo 9 | Main.py > 9ringSolution.txt。有兴趣有耐心的小伙伴可以对照输出用真实的九连环验证一下哦，341 步还是可以操作的。
那么这个实现是否和上一篇文章中一样有性能问题呢？能否计算 50 连环甚至 200 连环呢？性能问题是有的，这里的交叉递归的算法仍然必须拆解每个子问题直至基本条件，所以也是具有指数级别的复杂度，也就是 O(2^n)。不过在这里算法的低效不是主要问题，因为我们的要求是输出所有的解法步骤，这些步骤跟2^n 是相当的，由于 IO 是特别耗时的操作，与之相比算法本身的开销就微不足道了。所以不要试图去计算并输出 200 连环的拆解步骤，我们的电力，电脑，我们自己，我们所处的星系都将不能支撑或是等到程序结束。

Haskell 实现（1）

相应的，我们也将 Haskell 的代码写成一个完整的程序，将以下的代码存为一个文本文件并命名为 rings.hs（扩展名.hs 指明该文件是 Haskell 的源文件）。可以使用 Haskell 的编译器 ghc 将其编译链接成二进制本地文件运行，或者使用 ghc 提供的解释器犹如解释脚本文件般地运行。

printAction act n stepNo = do     -- (1)
    putStr (show stepNo)          -- (2)
    putStr ":"
    putStr act
    putStr " "
    putStrLn (show n)             -- (3)

takeOff :: Int -> Int -> IO Int   -- (4)
takeOff n stepNo
    | n == 1 = do                 -- (5)
        printAction "OFF" 1 stepNo
        return (stepNo + 1)       -- (6)
    | n == 2 = do
        printAction "OFF" 2 stepNo
        printAction "OFF" 1 (stepNo + 1)
        return (stepNo + 2)
    | otherwise = do              -- (7)
        newStepNo <- takeOff (n-2) stepNo     -- (8)
        printAction "OFF" n newStepNo
        newStepNo' <- putOn (n - 2) (newStepNo + 1)
        takeOff (n -1) newStepNo'

putOn :: Int -> Int -> IO Int
putOn 1 stepNo = do
    printAction "ON" 1 stepNo
    return (stepNo + 1)
putOn 2 stepNo = do
    printAction "ON" 1 stepNo
    printAction "ON" 2 (stepNo + 1)
    return (stepNo + 2)
putOn n stepNo = do
    newStepNo <- putOn (n-1) stepNo
    newStepNo' <- takeOff (n-2) newStepNo
    printAction "ON" n newStepNo'putOn (n - 2) (newStepNo' + 1)

main :: IO ()      -- (9)
main = do
    n <- read <$> getLine    -- (10)
    takeOff n 1   -- (11)
    return ()     -- (12)

这是一段挺长的代码了，好在上一节我们已经有了可供参照的 Python 程序，大家可以看到大块的结构是一一对应的。让我们沿着代码注释中的标号分析一下代码，特别是 Haskell 中特别的东西：

1. 和 Python 中一样，将输出一个步骤的代码提取出来成为一个函数。细心的读者也许注意到这里将参数 stepNo 移到了最后，在上一节的 Python 程序中，stepNo 由于会首先输出，很自然地被作为第一个参数，在 Python 中参数的顺序并不重要，只要在调用的地方按照正确的顺序传入参数即可。在 Haskell 中这个改动是经过仔细考虑的，其作用在稍后的代码简化中我们就可以看到。另外请注意 do 关键字，它在这段代码里几乎无处不在。其实 do 是 Monad 的语法糖，Monad 是 Haskell 中的一个很高层次的抽象，可以被理解为一个抽象的计算结构或计算语境，例如我们熟知的列表就具有 Monad 所概括的所有特性和要求的行为方式，所以列表有时也被称为一种 Monadic 的结构。Monad 最重要的作用之一是解决计算顺序的问题。我们知道 Haskell 本质上是 lambda 演算，在 lambda 演算中嵌套的表达式隐含了一定的求值顺序，例如 y=x+1，如果我们需要求值y，那么必须先要对x 求值。Monad 的抽象帮助我们以顺序的方式来表达事实上是嵌套的 lambda 表达式。回到 do 关键字，这里我们可以简单地理解为 do 后面通常跟随了多个动作（或者表达式），do事实上将它们“粘合”成一个大的动作，当这个“大”动作被要求执行的时候，其所包含的所有动作将会按照顺序依次执行并产生结果。
2. putStr是 Haskell 的标准输出函数，它接受一个字符串参数，执行的时候将该字符串打印到标准输出上。show函数是一个多态的函数，是类型类（Type Class）Show的成员函数，在 Haskell 里类型类比较类似于 Java 里的接口（Interface）。简单地说 show 函数接受一个参数，并将其转换为字符串，任何可以被 show 函数转换的类型必须实现（或者继承）Show类型类并且提供（或者继承）show的实现。Haskell 里的基础数值类型以及列表，元组等类型均是 Show 类型类的实例。
3. 在调用了多次 putStr 后我们调用了一次 putStrLn，该函数跟putStr 唯一的区别在于输出字符串后再输出一个新行符（\n）。可以看到我们利用类型转换函数 show 和输出函数 putStr，putStrLn“拼凑”了一行输出。Haskell 有第三方的库提供了printf 函数，其功能与 C /C++ 中的 printf 类似，功能上一点也不弱。
4. 和 Python 代码一样，我们选择了 takeOff 和putOn交叉递归。由于我们要在这两个函数中做输出，这两个函数的结果类型都必须包含 IO 结构。我们知道输入输出是具有副作用的（打开文件，读取键盘敲击，改变终端显示甚至拆毁房子，引爆炸弹都是 IO 的副作用），而 Haskell 通常的函数不允许有副作用，也就是说通常的函数不被允许做输入输出，这些函数也被称为纯粹的函数。在 Haskell 中 IO 被交给非纯粹（Impure）的函数来完成，这类函数必须有类似 IO a 的结果类型，其中 a 是一个具体类型例如 Int，String 甚至是函数类型例如 IO (String -> Int)。一个IO a 类型的值可以被看作一个动作，当该动作被成功执行（我们通常说执行一个 IO 动作，求值一个表达式，其实这二者的意义是等价的或是相当的）时，将会产生一个具有 a 类型的结果，该结果可以被从 IO 结构中取出并被后续程序使用。这里 takeOff 函数就可以被理解为接受两个 Int 型的参数（连环数目 n 和当前步骤计数器的数值），然后产生一个 IO Int 的动作，当该动作被执行时（也可以认为是被求值），会产生一系列的输入输出（副作用），当这一切成功后，该动作产生一个 Int 值作为动作最后的结果。在 takeOff 和putOn函数中这个 Int 的结果实际上是做了一系列输出后步骤计数器的下一个值。我们知道在 Haskell 的函数里，我们不能改变一个全局的状态，所以我们无法像在 Python 中那样使用类似 next 的调用在获得计数器当前值的同时将其状态加一以备后用，这里只能将计数器的新值返回，由调用者负责传递到下一个函数调用中。
5. 这一行使用的是哨兵（Guard）的机制，其语法是函数参数模式匹配后面有一个或多个形如“| < 条件表达式 > = < 函数体 >”的定义结构，首先是一个竖线 |，之后的条件表达式可以对参数以及在模式匹配中绑定的名称做判断，然后是等号和函数体。我们在上一篇文章中提到过，要对输入的参数分情形做判断，通常的机制是模式匹配和哨兵。这两种机制是互补的，经常被结合在一起使用。一般的，一个函数的实现可以有一个或者多个模式匹配，每个模式匹配可以没有，有一个或者多个哨兵。模式匹配和哨兵都是有顺序的。在运行时，当一个函数被求值的时候，Haskell 使用传入的参数依照定义顺序尝试模式匹配，如果某个模式匹配成功，则依照定义顺序尝试该模式的哨兵，如果某个哨兵的条件表达式求值为 True，则以该哨兵等号后的函数体作为该函数的求值表达式，如果该模式中的所有哨兵均返回 False，则移到下一个模式继续尝试匹配。如果尝试完所有的模式和哨兵仍然没有匹配的模式且求值为 True 的哨兵组合，那么该函数求值失败，会报告运行错误。模式匹配和哨兵在能力上还是有一些区别的，模式匹配能够匹配数值的结构以及常量，而哨兵通常不能判断数值的结构（除非借助一些辅助函数，而那些辅助函数实际上也是通过模式匹配返回布尔值而已），但能判断数值范围，复杂的布尔条件以及条件组合，当然哨兵也能处理常量。例如我们用模式匹配判断一个参数是否是一个形如(a,b) 的二元元组，而用哨兵判断一个年份是否是闰年 mod n 4 == 0 && mod n 100 /= 0 || mod n 400 == 0。回到我们的代码，这里我们对连环数目 n 做判断，看它是否为常量 1 或 2，对此模式匹配和哨兵均有能力完成。在此为了展示两者的语法，我们主要使用哨兵来实现函数takeOff 而完全使用模式匹配来实现putOn。
6. 在 Haskell 里 return 的含义与在命令式语言里有很大的不同，在命令式语言里，return通常立即终止函数的运行，并返回一个值作为函数运行的结果。而在 Haskell 里 return 是一个普通的函数，其作用是将一个值放入到一个结构中，具体是什么结构取决于上下文，而且 return 也不会终止函数或任何表达式的求值。在这里我们的上下文是 IO Int 其结构就是 IO，所以在这段代码里我们看到的 return 多数时候就是接受一个 Int 型的值（步骤计数器的当前值）并放入到 IO 结构中。那么在这里 return 的类型就应该是 Int -> IO Int。在 Haskell 的代码里，我们可以显式地申明值或函数的类型，看编译器是否同意我们的理解。例如我们可以将这行代码改为(return :: Int -> IO Int) (stepNo + 1)，代码仍然可以通过编译。而如果我们申明其类型为Int -> [Int] 或是 Int -> IO ()，编译器就会抱怨了。细心的读者可能注意到在 1，2 的情况下我们有return 但在 n 的情况下却没有，那是因为 doblock 的最后一个动作takeOff 或putOn的类型就是 IO Int，其中的值就是我们打算作为返回值的步骤计数器的最新值，所以这里没必要再通过<- 算符提取 IO 结构里的值，然后再通过 return 放入到同样的 IO 结构中了。关于算符 <- 我们会在随后讨论。
7. otherwise是一个总是为 True 的哨兵，其逻辑相当于 if ... then ... else ... 中的 else 或者 switch/case 中的 default 分支。
8. 操作符 <- 做的事情和 return 恰好相反，其右边是一个带有结构的值，<-从结构中取出值然后绑定到左边的名称上（可以像在命令式语言中那样理解为从结构中取出值赋给左边的“变量”）。这里 <- 的右边是一个 IO Int 的值，从其中取出那个 Int 型的值绑定到名称 newStepNo，那么我们可以确定名称（可以理解为“变量”）newStepNo 就具有 Int 类型。请注意= 和<-的区别 = 不会做任何附加操作，仅仅是一个名称绑定，如果 b 是一个类型为 IO Int 的值或表达式，那么当我们写 a = b 时a就具有 IO Int 的类型，而如果我们写 a <- b，那么a 必是 Int 型的。
9. 这就是 Haskell 的主函数。主函数必须是 IO 类型的，其类型可以是 IO () 或是 IO Int，可以理解为分别对应了 C /C++ 中的void main 和int main。这里的 () 是一个类型，就是之前我们提到过的零元的元组，零元元组的可能值只有一个，也是 ()，这个值又被称作 unit。Haskell 里所有的函数都必须有类型，也就是说必须有返回结果，当我们的确需要表达没有返回值或者返回值不重要的时候（这在做纯粹的输出的时候比较常见）就可以使用() 作为返回值以及其类型。在代码的最后一行有 return ()，那里的() 就是零元元组的值 unit。
10. getLine是 Haskell 的标准输入函数之一，它从标准输入设备上读取一行数据，直至回车，将读到的数据以字符串返回，其类型是 IO String。read 函数是 Read 类型类的成员函数，它所做的事情跟上面提到的 show 恰好相反，read接受一个字符串，将其转换成其它类型，例如 Int，Float 甚至是列表，元组等有结构的类型。操作符 <$> 是函数 fmap 的中缀版本，二者完全等价。fmap是 Functor 类型类的成员函数。Functor是 Haskell 中一个很重要的抽象概念，有些中文资料中翻译为“函数子”或者“函子”。简单地说 Functor 是一类计算结构（或者说计算环境），这类结构在内部存放数据，并且允许能够操作该数据的函数被 map over，map over 在 Haskell 中被广泛地理解为 lift（提升），就像电梯一样把一个函数提升到需要的层次去操作。其实最简单直接的中文理解是“穿越”，Functor作为一种计算结构，其中包含一定类型的数值，Functor允许那些能操作该数值的函数“穿越”进其结构外壳并操作内部的数值，并且不改变 Functor 的原有结构。我们熟知的 IO，[]（列表或者叫做 List）都是 Functor 的实例。举个例子，我们有函数 (+1) 能操作 Int 型的数据，例如 (+1) 7 的结果是 8，如果我们有个Int 型的列表 [1,2,3]，该怎样使用(+1) 去操作其中的 Int 值呢？在命令式语言中，我们通常会通过迭代，循环等方法打开结构依次取出所有的值，然后通过代码把函数作用到这些数值上，就地更改数据，或是复制一份结果。而在 Haskell 中我们只需利用列表结构的 Functor 特性将函数穿越进去操作即可，fmap (+1) [1,2,3]或者 (+1) <$> [1,2,3] 将返回给我们 [2,3,4]。回到代码，我们说过getLine 的类型是 IO String，而read 在这里的类型是 String -> Int（为什么这里read 会把字符串转化为 Int 而不是其他类型呢？这是 Hakell 的类型推导在起作用，这里我们解开表达式的结果，取出 IO 结构里面的值并绑定到名称 n，随后调用takeOff 函数将 n 作为其第一个参数，而该参数被明确定义为 Int，于是 Haskell 顺利推断出我们调用read 是期望得到一个整数），read <$> getLine就具有类型 IO Int，于是我们从 IO 结构中取出Int 数值绑定到名称 n。当然我们也可以先取出字符串绑定到一个名称，然后再转换，像这样 s <- getLine; let n = read s。可以看到使用Functor 的函数 map over 使代码简洁了一些。
11. 拆卸 n 连环是我们的目标问题，递归开始的地方。同样设定步骤序号的起始值为 1。
12. 这是编译器所要求的，因为我们的主函数 main 有类型 IO ()，最后必须通过return 将一个 () 放入到 IO 结构中。否则编译器、解释器将把最后一句的结果作为函数的结果类型，我们知道那是takeOff n 1，其类型为IO Int，类型的不匹配会导致编译错误。

打开操作系统的命令行环境，让我们来看看运行的情况：

c:\9ring>ghc rings.hs
[1 of 1] Compiling Main             (rings.hs, rings.o)
Linking rings.exe ...

c:\9ring>echo 5 | rings
1: OFF 1
2: OFF 3
3: ON 1
4: OFF 2
5: OFF 1
6: OFF 5
7: ON 1
8: ON 2
9: OFF 1
10: ON 3
11: ON 1
12: OFF 2
13: OFF 1
14: OFF 4
15: ON 1
16: ON 2
17: OFF 1
18: OFF 3
19: ON 1
20: OFF 2
21: OFF 1

c:\9ring>runhaskell rings.hs
9
1: OFF 1
2: OFF 3
3: ON 1

..........

338: OFF 3
339: ON 1
340: OFF 2
341: OFF 1

我们调用 Haskell 的编译器 ghc 将源文件编译为可执行文件，然后启动该可执行文件，通过 echo 和管道把 5 作为输入喂给该程序，得到 5 连环的解。之后我们使用 Haskell 提供的解释运行命令 runhaskell 以脚本解释的方式再次启动程序，通过键盘输入 9，于是得到了 9 连环的 341 步解法。编译运行和解释运行在 Haskell 里没有功能上的区别，唯一的不同在于编译运行会有较高的性能。
该实现虽然能正确运行，但跟 Python 的相比，这段 Haskell 代码显得异常笨拙。其中至少有两个比较明显的问题：

1. 数学运算和输入输出混在一起，这对于函数式编程天生不友好。特别在 Haskell 里，讲究把纯粹（pure）和非纯粹（impure）的部分完全隔离开来，以数学建模和公式推演的方式来完成纯粹部分的理论系统的建立，而使用传统的调试，测试的方法来验证和保证非纯粹部分的正确性。把纯粹非纯粹部分隔离开的做法不但能提高程序的模块化水平，让我们更加易于验证算法的正确性，而且经常能帮助我们大幅度地简化代码。
2. 有很大一部分代码用于不停地在 Int 和IO Int间做转换，可以看到我们多次使用 <- 将Int的数值从 IO Int 中取出，只是为了传递到只接受 Int 参数的函数，然后这些函数又生成 IO Int 的结果，为此我们还创建了好些像 newStepNo 这样的一次性的名称（变量）。

对于第 1 点我们需要放宽眼界，寻找别的数据结构和算法。而对第 2 点倒是可以立即做些改进和简化。我们提到过 do 只是语法糖，其背后的实质是 Monad 的核心函数 >>=，>>= 接受两个参数，像这样被调用 a >>= f。其左边的参数 a 是一个带有结构（Monadic 结构例如 IO, [] 等）的值，右边的参数 f 是这样一个函数，它接受一个不带结构的数值（就是 a 去掉结构后的数值），产生另一个带结构的数值，这个结果和 a 具有相同的结构，但是其中的数值可以有不同的类型。而算符 >>= 的作用就是当其所在表达式被求值的时候，>>=解开 a 的结构，取出其中的数值，把该数值喂给函数 f，将函数 f 的结果作为整个 >>= 表达式的结果，注意到这个结果跟 a 具有相同的结构，如果有相应的函数，又可以使用 >>= 来继续做进一步的计算。也就是说 >>= 可以方便地级联，像数据管道一样做多级的组合。
一般的，如果 m 是具有 Monad 特性的结构，>>=具有类型 m a -> (a -> m b) -> m b。在这里我们设 m 是 IO，a 和 b 都是Int，那么可以看到>>= 的一个特化的版本是 IO Int -> (Int -> IO Int) -> IO Int，也就是算符>>= 接受一个 IO Int 的值 a，还有一个具有 Int -> IO Int 类型的函数 f，将 a 中的 Int 型的值取出（上文中提到的 <- 所做的工作），将该值喂给 f 得到结果，该结果仍然是一个 IO Int。可以看到偏函数takeOff n 和putOn n都具有类型 Int -> IO Int。如果我们在打印一个动作后返回计数器的当前值，那么偏函数printAction act n 也将具有相同的类型。这里就可以看出我们为什么把计数器的值作为 printAction 的最后一个参数了。简化的代码如下：

printAction act n stepNo = putStr (show stepNo)
    >> putStr ":"
    >> putStr act
    >> putStr " "
    >> putStrLn (show n)
    >> return (stepNo + 1)

takeOff :: Int -> Int -> IO Int
takeOff n stepNo
    | n == 1 = printAction "OFF" 1 stepNo
    | n == 2 = printAction "OFF" 2 stepNo
        >>= printAction "OFF" 1
    | otherwise = takeOff (n-2) stepNo
        >>= printAction "OFF" n
        >>= putOn (n - 2)
        >>= takeOff (n -1)

putOn :: Int -> Int -> IO Int
putOn 1 stepNo = printAction "ON" 1 stepNo
putOn 2 stepNo = printAction "ON" 1 stepNo
    >>= printAction "ON" 2
putOn n stepNo = putOn (n-1) stepNo
    >>= takeOff (n-2)
    >>= printAction "ON" n
    >>= putOn (n - 2)

main :: IO ()
main = do
    n <- read <$> getLine
    takeOff n 1
    return ()

读者可以将这段代码存成一个新的文件（例如 rings1.hs）自行验证。唯一需要说明的是算符 >>，这个算符是>>= 的姊妹版本，它的作用是丢弃左边的数值。我们知道 >>= 保证了函数的顺序执行，并且将前一部分产生的带结构的数据从结构中取出来传递给下一个函数。而 >> 只有顺序的保证。很多时候我们有一些没有参数的函数，我们需要将它们链入到大的函数链中并需要它们的计算结果，这时候 >> 就很有用了。在 Haskell 中 >> 的实现是基于 >>= 的，从实现代码中也可以看到作为第 2 个参数的函数 f 没有任何参数，它具有类型m b。

(>>) :: m a -> m b -> m b
m >> f = m >>= (\_ -> f)

Haskell 实现（2）

现在我们来把纯粹和非纯粹的部分分开，也就是把算法和输出分开。思路是 takeOff n 和putOn n均返回一个动作序列，再交由专门的输出函数去做输出。为了表示动作和动作序列，我们需要首先定义一个数据结构 Action，在 Haskell 里用户定义的数据结构也和原生的数据类型一样被称为类型（Type）。Haskell 里跟定义新类型有关的语法有 3 种，分别由关键字type，newtype 和data界定。关于这 3 种语法的联系和区别请参阅其它相关资料。

data Action =          -- (1)
    ON Int
  | OFF Int            -- (2)
  deriving (Show)      -- (3)
  
takeOff :: Int -> [Action]    -- (4)
takeOff 1 = [OFF 1]
takeOff 2 = [OFF 2, OFF 1]
takeOff n = takeOff (n -2) ++ OFF n : putOn (n - 2) ++ takeOff (n - 1)   -- (5)

putOn :: Int -> [Action]
putOn 1 = [ON 1]
putOn 2 = [ON 1, ON 2]
putOn n = putOn (n - 1) ++ takeOff (n - 2) ++ ON n : putOn (n - 2)

printActions :: [Action] -> IO ()                                 -- (6)
printActions acts = sequence_ $ zipWith printSingleAct [1,2..] acts   -- (7)
    where printSingleAct stepNo act = putStr (show stepNo)       -- (8)
            >> putStr ":"
            >> putStrLn (show act)

main :: IO ()
main = takeOff.read <$> getLine >>= printActions    -- (9)

可以看到我们算法的部分 takeOff 和putOn是纯粹的函数，没有副作用，其实现也已经相当的公式化了。所有的输出交给了非纯粹的函数 printActions 去做，包括为动作加上序号的工作。读者可以将这段代码存成一个 Haskell 源文件例如 rings2.hs，如前启动运行，可以看到其输出和之前的代码完全一致。让我们来走读一下代码本身：

1. Action是我们为描述动作定义的类型。这里使用了关键字 data 是因为我们有多于一个的值构造子（Value Constructor），而 type 和newtype不能在这种情况下使用。另外请注意 Haskell 的类型名称必须以大写字母开头。
2. Action类型有两个值构造子 ON 和OFF，Haskell 允许一个类型有多个值构造子，值构造子定义间用操作符 | 隔开，寓意值构造子之间是互斥的。这个很容易理解，当我们构造一个该类型的值的时候，必须且仅能选用一个值构造子。ON和 OFF 均接受一个 Int 类型的参数。值构造子与普通的函数无异，唯一的区别仅在于值构造子的名称必须以大写字母开头而普通函数必须以小写字母开头（运算符是另一种情况）。值构造子作为函数，它们接受参数并返回一个相关类型的值。如果在 ghci 中加载该代码文件或是直接键入 Action 的定义，可以使用命令 :type ON 来查看 ON 的类型，其结果是 Int -> Action。如果在命令式语言中定义类似的数据结构，可以定义一个structure（C/C++）或是一个class（C++/Java/Python），并拥有两个成员，其一为一个标志（Flag）用于区分值的类型是ON 还是OFF，另一个成员则用于存放构造时通过参数传入的整型值。
3. Haskell 中有很多基础类类型可以被自动继承，实际上就是由编译器通过一定的规则自动为我们编写实现，这其中就包括 Show。我们知道类类型Show 提供了成员函数 show 用于将该类型的一个值转换为字符串。在这里 Haskell 自动生成的实现将把 Action 的值转换为类似“ON 5”、“OFF 8”一样的字符串，完全符合我们的要求，好巧！
4. 为动作编排序号的工作交给了专门的输出函数去做，takeOff和 putOn 就只有一个参数了，就是目标问题圆环的数目 n，根据算法思路，其返回值也变成了一个动作序列。
5. 操作符 ++ 接受两个类型相同的列表 a 和 b，将两个列表联结在一起并返回一个新的列表，结果列表中前面依次是 a 中的所有元素，然后依次是 b 中所有的元素。操作符 : 是列表的一个值构造子，它接受一个单个的元素 a 和一个列表 l，将 a 插入到 l 的头上，返回这个包含元素 a 的新列表。可以看到这行代码就是依据定理 3 将较大的问题拆分成几个较小的问题，然后将所有子问题的结果合并为目标问题的结果。幸运的是大多数操作符以及函数调用的优先级都恰好符合我们的需求，这里仅有 n-1，n-2 需要加上括号。
6. printActions处理一个动作列表，将所有的动作加上序号，打印到输出设备上。所以其名称中使用了复数。

7. 这行的要点有好几处，需要详细说明：

   • [1,2..]是一个无穷的正整数序列，作为动作的序号使用。
   • zipWith 是我们的老朋友了，在上一篇文章中我们见过。这里 zipWith 将序号序列（[1,2..]）和动作序列（acts）依次配对，然后将配好的值对作为参数传给函数 printSingleAct，再将printSingleAct 的所有结果依次放入一个列表中作为结果返回。函数 printSingleAct 将随后定义，它接受一个整型的序号和一个动作，将它们拼接打印成一行输出。这里 printSingleAct 的类型是 Int -> Action -> IO ()。因此函数zipWth 的结果就是[IO ()]，是一个 IO 动作的序列。
   • sequnce_函数后面有比较抽象的数学理论的支持和演化历史。这里我们可以简单地理解为 sequnce_ 接受一个 IO 动作的序列，将其中包含的 IO 动作依次“粘合”成一个大的 IO 动作，当这个大的 IO 动作被执行时，相当于所有原始 IO 动作被依次执行，然后抛弃所有原始 IO 动作的返回结果并返回IO ()。sequence_ 有个姊妹版本 sequence 会将所有原始 IO 动作所返回结果中包含的数据放入到一个列表中返回。例如当传入 IO 动作列表是 [IO Int] 的时候，sequence_的结果是 IO () 而sequence的结果是 IO [Int]。这里我们知道zipWith 的结果是 [IO ()]，如果我们在这里使用sequence 将会得到 IO [()]，我们知道 unit() 作为返回结果对我们来说没有什么意义，并且外围函数 printActions 的类型是IO ()，于是在此简单地选用了sequence_。
8. where语法是 Haskell 中申明定义“局部”名称的方法之一。所谓“局部”名称可以是常量或是函数，仅在包含该 where 子句的表达式中可见，语法上 where 子句紧跟其起作用的外围表达式。这里我们通过 where 子句定义了一个 (在where 子句里可以定义多个名称)“局部”函数 printSigneAct。printSingleAct 的实现代码很直接，通过 putStr，putStrLn 和show函数结合传入的参数“拼凑”了一行输出。细节可以参阅上一节。
9. 这次我们选择“穿越”进 IO 结构外壳的是组合函数 takeOff.read，我们知道getLine 封装在 IO 内的是一个字符串 String。“穿越”进去的组合函数首先起作用的是 read 函数，它将 String 转换为 Int，然后这个Int 值被喂给组合中的下一个函数 takeOff，takeOff 接受一个 Int 值后生成我们的解，一个动作序列 [Action]，由于<$> 穿越之后不改变 getLine 的结构外壳 IO，于是 takeOff.read <$> getLine 的结果就是 IO [Action]。最后我们使用>>= 算符打开 IO 的外壳，取出其中的动作序列 [Action]，将其作为参数喂给输出函数printActions 去输出。而 printActions 返回的 IO () 正是我们期待的作为整个 main 函数的返回值。至少在这一行上所有的动作都完美地结合在一起，一个多余的动作都没有，一个局部名称或变量都不需要。

在这个算法中 takeOff 返回的是一个动作序列，如果我们的目的只是解决拆卸的问题的话，那我们完全可以利用推论 1 来简化代码，那样我们就可以不用使用两个函数交叉递归了。为了得到一个动作序列的逆反序列，我们首先要有方法得到一个动作的反动作，至于获取一个序列的倒序序列在 Haskell 中有预定义的函数reverse。以下是简化后的代码：

data Action =
    ON Int
  | OFF Int
  deriving (Show)
  
flipAction (ON n) = OFF n    -- (1)
flipAction (OFF n) = ON n
  
takeOff :: Int -> [Action]
takeOff 1 = [OFF 1]
takeOff 2 = [OFF 2, OFF 1]
takeOff n = takeOff (n -2) ++ OFF n : (map flipAction $ reverse $ takeOff $ n - 2) ++ takeOff (n - 1)   -- (2)

printActions :: [Action] -> IO ()
printActions acts = sequence_ $ zipWith printSingleAct [1,2..] acts
    where printSingleAct stepNo act = putStr (show stepNo)
            >> putStr ":"
            >> putStrLn (show act)

main :: IO ()
main = takeOff.read <$> getLine >>= printActions

仅有两处需要说明一下：

1. 定义并实现了求一个动作的反动作的函数 flipAction，使用了模式匹配来识别输入参数是由哪个值构造子构造的并绑定其中的整型值到名称 n，从而返回相应的反动作。这里没有显式申明函数flipAction 的类型，程序员可以一眼看出，对于编译器更不在话下。
2. 我们使用了 map flipAction $ reverse $ takeOff $ n - 2 来替代原有的 putOn (n - 2)。这里所有的$ 算符都是为了节省括号，该表达式的括号版本为 map flipAction (reverse (takeOff (n - 2)))，可以看出首先得到takeOff (n -2) 的解法的动作序列，然后调用函数 reverse 将该动作序列反序，最后由 map 函数对反序后的序列里的每个动作求取其反动作，结果就是 putOn (n-2) 的解法动作序列。这个完全是推论 1 的直接代码映射。

Haskell 实现（3）

目前为止，一切都不错。不过有没有类似上一篇文章中最后那个实现一样的公式化解法呢？有的。首先让我们来做公式推导。设定解法动作序列的序列 offSolutions = [S1, S2, S3 ... Sn ...]，其中的元素Sn 就是拆解 n 连环的动作序列，注意 offSolutions 是一个动作序列的序列，映射成代码就是 [] ([] Action) 或者语法糖 [[Action]]。可以看出offSolutions 是一个无穷序列，并且 S1 = [OFF 1]，S2 = [OFF 2, OFF 1]。设offSolutions 从S3开始的子序列 [S3, S4, S5 ...] 为subS, 于是我们有 offSolutions = [S1, S2] ++ subS。根据我们之前的推导Sn 可以由 Sn-1 和Sn-2以及 n 计算而来，n在这里是需要的，注意到定理 3 所描述的算法里有一步 OFF n，而Sn-1 和Sn-2均是动作序列，从其中很难提取出所需要的 n 的值。我们把定理 3 定义为一个函数 f，那么就有Sn = f(Sn-2, Sn-1, n)，展开有subS = [S3, S4, S5 ... Sn ...] = [f(S1, S2, 3), f(S2, S3, 4), f(S3, S4, 5) ... f(Sn-2, Sn-1, n) ...] = g([S1, S2 ... Sn-2 ...], [S2, S3 ... Sn-1 ...], [3, 4 ... n ...]) = g(xs, ys, ns)。至此可以看出xs 就是序列 offSolutions，ys 是offSolutions刨除第 1 个元素后的子序列，ns是从 3 开始的正整数序列。而函数 g 是这样一个函数，它接受 3 个无穷序列，从 3 个序列中依次取出 1 个值作为参数喂给有 3 个参数的函数 f 将函数 f 的结果依次组成序列作为结果返回。以下程序中由标签 begin 和 End 界定的部分就是由公式推导直接翻译出的代码，另外仅有 main 函数的实现略有改动，其余部分均与前一程序相同。

data Action =
    ON Int
  | OFF Int
  deriving (Show)
  
flipAction (ON n) = OFF n
flipAction (OFF n) = ON n

-- Begin
offSolutions = [OFF 1]:[OFF 2, OFF 1]:subS

subS = g xs ys ns
g = zipWith3 f                 -- (1)
f sn2 sn1 n = sn2 ++ OFF n:(map flipAction $ reverse sn2) ++ sn1   -- (2)
xs = offSolutions
ys = tail offSolutions
ns = [3,4..]
-- End
  
printActions :: [Action] -> IO ()
printActions acts = sequence_ $ zipWith printSingleAct [1,2..] acts
    where printSingleAct stepNo act = putStr (show stepNo)
            >> putStr ":"
            >> putStrLn (show act)

main :: IO ()
main = (offSolutions !!).(subtract 1).read <$> getLine >>= printActions  -- (3)

该程序是完整可运行的。读者可以自行寻找对应代码与公式推导中对应的各个要点。几点简要说明如下：

1. 预定义函数 zipWith3 和之前我们介绍过的 zipWith 类似，区别在于 zipWith3 处理 3 个序列，相应的作为其第一个参数的函数 f 必须接受 3 个参数。在 Haskell 的 Data.List 库中预定义了 zipWith，zipWith3 直至 zipWith7。Haskell 中认为参数过多的函数难以操纵或重用，多于 7 个参数的函数很少见。如果的确有必要zip 8 个或更多的序列，在Control.Applicative 库中有 ZipList 类型提供了完美地解决方案，其细节不在本文的讨论范围。
2. sn2就是推导中的 Sn-2，sn1 是Sn-1。
3. 这次“穿越”进 IO 结构的是组合函数 (offSolution !!).(subtract 1).read，read 将输入的 String 转换为 Int，偏函数(subtract 1) 将输入减 1，这里不能使用 (-1)，编译器会解释为负一。之所以要减一是因为!! 所接受的索引是从零开始的，offSolutions的第 n 个元素是拆解 n 连环的解，其索引为 n-1。最后偏函数(offSolutions !!) 接受一个整型的索引值，返回 offSolutions 在该索引处的元素。

最后让我们来简化这段代码，简化的机会在于以下三点：

1. 仅使用一次的名称可以就地展开，命名函数转换为 lambda 版本。
2. 合乎直觉地，如果我们认为拆解 0 连环的所有步骤为空序列[]，定理 3 所确定的算法仍然有效，就是说我们的递归算法可以扩展到 0 连环的情况，这样我们就不需要在索引值上减 1。
3. 还有一个不寻常的技巧（Trick，花招，烂招？），我们可以用一个有符号的整数来表示一个动作，正数表示 ON 而负数表示 OFF，这样取负值的操作就成为求反动作的函数，虽然在输出打印的时候需要额外做判断，但节约了Action 类型的定义还有求反动作的函数，还是可以节约一些代码的。

offSolutions = []:[-1]:
            zipWith3 (\sn2 sn1 n -> sn2 ++ n:(map negate.reverse $ sn2) ++ sn1)
               offSolutions (tail offSolutions) [-2, -3 ..]

printActions :: [Int] -> IO ()
printActions acts = sequence_ $ zipWith printSingleAct [1,2..] acts
    where printSingleAct stepNo act = putStr (show stepNo)
            >> putStr (if act > 0 then ": ON" else ": OFF")
            >> (putStrLn.show.abs) act

main :: IO ()
main = (offSolutions !!).read <$> getLine >>= printActions

这段代码就没多少好解释的了，注意函数 negate 返回给定参数的负值，而 abs 则是取绝对值的函数。

后记

依照最初的设想，本文就是系列中的最后一篇文章了，关于九连环的问题我们都已解决。而关于 Haskell 的内容还多，路也还长，今后会有其它的文章或是系列来讨论和展现 Haskell 的能力和魅力。另外我真心希望能和各位高手，读者有交流和互动，如果在评论区中出现有趣的问题和讨论的话，笔者不排斥在系列中再整理一篇额外的文章。