# 斯坦福编程范式 CS107_20

# 接着上节课的 sum-list

我们希望不利用系统提供的递归，自己设计一个计算求和的函数，如下：要求对于 (sum-list '(1 2 3 4 5)) 输出 15

	(define sum-list(num-list)
	(if(null? num-list) 0
	(+(car num-list)
	(sum-list(cdr num-list)))))

下面我们设计一个斐波那契数函数使用递归。

	(define fib(n)
	(if (or (= n 0)
	(= n 1)) n
	(+ (fib(- n 1))
	(fib(- n 2))))

scheme 语言中，不会去提前查看有无语法或者编程错误，如下例子：

	>(if (zero? 0) 4
	(+ "hello" 4.5 '(8 2)))

对于这样的一个例子，if 判断当然是真的，那么就会输出 4，它不会去检查 if 没有通过后的那个错误的语句，对于 scheme，没有执行的语句的所有元素都认为是一个 token，只有当运行的时候，才回去检查 token。

# flatten 函数

对于如下输入，flatten 会输出如下内容。

	>(flatten '(1 2 3 4))
	(1 2 3 4)
	>(flatten '(1 (2 3) 4 ((5))))
	(1 2 3 4 5)

函数实现如下：这里我们使用了一个 cond，cond 类似一个 switch 语句，但是它是关于布尔测试的 swtich 语句。cond 首先判断输入是不是一个空列表，如果是就返回一个空列表；随后 cond 判断输入中有没有嵌套列表，如果嵌套了就去嵌套，即调用本身；如果没有嵌套就直接提取出这个元素。

	(define flatten(sequence)
	(cond (((null? sequence) '())
	((list? (car sequence)
	(append (flatten(car sequence))
	(flatten(cdr sequence))))
	(else (cons (car sequence)
	(flatten (cdr sequence))))))))

# 判断列表是不是按顺序排

函数例子：

	>(sorted? '(1 2 2 4 7))
	#t
	>(sorted '(1 0 4 7 10))
	#f

函数实现。首先如果列表中的元素个数小于 2 那肯定是顺序的，就一个或零个元素。如果按顺序对于列表的每两个元素，第一个元素的值小于第二个元素的值 (cadr 的意思是 car cdr，即第二个元素)，那么列表就是有序的。如果不符合，函数就运行不下去就会返回 false。

	(define sorted? (num-list)
	(or (< (length num-list) 2)
	and (<= (car num-list)
	(cadr num-list))
	(sorted? (cdr num-list))))

# 函数的指针

对于下述代码，它的内存结构如下图所示。car 在被使用的时候总是会整顿成对应的代码。

(car '(1 2 3 4))

# 重写 sorted? 函数

重写 sorted? 函数以实现以下内容，comp 参数是一个内置的函数，比如 > < = 之类的。

	>(sorted? '(1 2 3 4) >=)
	#t
	>(sorted '("a" "b" "d" "c") String<?)
	#f

	(define sorted? (seq comp)
	(or (< (length seq) 2)
	(and (comp (car seq)
	(cadr seq))
	(sorted? (cdr seq) comp))))

下节课讲一些 scheme 的核心内容，以及映射、过滤之类的。

斯坦福编程范式CS107