Skip to main content

Haskell 介绍 - the Game of Life

提示
  • 本 Handout 备份于此处。(不保证与源文件同步)

先决条件

学习目标

在这些笔记中,我们讨论了一个自包含的 Haskell 程序,它具有我们将在接下来的几节课中研究的许多功能。 如果您不了解所有内容,请不要担心。 我们的目标是通过一个有趣的例子来激发这些功能的实用性。

有一个 blackboard file,其中包含此处的材料摘要,以及对上述视频讲座中使用的现有函数式编程语言的讨论。

背景

John Conway 发明的生命游戏是元胞自动机的早期例子,它具有从一组简单规则生成的复杂行为。

规则

Game of Life 从在二维网格的单元格上放置一些标记开始。包含标记的网格单元称为 live,而空单元称为 dead。每个单元格恰好有八个相邻单元格,对应于水平、垂直或对角线直接相邻的单元格。

初始配置称为 seed,或第 0 代。之后,根据以下进化规则确定性地进行游戏,其中细胞与其邻居相互作用:

  1. [Birth.] 一个死细胞正好有三个活的邻居,在下一代就会变成活的。
  2. [Survival.] 一个有两个或三个活邻居的活细胞可以存活到下一代。
  3. [Death.] 如果一个细胞有三个以上的活体邻居,它就会因过度拥挤而死亡;如果它的邻居少于两个,就会因隔离而死亡。

必须澄清的是,规则规定所有这些出生和死亡都是在网格演化到下一代时同时发生的,而不是以任何特定的顺序。

例子

许多初始配置很快就会消亡。

例如,种子

pentagenarian0

在五代后演化为一个空网格。 (由于空网格永远不能被重新填充,所以第 5 代之后的所有世代都是一样的)。)

0 pentagenarian0 1 pentagenarian1 2 pentagenarian2 3 pentagenarian3

4 pentagenarian4 5 pentagenarian5 6 pentagenarian6 7 pentagenarian7

另一方面,一些种子在两个或多个状态的集合之间进入稳定的振荡模式。

0 block0 1 block1 2 block2 3 block3

4 block4 5 block5 6 block6 7 block7


0 pulsar0 1 pulsar1 2 pulsar2 3 pulsar3

4 pulsar4 5 pulsar5 6 pulsar6 7 pulsar7

另一个有趣的例子是康威的滑翔机图案,它在棋盘上缓慢移动,每隔四代就向上和向右漂移一格。

0 glider0 1 glider1 2 glider2 3 glider3

4 glider4 5 glider5 6 glider6 7 glider7

事实证明,生命游戏中的行为可以变得任意复杂 - 事实上,通过将其编码为初始种子并观察其演化,是可以模拟图灵机的!

实施康威的生命游戏

现在让我们看看如何将生命游戏的规则转化为简单的 Haskell 实现。 我们将在这些 markdown 笔记中开发我们需要的所有代码,通过运行 mdtohs.hs 程序,可以自动转换为一个 Haskell 文件,如下所示。

$ cat Life.md | runhaskell ../../Resources/mdtohs.hs > Life.hs

很快我们就会想把游戏做成动画,因此我们需要包括以下导入,以使用一个内置的延迟函数。

import Control.Concurrent

注意,除了这个库,Haskell Standard Prelude 也被自动导入到环境中。

抛开这些官僚主义,让我们转向更实质性的问题,即如何代表游戏的状态。

代表表格和步骤功能

我们可能会认为表示网格的一种方式是将其作为一个具有某种固定数量的行和列的二维布尔阵列。然而,这种表示方法有几个缺点。

  • 官方规则没有对网格的大小做任何限制,而且有些图案(如滑翔机)最终会穿越无限大的单元格区域。
  • 典型的网格配置是稀疏的,即大多数单元是空的。

为了避免这些问题,我们将通过只保持跟踪的单元格来表示一个网格。因此,让我们做以下类型的声明

type Cell = (Int,Int)
type Grid = [Cell]

这定义了 Cell 类型作为机器整数对的同义词,而 Grid 类型作为单元格列表的同义词(机器整数对的列表)。预期的解释是,一个单元是通过给出它的(x,y)坐标来指定的,而一个网格是通过列出它的活单元(坐标)来指定的。

例如,网格

pentagenarian8glider

由以下坐标表表示:

pentagenarian :: Grid
pentagenarian = [(1,2),(2,2),(2,3),(4,1),(4,3)]

