嵌套映射

序列中的嵌套映射

在上一小节中，我们看到了如何组合 enumerate、map、filter 和 accumulate 来写出更复杂的函数。本小节我们将探讨嵌套映射（nested mapping）的一个例子：对列表调用两次 map。

棋盘网格

Jack 是跳棋的超级粉丝。他想写一个函数，列出 4×4 棋盘上所有的坐标。更具体地说，他希望函数输出：

( (1 . 1) (1 . 2) (1 . 3) (1 . 4)
  (2 . 1) (2 . 2) (2 . 3) (2 . 4)
  (3 . 1) (3 . 2) (3 . 3) (3 . 4)
  (4 . 1) (4 . 2) (4 . 3) (4 . 4) )

注意，坐标表示为一对 x 和 y 坐标，代码输出由这些坐标组成的列表。我们将一步步演示 Jack 如何用已经学过的列表操作技术写出这个函数。

棋盘网格：第一行

首先，我们把问题分成一小块，自底向上推进：写一些代码，返回第一行的坐标列表，即 ( (1 . 1) (2 . 1) (3 . 1) (4 . 1) )。怎么做到呢？我们发现 x 坐标从 1 开始、到 4 结束，而 y 坐标始终是 1。所以，如果我们有列表 (1 2 3 4)，就可以把每个元素与 1 cons 起来。可以这样写：

> (map (lambda (x) (cons x 1))
     (enumerate 1 4))
((1 . 1) (2 . 1) (3 . 1) (4 . 1))

目前为止一切顺利。Jack 很开心。

棋盘网格：所有行

我们已经有了返回第一行坐标列表的代码。既然只有 4 行，技术上我们可以给每行复制一份。

(map    (lambda (x) (cons x **1**))
        (enumerate 1 4))

(map    (lambda (x) (cons x **2**))
        (enumerate 1 4))

(map    (lambda (x) (cons x **3**))
        (enumerate 1 4))

(map    (lambda (x) (cons x **4**))
        (enumerate 1 4))

这倒也行，但大家都知道，复制粘贴代码通常不是好主意。（万一棋盘是 1000×1000 呢？）我们希望保留相同的部分，改动越少越好。注意，第 1、2、3、4 行代码唯一的区别，就是那个用来 cons 的数字。我们可以套用之前的方法：

(map (lambda (y) (map (lambda (x) (cons x y))
                      (enumerate 1 4)))
     (enumerate 1 4))

请注意，内层 λ 负责一行中的每一格，外层 λ 负责棋盘上的每一行。万岁！我们搞定了，对吧？

棋盘网格：压平

这是我们运行当前代码得到的结果：

> (map (lambda (y)
        (map (lambda (x) (cons x y))
             (enumerate 1 4)))
      (enumerate 1 4))
( ((1 . 1) (2 . 1) (3 . 1) (4 . 1))
  ((1 . 2) (2 . 2) (3 . 2) (4 . 2))
  ((1 . 3) (2 . 3) (3 . 3) (4 . 3))
  ((1 . 4) (2 . 4) (3 . 4) (4 . 4)) )

这看起来与我们想要的结果惊人地相似：

( (1 . 1) (2 . 1) (3 . 1) (4 . 1)
  (1 . 2) (2 . 2) (3 . 2) (4 . 2)
  (1 . 3) (2 . 3) (3 . 3) (4 . 3)
  (1 . 4) (2 . 4) (3 . 4) (4 . 4) )

区别在哪里？我们当前的代码返回的是坐标的列表的列表，而我们想要的是坐标的列表。那么，如何”压平”这个列表呢？我们可以用 append 调用 accumulate：

(accumulate append
            nil
            (map (lambda (y)
                    (map (lambda (x) (cons x y)
                (enumerate 1 4))
            (enumerate 1 4))

Flatmap

用 append 调用 accumulate 非常常见，我们把这个过程实现为 flatmap：

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

有了这个定义，我们终于可以写出 Jack 想要的函数了：

(flatmap (lambda (y)
             (map (lambda (x) (cons x y))
                  (enumerate 1 4)))
         (enumerate 1 4))

要点总结

当你想遍历某个列表并把它们的元素配对时，嵌套映射会很有用。为了让函数正确无误，强烈建议像我们这里一样把问题分解开。flatmap 是一个”压平”列表的列表的函数。