第 10 章：交互式编程（Interactive programming）
原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 10。维护者已确认本书可翻译并发布用于学习研究。
本章展示如何用 Haskell 编写交互式程序。我们先解释在纯语言中处理交互的问题，然后介绍 Haskell 采用的解决方案，接着介绍一系列用于交互式编程的基本操作和派生函数，最后开发三个交互式游戏：猜词、尼姆游戏和生命游戏。
10.1 问题（The problem）
在计算早期，大多数程序都是批处理程序，它们与用户隔离运行，以最大化计算机执行有用工作的时间。例如，编译器就是一个批处理程序，它接收高级程序作为输入，默默执行大量操作，然后产生低级程序作为输出。
在本书第一部分，我们展示了如何用 Haskell 编写批处理程序。在 Haskell 中，这类程序，以及更一般地说所有程序，都被建模为纯函数：它们把所有输入作为显式参数接收，并把所有输出作为显式结果产生：
inputs -> batch program -> outputs
例如，像 GHC 这样的编译器可以建模为类型为 Prog -> Code 的函数，它把高级程序转换为低级代码。
在现代计算中，大多数程序现在都是交互式程序，它们以持续对话的形式与用户一起运行，以提供更高的灵活性和功能性。例如，解释器就是一个交互式程序，它允许用户通过键盘输入表达式，并立即在屏幕上显示这些表达式的求值结果：
keyboard -> interactive program -> screen
这样的程序如何建模为纯函数？乍看之下，这似乎不可能，因为交互式程序按其本性要求在程序运行期间产生副作用，包括读取额外输入和产生额外输出。例如，像 GHCi 这样的解释器如何被看作从参数到结果的纯函数？
多年来，人们已经发展出许多方法，用于把纯函数的使用和副作用需求结合起来。本章余下部分介绍 Haskell 使用的解决方案，它基于一种新类型以及少量基本操作。正如后续章节会看到的，这个底层方法并不限于交互，也可以用于处理其他形式的效果。
10.2 解决方案（The solution）
在 Haskell 中，交互式程序被看作一个纯函数。它接收当前世界状态作为参数，并产生修改后的世界作为结果，其中修改后的世界反映了程序执行期间完成的任何副作用。因此，如果有一个合适的类型 World，其值表示世界状态，那么交互式程序的概念可以表示为类型 World -> World 的函数。我们用下面的类型声明把它简写为 IO，即 input/output：
type IO = World -> World
不过，一般而言，交互式程序除了执行副作用之外，可能还会返回一个结果值。例如，从键盘读取字符的程序可能会返回所读到的字符。为此，我们把交互式程序的类型推广为也返回结果值，而这类值的类型成为 IO 类型的参数：
type IO a = World -> (a,World)
类型为 IO a 的表达式称为动作（actions）。例如，IO Char 是返回字符的动作类型，而 IO () 是返回空元组 () 作为哑结果值的动作类型。后一种类型的动作可以看作纯粹产生副作用、但不返回实际结果值的动作，在交互式编程中经常有用。例如，第 9 章的倒计时程序使用了类型为 IO () 的顶层定义 main。
除了返回结果值，交互式程序也可能需要参数值。不过，没有必要进一步推广 IO 类型来说明这一点，因为这种行为已经可以通过柯里化实现。例如，一个接收字符并返回整数的交互式程序，其类型为 Char -> IO Int，这是柯里化函数类型 Char -> World -> (Int,World) 的简写。
到这里，读者可能会相当合理地担心：使用动作编程时，传递整个世界状态是否可行？当然，这并不可能。现实中，类型 IO a 是 Haskell 提供的基本类型，而不是表示成函数类型。不过，上面的解释有助于理解动作如何被看作纯函数，而且 Haskell 中动作的实现与这种观点一致。本章余下部分将把 IO a 看作一个实现细节隐藏起来的内置类型：
data IO a = ...
10.3 基本动作（Basic actions）
现在介绍 Haskell 提供的三个基本 IO 动作。首先，动作 getChar 从键盘读取一个字符，把它回显到屏幕上，并将该字符作为结果值返回：
getChar :: IO Char
getChar = ...
getChar 的实际定义内置于 GHC 系统中。如果键盘上没有等待读取的字符，getChar 会等待直到用户输入一个字符。与之对偶的动作 putChar c 会把字符 c 写到屏幕上，并且不返回实际结果值，也就是返回空元组：
putChar :: Char -> IO ()
putChar c = ...
最后一个基本动作是 return v，它只是返回结果值 v，而不与用户发生任何交互：
return :: a -> IO a
return v = ...
函数 return 提供了一座从没有副作用的纯表达式通往带副作用的不纯动作的桥。关键是，没有返回的桥。一旦进入不纯世界，就永远不纯，无法赎回。结果，我们可能会怀疑不纯性会迅速蔓延到整个程序，但实践中通常并非如此。对大多数 Haskell 程序来说，绝大多数函数并不涉及交互，交互由最外层相对较少的一组交互式函数处理。
10.4 顺序执行（Sequencing）
在 Haskell 中，可以使用 do 记法把一列 IO 动作组合成一个复合动作，其典型形式如下：
do v1 <- a1
v2 <- a2
...
vn <- an
return (f v1 v2 ... vn)
这样的表达式有一个简单的操作性读法：先执行动作 a1，并把它的结果值命名为 v1；然后执行动作 a2，并把它的结果值命名为 v2；如此继续，直到执行动作 an 并把它的结果值命名为 vn；最后，把函数 f 应用于所有结果，将它们组合成单个值，作为整个表达式的结果值返回。
关于 do 记法，还需要注意三点。首先，布局规则适用，也就是说，序列中的每个动作都必须从完全相同的列开始，如上所示。其次，与列表推导式一样，表达式 vi <- ai 称为生成器，因为它们会为变量 vi 生成值。最后，如果生成器 vi <- ai 产生的结果值不需要使用，那么这个生成器可以简写为 ai，含义与写作 _ <- ai 相同。
例如，现在可以如下定义一个动作：它读取三个字符，丢弃第二个，并把第一个和第三个作为一对返回：
act :: IO (Char,Char)
act = do x <- getChar
getChar
y <- getChar
return (x,y)
注意，如果在这个例子中省略 return，就会产生类型错误，因为 (x,y) 是类型为 (Char,Char) 的表达式，而在上面的上下文中，我们需要类型为 IO (Char,Char) 的动作。
10.5 派生原语（Derived primitives）
使用三个基本动作和顺序执行后，现在可以定义若干其他有用的动作原语，它们由标准 Prelude 提供。首先，定义动作 getLine，它从键盘读取一串字符，直到遇到换行字符 '\n'：
getLine :: IO String
getLine = do x <- getChar
if x == '\n' then
return []
else
do xs <- getLine
return (x:xs)
注意这里使用递归：读到第一个字符之后，再读取字符串的其余部分。与之对偶，我们定义原语 putStr 和 putStrLn，它们把字符串写到屏幕上，后者还会换到新行：
putStr :: String -> IO ()
putStr [] = return ()
putStr (x:xs) = do putChar x
putStr xs
putStrLn :: String -> IO ()
putStrLn xs = do putStr xs
putChar '\n'
例如，使用这些原语后，可以定义一个动作，提示用户从键盘输入一个字符串，然后显示其长度：
strlen :: IO ()
strlen = do putStr "Enter a string: "
xs <- getLine
putStr "The string has "
putStr (show (length xs))
putStrLn " characters"
例如：
> strlen
Enter a string: Haskell
The string has 7 characters
10.6 猜词（Hangman）
本章余下部分给出三个复杂度递增的扩展编程示例。第一个示例用一种猜词游戏变体说明 IO 编程基础。游戏开始时，一个玩家秘密输入一个单词；另一个玩家随后通过一系列猜测来推断这个单词。每次猜测后，我们指出秘密单词中哪些字母出现在本次猜测里；当猜测正确时，游戏结束。
我们用自顶向下的方式实现猜词游戏，从一个顶层动作开始。它提示第一个玩家输入秘密单词，然后要求第二个玩家尝试猜出它：
hangman :: IO ()
hangman = do putStrLn "Think of a word:"
word <- sgetLine
putStrLn "Try to guess it:"
play word
现在还需要完成 sgetLine 和 play 的定义。首先，动作 sgetLine 以类似基本动作 getLine 的方式从键盘读取一串字符，不同之处在于它把每个字符回显为短横线符号 '-'，以便隐藏字符串：
sgetLine :: IO String
sgetLine = do x <- getCh
if x == '\n' then
do putChar x
return []
else
do putChar '-'
xs <- sgetLine
return (x:xs)
这个定义中使用的动作 getCh 会从键盘读取单个字符而不回显到屏幕上。它通过库 System.IO 中的原语 hSetEcho 实现：在读取字符之前关闭输入回显，读取之后再打开：
getCh :: IO Char
getCh = do hSetEcho stdin False
x <- getChar
hSetEcho stdin True
return x
只要在脚本开头包含声明 import System.IO，就可以使用原语 hSetEcho。现在回到函数 play，它实现主游戏循环：不断提示第二个玩家输入猜测，直到猜测等于秘密单词：
play :: String -> IO ()
play word = do putStr "? "
guess <- getLine
if guess == word then
putStrLn "You got it!!"
else
do putStrLn (match word guess)
play word
当猜测不正确时，我们使用列表推导式指出秘密单词中哪些字母出现在猜测的任意位置：
match :: String -> String -> String
match xs ys = [if elem x ys then x else '-' | x <- xs]
游戏现在已经完整，可以试运行。例如，如果秘密单词是 nottingham，游戏可能如下进行：
> hangman
Think of a word:
----------
Try to guess it:
? glasgow
-o----g-a-
? utrecht
--tt---h--
? gothenburg
nott-ngh--
? nottingham
You got it!!
10.7 尼姆游戏（Nim）
第二个示例考虑一种尼姆游戏变体。游戏在一个由五行星号组成的棋盘上进行，初始设置如下：
1: * * * * *
2: * * * *
3: * * *
4: * *
5: *
两个玩家轮流从某一行末尾移除一个或多个星号。让棋盘变空的玩家获胜，也就是说，移除棋盘上最后一个或最后几个星号的玩家获胜。为了与上一节猜词游戏的自顶向下开发形成对比，我们用自底向上的方式实现尼姆游戏，先定义一系列辅助函数，然后用它们实现游戏本身。
游戏辅助函数
为简单起见，我们把玩家编号（1 或 2）表示为整数，并使用下面的函数给出下一位玩家：
next :: Int -> Int
next 1 = 2
next 2 = 1
接着，把棋盘表示为一个列表，其中包含每行剩余的星号数量。初始棋盘由列表 [5,4,3,2,1] 给出；当所有行都没有星号时，游戏结束：
type Board = [Int]
initial :: Board
initial = [5,4,3,2,1]
finished :: Board -> Bool
finished = all (== 0)
一次移动由行号和要移除的星号数量指定。如果该行至少包含这么多星号，那么移动有效：
valid :: Board -> Int -> Int -> Bool
valid board row num = board !! (row-1) >= num
回忆一下，列表索引从零开始，因此上面使用了减一。例如，valid initial 1 3 返回 True，因为初始棋盘第一行至少包含三个星号；而 valid initial 4 3 返回 False，因为第四行少于三个星号。一个有效移动可以应用到棋盘上产生新棋盘，方法是使用列表推导式更新每行剩余的星号数量：
move :: Board -> Int -> Int -> Board
move board row num = [update r n | (r,n) <- zip [1..] board]
where update r n = if r == row then n-num else n
例如，move initial 1 3 返回新棋盘 [2,4,3,2,1]，其中第一行被移除了三个星号。
IO 辅助函数
首先定义一个函数，把棋盘的一行显示在屏幕上。它接收行号和剩余星号数量：
putRow :: Int -> Int -> IO ()
putRow row num = do putStr (show row)
putStr ": "
putStrLn (concat (replicate num "* "))
回忆一下，库函数 replicate 会产生一个包含指定数量相同元素的列表。例如：
> putRow 1 5
1: * * * * *
接着，可以使用 putRow 显示棋盘。为简单起见，我们假设棋盘总是精确包含五行：
putBoard :: Board -> IO ()
putBoard [a,b,c,d,e] = do putRow 1 a
putRow 2 b
putRow 3 c
putRow 4 d
putRow 5 e
例如：
> putBoard initial
1: * * * * *
2: * * * *
3: * * *
4: * *
5: *
我们还定义辅助函数 getDigit，它显示一个提示，并从键盘读取单个字符。如果该字符是数字，就把相应整数作为结果值返回；否则显示错误消息，并重新提示用户输入数字：
getDigit :: String -> IO Int
getDigit prompt = do putStr prompt
x <- getChar
newline
if isDigit x then
return (digitToInt x)
else
do putStrLn "ERROR: Invalid digit"
getDigit prompt
函数 digitToInt :: Char -> Int 会把数字字符转换为整数，只要在脚本开头写入 import Data.Char 即可使用它。最后，定义一个换到新行的动作：
newline :: IO ()
newline = putChar '\n'
尼姆游戏本体
使用上面的辅助函数后，现在可以实现主游戏循环。它接收当前棋盘和玩家编号作为参数：
play :: Board -> Int -> IO ()
play board player =
do newline
putBoard board
if finished board then
do newline
putStr "Player "
putStr (show (next player))
putStrLn " wins!!"
else
do newline
putStr "Player "
putStrLn (show player)
row <- getDigit "Enter a row number: "
num <- getDigit "Stars to remove : "
if valid board row num then
play (move board row num) (next player)
else
do newline
putStrLn "ERROR: Invalid move"
play board player
也就是说，先显示棋盘，然后检查游戏是否结束。如果结束，就把另一位玩家显示为胜者，因为正是他让棋盘变空。否则，提示当前玩家输入想要执行的移动。如果移动有效，就相应更新棋盘，并让下一位玩家继续游戏；否则显示错误消息，并重新提示当前玩家输入有效移动。
最后，尼姆游戏本身只需用初始棋盘和玩家编号调用游戏循环即可实现：
nim :: IO ()
nim = play initial 1
关于这个尼姆实现，还可以补充两点。首先，因为 Haskell 是纯语言，我们需要把游戏状态显式作为参数传给 play 函数。在这里，游戏状态由当前棋盘和玩家编号组成。其次，要注意实现中纯部分与不纯部分之间的分离。玩家和棋盘上的辅助函数是纯的，而涉及输入输出的部分是不纯的。在 Haskell 程序中努力维持这种分离是一种好习惯，因为它可以最小化并局部化副作用的使用。
10.8 生命游戏（Life）
第三个也是最后一个交互式编程示例是生命游戏。这个游戏基于细胞来模拟一个简单的演化系统，并在二维棋盘上进行。棋盘上的每个方格要么为空，要么包含一个活细胞。例如，下面的 O 表示活细胞：
.....
...O.
.O.O.
..OO.
.....
棋盘上的每个内部方格都有八个直接邻居：
NW N NE
W x E
SW S SE
为了统一起见，每个外部方格也被看作有八个邻居，方法是假设棋盘可以从上到下、从左到右环绕。也就是说，可以把棋盘想象成一个环面，也就是三维甜甜圈形物体的表面。
给定棋盘的初始配置后，下一代棋盘通过同时把下面规则应用到所有方格得到：
- 如果一个活细胞恰好有两个或三个相邻方格包含活细胞，那么它会存活；
- 如果一个空方格恰好有三个邻居包含活细胞，那么它会诞生一个活细胞，否则保持为空。
例如，把这些规则应用到上面的棋盘，会得到下一代图案。不断用新棋盘重复这个过程，就可以产生一个无限的世代序列。通过仔细设计初始配置，可以在这类序列中观察到许多有趣的行为模式。例如，上面的细胞排列称为滑翔机（glider），它会在连续世代中沿棋盘对角线向下移动。尽管生命游戏很简单，它实际上是计算完备的，也就是说，任意计算过程都可以通过合适编码在其中模拟。本节余下部分展示如何在 Haskell 中实现生命游戏。
屏幕辅助函数
首先定义一些与游戏显示屏幕相关的有用输出辅助函数。第一步是定义一个清屏动作，这可以通过显示适当的控制字符来实现：
cls :: IO ()
cls = putStr "\ESC[2J"
按照惯例，屏幕上每个字符的位置由一对正整数 (x,y) 给出，其中 (1,1) 是左上角。我们用下面的类型表示这种坐标位置：
type Pos = (Int,Int)
然后可以定义一个函数，使用控制字符把光标移动到给定位置，并在该位置显示字符串：
writeat :: Pos -> String -> IO ()
writeat p xs = do goto p
putStr xs
goto :: Pos -> IO ()
goto (x,y) = putStr ("\ESC[" ++ show y ++ ";" ++ show x ++ "H")
生命游戏本体
为简单起见，尼姆游戏假设棋盘大小固定。为了提高灵活性，生命游戏允许通过两个整数值修改棋盘大小，这两个值指定棋盘的方格尺寸：
width :: Int
width = 10
height :: Int
height = 10
使用与屏幕相同的坐标约定，我们把棋盘表示为一个列表，其中包含存在活细胞的 (x,y) 位置：
type Board = [Pos]
例如，上面的初始棋盘可以表示为：
glider :: Board
glider = [(4,2),(2,3),(4,3),(3,4),(4,4)]
使用这种棋盘表示后，很容易在屏幕上显示活细胞，并判断给定位置是活的还是空的：
showcells :: Board -> IO ()
showcells b = sequence_ [writeat p "O" | p <- b]
isAlive :: Board -> Pos -> Bool
isAlive b p = elem p b
isEmpty :: Board -> Pos -> Bool
isEmpty b p = not (isAlive b p)
库函数 sequence_ :: [IO a] -> IO () 会按顺序执行一列动作，丢弃它们的结果值，并且不返回实际结果。接着，定义一个函数返回某个位置的邻居：
neighbs :: Pos -> [Pos]
neighbs (x,y) = map wrap [(x-1,y-1), (x,y-1),
(x+1,y-1), (x-1,y),
(x+1,y), (x-1,y+1),
(x,y+1), (x+1,y+1)]
辅助函数 wrap 会处理棋盘边缘的环绕。它先从给定位置的每个分量中减一，再除以棋盘宽度和高度取余，最后再给每个分量加一：
wrap :: Pos -> Pos
wrap (x,y) = (((x-1) `mod` width) + 1,
((y-1) `mod` height) + 1)
利用函数组合，现在可以定义一个函数来计算给定位置的活邻居数量：先产生邻居列表，再保留其中活着的邻居，最后计算数量：
liveneighbs :: Board -> Pos -> Int
liveneighbs b = length . filter (isAlive b) . neighbs
使用这个函数，就可以直接产生棋盘中那些恰好有两个或三个活邻居的活位置列表，因此它们会存活到下一代：
survivors :: Board -> [Pos]
survivors b = [p | p <- b, elem (liveneighbs b p) [2,3]]
接着，棋盘中那些恰好有三个活邻居的空位置列表，也就是会诞生新细胞的位置，可以如下产生：
births :: Board -> [Pos]
births b = [(x,y) | x <- [1..width],
y <- [1..height],
isEmpty b (x,y),
liveneighbs b (x,y) == 3]
不过，这个定义会考虑棋盘上的每个位置。对于较大的棋盘，一个可能更高效的细化方法是只考虑活细胞的邻居，因为只有这些方格才可能产生新细胞。使用这种方法，函数 births 可以改写如下：
births :: Board -> [Pos]
births b = [p | p <- rmdups (concat (map neighbs b)),
isEmpty b p,
liveneighbs b p == 3]
辅助函数 rmdups 会从列表中移除重复项，上面使用它是为了确保每个潜在新细胞只被考虑一次：
rmdups :: Eq a => [a] -> [a]
rmdups [] = []
rmdups (x:xs) = x : rmdups (filter (/= x) xs)
现在，只要把幸存者列表与新诞生细胞列表拼接起来，就可以产生棋盘的下一代：
nextgen :: Board -> Board
nextgen b = survivors b ++ births b
最后，定义函数 life 实现生命游戏本身。它清屏，显示当前棋盘中的活细胞，等待片刻，然后用下一代继续：
life :: Board -> IO ()
life b = do cls
showcells b
wait 500000
life (nextgen b)
函数 wait 用于把游戏速度放慢到合理水平，可以通过执行给定数量的哑动作来实现：
wait :: Int -> IO ()
wait n = sequence_ [return () | _ <- [1..n]]
你可以试着把 life 函数应用到 glider 示例上，也可以实验一些自己的图案。还要注意，实现生命游戏的大多数定义都是纯函数，只有少量顶层定义涉及输入输出。此外，带有这类副作用的定义与没有副作用的定义可以通过它们类型中是否出现 IO 清楚区分。
10.9 章注（Chapter remarks）
使用 IO 类型执行其他形式的副作用，包括从文件读取和写入文件，在 Haskell Report [4] 中有所讨论；文献 [15] 给出了这个类型的形式化含义。对于特殊应用，事实上可以通过库 System.IO.Unsafe 中的函数 unsafePerformIO :: IO a -> a 从不纯动作回到纯表达式。不过，正如其命名所暗示的，这个函数是不安全的，不应在普通 Haskell 程序中使用，因为它会破坏语言的纯性。
10.10 练习（Exercises）
- 使用列表推导式和库函数
sequence_ :: [IO a] -> IO ()，重新定义putStr :: String -> IO ()。 - 使用递归定义一个版本的
putBoard :: Board -> IO ()，让它可以显示任意大小的尼姆棋盘，而不是只适用于恰好五行星号的棋盘。提示：先定义一个辅助函数，把当前行号作为额外参数。 - 采用与第一个练习类似的方式，使用列表推导式和
sequence_重新定义泛化后的putBoard。 - 定义动作
adder :: IO ()，从键盘读取给定数量的整数，每行一个，然后显示它们的和。例如：
> adder
How many numbers? 5
1
3
5
7
9
The total is 25
提示：先定义一个辅助函数，把当前总和以及还需要读取多少个数字作为参数。你很可能还需要使用库函数 read 和 show。
- 使用函数
sequence :: [IO a] -> IO [a]重新定义adder，该函数会执行一列动作，并返回由这些动作结果组成的列表。 - 使用
getCh，定义动作readLine :: IO String，它的行为与getLine相同，但还允许使用 Delete 键移除字符。提示：Delete 字符是'\DEL'，把光标向后移动一格的控制字符是'\b'。
练习 1-3 的解答见附录 A。