glider :: Grid
glider = [(1,3),(2,1),(2,3),(3,2),(3,3)]

现在我们已经确定了表现形式,让我们继续实现生命游戏的规则。我们以几个辅助函数开始。

isLive, isDead :: Cell -> Grid -> Bool
isLive c g = c `elem` g
isDead c g = not (isLive c g)

函数 isLiveisDead 确定坐标 c 处的单元格在给定的网格 g 中是否是活的:由于网格被表示为活单元格的列表,这只是简化为检查 c 是否是 g 的一个元素。

neighbours :: Cell -> [Cell]
neighbours (x,y) = [ (x+i,y+j) | i <- [-1..1], j <- [-1..1], not (i==0 && j==0) ]

函数 neighbours 返回一个给定单元格的八个邻居的列表。这个定义中值得指出的第一个方面是在左侧使用了模式匹配的方法

neighbours (x,y) = {- ... -}

来自动给单元格坐标的两个组成部分命名。这个定义可以用析构器和 let 绑定来等效表达

neighbours c = let x = fst c in let y = snd c in {- ... -}

但通过模式匹配的定义更清晰、更简洁。这个定义的另一个值得指出的方面是在右侧使用了列表的理解

{- ... -} = [ (x+i,y+j) | i <- [-1..1], j <- [-1..1], not (i==0 && j==0) ]

列表理解是 Haskell 的一个强大功能,它模仿了数学中的集合理解符号。上面的表达式构造了一个形式为 (x+i, y+j) 的配对列表,其中 i 和 j 从-1 到 1,但不能都等于 0。(你可以在教科书第 4 章和第 5 章中阅读更多关于模式匹配和列表理解的内容)

下面是在 GHC 解释器中运行的 neighbours 的输出样本:

> neighbours (2,2)
[(1,1),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2),(3,3)]

通过将 neighboursisLive 结合起来,使用另一种列表理解,我们可以计算出一个给定网格内的单元的活邻居。

liveNeighbours :: Grid -> Cell -> [Cell]
liveNeighbours g c = [c' | c' <- neighbours c, isLive c' g]

样本产生的结果:

> liveNeighbours pentagenarian (2,2)
[(1,2),(2,3)]
> liveNeighbours glider (2,2)
[(1,3),(2,1),(2,3),(3,2),(3,3)]

最后,我们把这些成分结合起来,编写了一个函数 step ,它把一个网格作为输入,应用生命游戏的规则,计算出下一代的网格作为输出。

step :: Grid -> Grid
step [] = []
step g =
[(x,y) | x <- [minX-1 .. maxX+1],
y <- [minY-1 .. maxY+1],
(isDead (x,y) g && length (liveNeighbours g (x,y)) == 3)
|| (isLive (x,y) g && length (liveNeighbours g (x,y)) `elem` [2,3])
]
where
minX = minimum [ x | (x,y) <- g ]
maxX = maximum [ x | (x,y) <- g ]
minY = minimum [ y | (x,y) <- g ]
maxY = maximum [ y | (x,y) <- g ]

定义的第一个条款

step [] = []

简单地重复了已经提到的事实,即一个空的网格永远不会被重新填满。第二个条款更微妙一些,所以值得花些时间来理解它。我们首先计算网格中所有活单元的 x 和 y 坐标的最小/最大值。(这一切都发生在 where 块中,尽管它在语法上发生在列表理解的下面,但它是首先被评估的)。) 由于下一代的活细胞必须与当前一代的活细胞在一个距离之内,因此只需考虑从左下角(minX-1, minY-1)到右上角(maxX+1, maxY+1)的矩形细胞(x, y)(见下图中的阴影区域)。

glider shaded

对于位于该区域内的所有单元格,我们接着测试布尔公式

              (isDead (x,y) g && length (liveNeighbours g (x,y)) == 3)
|| (isLive (x,y) g && length (liveNeighbours g (x,y)) `elem` [2,3])

直接表达了 birthsurvival 的逻辑:如果一个死细胞正好有三个邻居,那么它在下一代就会成为活细胞,而如果一个活细胞有两个或三个邻居,它就会生存。( death 的逻辑也隐含在这个公式中,因为一个有三个以上或两个以下活体邻居的细胞将被排除在下一代的活体细胞名单之外)。)

下面是一个与 step 函数交互的例子。

