23 Mar 2013

Clojure 学习笔记：生命游戏

本周继续在看「Clojure Programming」这本书，这本书的第三章讲的是 Clojure 的集合和数据结构，作为这章的结束，作者举了一个「生命游戏」的例子来讲解 Clojure 数据结构的使用，作者一共提供了三种方式来解这个生命游戏，其中前两种方式比较好理解，最后一种方式对我来说理解起来比较困难，不过经过几个小时的推敲，总算是基本搞明白了，这里就将我理解的过程记录一下。

关于什么是「生命游戏」，大家可以直接看维基百科：Game of Life。简单地来说，生命游戏的规则就是在一个二维数组里面，有一些元素是“活着的”，有一些元素是“死亡的”，这个二维数组随着每一代的进化，有些元素会死去，有些元素会活过来，具体变化的规则如下：

如果一个元素现在是“活着”的，并且它的邻居里面（周围的 8 个元素）活着的元素的数量少于 2 个，那么这个元素在下一代就会死去。
如果一个元素现在是“活着”的，并且它的邻居里面活着的元素的数量等于 2 个或者 3 个，那么这个元素在下一代会依旧活着。
如果一个元素现在是“活着”的，并且它的邻居里面活着的元素大于 3 个，那么这个元素在下一代周就会死去。
如果一个元素是“死”的，并且它的邻居里面有三个元素是活着的，那么下一代这个元素就会复活。

如果我们对这些规则进行简化，就可以得出以下的结论：

如果一个元素的邻居有 3 个是活着的，那么无论如何，它在下一代中肯定是活着的。
如果一个元素的邻居有 2 个是活着的，那么下一代中的死活状态和本代是一样的。
如果是其他的情况，那么这个元素在下一代肯定会死去。

根据这些规则，「Clojure Programming」这本书给出的代码如下（是的，一共才 11 行代码，不得不感慨 Clojure 真是精简，用 Java 写起来这得多少啊）：

;; 生命游戏
(defn neighbours
  [[x y]]
  (for [dx [-1 0 1] dy [-1 0 1] :when (not= 0 dx dy)]
    [(+ dx x) (+ dy y)]))

(defn step
  "Yields the next state of the world"
  [cells]
  (set (for [[loc n] (frequencies (mapcat neighbours cells))
             :when (or (= n 3) (and (= n 2) (cells loc)))]
         loc)))

这个源代码的前面一个方法比较简单，就是给定一个元素的座标，计算其邻居的各个元素的座标，主要的代码在第二个方法 step 上。

第二个函数接受的参数是一个当前活着的元素座标的列表，结果是下一代存活的元素的集合。先看第二个函数的 for 循环，这个 for 里面有一个

mapcat neighbours cells

这个 mapcat 方法其实是 map 和 concat 两个函数结合，其定义如下：

Returns the result of applying concat to the result of applying map to f and colls. Thus function f should return a collection.

相当于

(concat (map neighbours cells))

在这段代码里面这段函数起到的作用就是将当前所有活着的元素的邻居收到一个集合里面。

收集完成以后，函数对这个集合进行了 frequencies 操作，这个 frequencies 就是统计集合内每一个不同的元素出现的数量。最后对 frequencies 的结果进行解构，就得到 for 循环里面的 loc 和 n 的值，其中：loc 就是当前活着的元素的某个邻居的座标，n 就是这个邻居作为邻居出现次数。

但是，这里有一个点需要注意的，如果一个元素 A 是另一个元素 B 的邻居，那么这个元素 A 的邻居也就包含了 B。换句话说，两个元素总是互为邻居的，也就是，n 是这个元素作为邻居出现的次数，同时也是这个元素周围活着的邻居数量。

这样，for 循环的后面还有的 :when 就可以根据规则对 n 的值进行判断了：

如果 n 为 3，无论如何这个元素在下一代都会活着，所以这个元素的座标就作为结果返回了（就是最后的 loc 那段代码）。
如果 n 为 2，那么需要进行进一步的判断，如果当前元素在 cells 中，也就是说当前元素原来是活着的，根据规则，它下一代依旧会活着，它的座标也会被返回。

最后，所有符合上面的条件的元素都会被返回，这个函数最后就返回了下一代中所有的存活的元素的座标了。