# 斯坦福编程范式 CS107_23

# Scheme 内存模型

>'(1 2 3)

对于上述的数据，他的内存结构如下所示。

当使用以下命令时，scheme 会创建一个全局符号表，这个东西交 seq ，它会与这个变量关联起来。

>(define seq '(1 2 3))

当使用 cons 命令时，如下所示。cons 在合并两个列表的时候其实是构造了一个新列表，如下图所示。

>(cons '(1 2 3) '(4 5 6))

因此，输出的结果是如下所示的。

((1 2 3) 4 5 6)

下面让我们用两种方式构建一个列表：

((1 2) 1 2)

# 第一种方法

>(cons '(1 2) '(1 2))

这种方法和上面描述 cons 的使用大差不差，我们主要来介绍第二种方法。

# 第二种方法

使用如下内存存储方式：

如果想要构造如上所示的列表，那么我们要用到一点技巧。

((lambda(x) (cons x x)) '(1 2))

通过上述代码我们构造了一个列表，并且将这个列表绑定到另一个上面，该变量在该定义中用到两次。最终使 car 和 cdr 域都指向同一个内容。

# 改造我们之前的只能处理一元的 map

先把之前的那个一元的 map 重写一遍：

	(define (unary-map fn seq)
	(if (null? seq) ()
	(cons (fn (car seq))
	(unary-map fn
	(cdr seq)))))

为了使这个 map 能够容纳多个参数，我们需要使用 ... 在 scheme 中。

如下例子所示，这个函数 bar 在接受完参数 a、b、c 之后，剩下的所有参数都需要以列表的形式存放在参数 d 中再传入给函数。随后我们再用 list 将这些参数存放在一个列表中，我们看看随意调用会发生什么。

	(define (bar a b c . d)
	(list a b c d))

	>(bar 1 2 3 4 5 6)
	(1 2 3 (4 5 6))

	>(bar 1 2 3)
	(1 2 3 ())

这个例子显示出点在 scheme 中的具体用法。

下面我们来构造我们的一般性的 map 函数，它会需要用到我们之前的一元参数的 map 函数，所以我们在开头提前把它写了出来。

# map 的实现思想

我们最终的 map 要实现 scheme 中一模一样的功能：

	>(map car '((1 2) (3 4) (5 6 7)))
	(1 3 5)

	>(map + '(1 2) '(10 20) '(100 400))
	(111 422)

	>(map * '(1) '(2) '(3) '(4) '(5))
	(120)

简单起见。我们先假设，first-list 这一列表，与 other-lists 里面的所有列表长度相同。

	(define (map fn first-list . other-lists)
	(if (null? first-list) '()
	(cons (apply fn (cons (car first-list) (unary-map car other-lists)))
	(apply map
	(cons fn
	(cons (cdr first-list)
	(unary-map cdr other-lists))))

我们来举一个例子来对上述复杂的代码进行测试。

>(map list (1 10 100) (2 20 200) (3 30 300))

第一次调用第一个接收第一块数据 (1 10 100) 将它绑定到 first-list 上；其他的 ((2 20 200) (3 30 300)) 都绑定到 other-lists 上；使用 unary-map list other-lists 我们得到了 (2 3) ；随后是 cons (car first-list) (unary-map list other-lists) 得到了 (1 2 3) ；随后我们对上述结果使用 apply fn 即 apply list 最终得到了 ((1 2 3)) 。

接下来递归的部分，对 other-lists 的 cdr 部分，即 ((20 200) (30 300)) 进行 map，之后我们使用 cons (cdr first-list) 把第一个列表中的 cdr 部分加在它们前面；得到 ((10 100) (20 200) (30 300)) ；然后再把 fn 放在这整个部分的最前面，得到 (list (10 100) (20 200) (30 300)) ；最后再使用 apply map 对这整个部分进行递归计算，即 (map list (10 100) (20 200) (30 300)) 。