> step pentagenarian
[(1,2),(1,3),(2,2),(2,3),(3,3)]
> step (step pentagenarian)
[(1,2),(1,3),(2,4),(3,2),(3,3)]
> step (step (step pentagenarian))
[(1,3),(2,4),(3,3)]
> step (step (step (step pentagenarian)))
[(2,3),(2,4)]
> step (step (step (step glider)))
[(2,4),(3,2),(3,4),(4,3),(4,4)]

最后一句话:在 step 的定义中,重要的是,条款

step [] = []

出现在句子前

step g = {- ... -}

以涵盖空网格的情况。否则,实现将是不正确的,因为操作 最小最大 在空列表的情况下会引发一个异常。

在终端中实现游戏的可视化

我们将在一个终端中为游戏制作动画,使用Ansi escape code

首先,我们将假设我们的终端有以下尺寸(如果需要的话,为测试而改变):

terminalWidth  = 70
terminalHeight = 22

对于进行输入和输出的程序,我们必须使用 IO() 类型。Ansi 转义代码 ESC[2J 是用来清除终端的。

cls :: IO ()
cls = putStr "\ESC[2J"

如果我们想在终端的某个位置打印一个字符,我们需要用 Ansi 转义代码 Esc[ ,后面有两个数字,用 ; 隔开,以 H 结束,将光标移到那里。

goto :: Cell -> IO ()
goto (x,y) = putStr ("\ESC[" ++ show (terminalHeight-y) ++ ";" ++ show (x+1) ++ "H")

这里我们从终端的高度中减去 y ,因为我们使用的惯例是棋盘的行数是从下到上,而终端的行数是从上到下。 我们还在 x 上加了 1,因为我们希望棋盘的位置(0, 0)与终端的左下角位置相对应。

我们将打印字母O来代表一个活细胞:

printCell :: Cell -> IO ()
printCell (x,y) | x >= 0 && x < terminalWidth
&& y >= 0 && y < terminalHeight = do
goto (x,y)
putChar 'O'

| otherwise = return ()

一个警告是,IO-type 的 return 函数与 Java 的 return 不同。我们将在以后研究单体时看到 return 的确切含义。目前,我们只是说明它的类型:

return :: Monad m => a -> m a

请注意,由于 ma 是变量,所以 return 有一个 polymorphic 类型。在这里,我们将它与单体 m = IO 和类型 a = () 一起使用。

最后,我们在终端渲染一个网格,如下所示:

terminalRender :: Grid -> IO ()
terminalRender g = do
cls
sequence [ printCell c | c <- g ]
goto (0,terminalHeight)

在这种情况下,Haskell 的前导函数 sequence 执行一连串的 IO 操作,一般来说是一连串的单体操作,其类型如下:

sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

这里我们用的是 t a = [a]m = IO

我们还需要一个延迟函数,否则游戏的演变会显示得太快(这需要 import Control.Concurrent)。

delayTenthSec :: Int -> IO ()
delayTenthSec n = threadDelay (n * 10^5)

最后,我们可以在终端将 "生命游戏 "制作成动画,如下所示。

life :: Grid -> IO ()
life seed = f 0 seed
where
f n g = do
terminalRender g
putStrLn (show n)
delayTenthSec 1
f (n+1) (step g)

例子:

main :: IO ()
main = life glider

在实验室机器的终端上运行这个文件,如下所示。

$ module load func-prog
$ git clone https://git.cs.bham.ac.uk/mhe/fp-learning-2021-2022.git
$ cd fp-learning-2021-2022/LectureNotes
$ cat Sections/Life.md | runhaskell ../Resources/mdtohs.hs > Life.hs

接着运行

$ runhaskell Life.hs

或者,运行 ghci Life.hslife gliderlife pentagenarian 或其他例子。

顺便说一下,在实例部分说明的另外两个初始种子可以用列表理解法简洁地表达如下。

block3 :: Grid
block3 = [(x,y) | x <- [1..3], y <- [1..3]]

pulsar :: Grid
pulsar = [(x+i,y) | x <- [2,8], y <- [0,5,7,12], i <- [0..2]] ++ [(x,y+i) | x <- [0,5,7,12], y <- [2,8], i <- [0..2]]

你可以去尝试运行它们!

在 Kotlin 中的实现

Kotlin 是谷歌的开发 Android 应用程序的首选语言

Kotlin 支持函数式编程,正如这个 direct translation 的 Haskell 程序所说明的。

你能把它翻译成 Java,同时保持代码的功能风格吗?

学习完本 Handout 后

实验练习