日拱一卒，伯克利CS61A完结撒花
大家好，日拱一卒，我是梁唐。
今天是伯克利CS61A这门课的最后一节实验课，也是这个系列的完结篇。
从四月初至今，经过了一个多月的漫长学习，我们终于迎来了它的尾声。说真的，从看视频，到写作业、做实验再到把相应的内容写成文章。这一步一步下来，我真的有一种重新回到课堂上课的感觉。即使之前学过Python，对算法也有一定的了解，这节课下来也依然收获满满。
所以再次安利，如果你是中途看到这篇文章，不妨翻下历史记录从头开始，这门课值得每一个CS从业者学习。
还是和以前一样，我们登录官网，下载压缩包。
这次的文件有点多，所有以lab13开头的文件都是我们要用的。
这次的实验课没有新的内容，是本节课的期末测试，对之前讲过的内容进行了一个复习和回顾。
Q1: Compose All
实现compose-all函数，它接收一系列单参数函数，返回一个单参数函数将所有传入的函数应用在一起。比如，如果func是对函数(f, g, h)调用compose-all的结果。那么(func x)应该等价于(h (g (f x)))
(define (compose-all funcs)
'YOUR-CODE-HERE
nil
)
使用ok命令进行测试：python3 ok -q compose-all
答案
首先要确保返回的是一个只有一个参数的函数，但显然我们需要通过递归来遍历所有的funcs，那么就势必需要把funcs也作为参数，这和只有一个参数的设定矛盾了。
要解决这个问题，需要我们再定义一个函数，比如这里我定义了一个dfs函数，它接收funcs表示函数的list，以及一个数x，即执行过程中的中间结果。在dfs函数当中，就是一个经典的递归问题，我们通过判断funcs是否为nil，来判断递归是否结束。
这里要注意一下funcs的执行顺序，按照题目说明是第一个函数最先执行。注意不要写错了，否则结果完全不同。
(define (compose-all funcs)
(define (dfs funcs x)
(if (null? funcs) x
(dfs (cdr funcs) ((car funcs) x))
)
)
(lambda (x)
(dfs funcs x)
)
)
Tail Recursion
尾递归
Q2: Replicate
编写一个尾递归函数，返回一个list，它是x重复n次之后的结果
使用ok进行测试：python3 ok -q tail-replicate
答案
我们之前做过尾递归的问题，如果还记得的话，应该没有难度。
尾递归需要我们在函数的返回语句上不进行任何依赖当前运行环境的操作，最简单的办法就是把递归的结果也当做是函数的参数传入，这样就可以摆脱当前运行环境的依赖。但这样同样会导致参数不匹配，所以还是通过高阶函数来解决。
(define (tail-replicate x n)
(define (dfs x n ret)
(if (= n 0) ret
(dfs x (- n 1) (cons x ret))
)
)
(dfs x n nil)
)
Generators
生成器
给定一个各不相同的元素组成的数组，排列是这个list一个任意的排序。
比如[2, 1, 3], [1, 3, 2], [3, 2, 1]都是list [1, 2, 3]的排列
实现permutations，一个生成器函数，它接收一个list，返回list的所有排列。每一个排列都是一个list。你生成排列的顺序无关紧要。
提示：如果你拥有lst中元素数量减一之后的排列，你怎样生成lst的全排列呢？
给定的代码当中有一个return语句，它的功能像是raise StopIteration。目的是为了让产生的生成器在传入的lst是空时，不会进入return下方的代码部分。这并不会影响生成器的正常返回，因为主体函数当中仍然有yield语句
代码框架：
def permutations(lst):
"""Generates all permutations of sequence LST. Each permutation is a
list of the elements in LST in a different order.
The order of the permutations does not matter.
>>> sorted(permutations([1, 2, 3]))
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
>>> type(permutations([1, 2, 3]))
<class 'generator'>
>>> sorted(permutations((10, 20, 30)))
[[10, 20, 30], [10, 30, 20], [20, 10, 30], [20, 30, 10], [30, 10, 20], [30, 20, 10]]
>>> sorted(permutations("ab"))
[['a', 'b'], ['b', 'a']]
"""
if not lst:
yield []
return
"*** YOUR CODE HERE ***"
使用ok命令进行测试：python3 ok -q permutations
答案
题目已经提示我们了，先去掉最后一个元素，生成长度-1的全排列。然后再将这个元素插入递归得到的全排列，得到lst的排列。
在遍历插入位置的时候，需要考虑最末尾的情况，应该使用for i in range(0, len(lst)+1)最后的+1不可少，否则会少掉v排在最后的排列。
测试样本当中存在tuple，所以最后拼接的时候需要转成list，否则会报错。
def permutations(lst):
if not lst:
yield []
return
"*** YOUR CODE HERE ***"
if len(lst) == 1:
yield lst
return
v = lst[-1]
for p in permutations(lst[:-1]):
for i in range(0, len(p)+1):
yield list(p[:i]) + [v] + list(p[i: ])
Optional Questions
Streams
Q4: Run-Length Encoding
Run-length encoding是一个非常简单的数据压缩技术，这项技术把相同的数压缩成一个数。一个相同的数字序列被称为一个run。比如下面这个有限序列：
它可以被分成4个run：
注意，每个list中的第一个元素是run中的元素，第二个元素是它出现的次数。我们将会在stream上延续这个做法。编写一个函数叫做rle，它读入一个数据流，返回一个对应的二元数组组成的流，将数据压缩表示成run的形式。你不需要考虑压缩run长度无限的情况
使用ok命令进行测试：python3 ok -q rle
答案
对scheme中流定义的复习，记不清楚的同学可以去翻一下之前的作业。
(define (rle s)
(define (helper v cnt s)
(cond
((null? s) (cons-stream (list v cnt) nil))
((equal? v (car s)) (helper v (+ cnt 1) (cdr-stream s)))
(else (cons-stream (list v cnt) (helper (car s) 1 (cdr-stream s))))
)
)
(if (null? s) nil (helper (car s) 1 (cdr-stream s)))
)
More Tail Recursion
下面的题目将在lab13_extra.scm中完成
Q5: Insert
编写一个尾递归函数，将n插入一个有序list当中
提示：scheme内置的函数append可以拼接两个list
使用ok进行测试：python3 ok -q insert
ok测试只能检查你的结果是否准确，不能检查你是否使用了尾递归。你可以使用一些人工的大测试样例来检查比如：
答案
同样使用高阶函数来解决尾递归需要传入更多参数的问题。
在本题当中，我们遍历n插入的位置，会将s分成两个部分，我们分别存储在prev和suf当中。将这两个部分都传入递归当中，即可进行尾递归。
(define (insert n s)
(define (helper n prev suf)
(if (null? suf) (append prev (list n))
(if (< n (car suf))
(append (if (null? prev) (list n) (append prev (list n))) suf)
(helper n (append prev (list (car suf))) (cdr suf))
)
)
)
(helper n nil s)
)
Q6: Deep Map
实现deep-map函数，它接收一个函数fn和一个嵌套的list s。嵌套的list当中它的每一个元素都可能是另外一个list。比如(1 (2) 3)。
它返回一个list，和s结构一样，但当中的每一个元素都是调用fn之后的结果，比如：
你可以使用list?来检查一个值是否是list
使用ok进行测试：python3 ok -q deep-map
答案
答案
这也是老题目了，我们之前做过很多类似的
(define (deep-map fn s)
(if (null? s) nil
(if (list? (car s))
(cons (deep-map fn (car s)) (deep-map fn (cdr s)))
(cons (fn (car s)) (deep-map fn (cdr s)))
)
)
)
Q7: Tally
实现tally，接收一个list names，返回一个list的pair。每一个pair包含一个names中一个不重复的名字。每一个pair包含名字和它出现的次数。每一个name只会在答案中出现一次，并且按照它在names中的顺序排列
提示：使用eq?过程来判断两个name是否相等
提示：如果你发现你的过程太复杂，你可以试试实现count和unique两个过程。你也可以试试使用map和filter
使用ok命令进行测试：python3 ok -q tally
答案
这题非常麻烦，最好顺着老师的思路来。老师已经为我们提供了map和filter，我们可以在此基础上实现unique和count。
count非常简单，就是一个递归的简单使用。
unique如果我们自己实现也会非常麻烦，使用filter之后会变得简单很多。
理清楚逻辑之后再编码，实现起来会简单很多。
(define (map fn s)
(if (null? s) nil
(cons (fn (car s))
(map fn (cdr s)))))
(define (filter fn s)
(cond ((null? s) nil)
((fn (car s)) (cons (car s)
(filter fn (cdr s))))
(else (filter fn (cdr s)))))
; Implementing and using these helper procedures is optional. You are allowed
; to delete them.
(define (unique s)
(if (null? s) nil
(cons (car s) (filter (lambda (x) (not (eq? (car s) x))) (unique (cdr s))))
)
)
(define (count name s)
(if (null? s) 0
(if (eq? name (car s))
(+ 1 (count name (cdr s)))
(count name (cdr s))
)
)
)
(define (tally names)
(map (lambda (x) (cons x (count x names))) (unique names))
)
More Generators
Q8: Generators generator
编写一个生成器函数make_generators_generator，它接收一个0入参的生成器g，返回一个yield生成器的生成器。对于g返回的生成器，每次获得一个元素e，g就会新创建一个生成器，可以生成从1至e。
def make_generators_generator(g):
"""Generates all the "sub"-generators of the generator returned by
the generator function g.
>>> def ints_to(n):
... for i in range(1, n + 1):
... yield i
...
>>> def ints_to_5():
... for item in ints_to(5):
... yield item
...
>>> for gen in make_generators_generator(ints_to_5):
... print("Next Generator:")
... for item in gen:
... print(item)
...
Next Generator:
1
Next Generator:
1
2
Next Generator:
1
2
3
Next Generator:
1
2
3
4
Next Generator:
1
2
3
4
5
"""
"*** YOUR CODE HERE ***"
使用ok命令进行测试：python3 ok -q make_generators_generator
答案
def make_generators_generator(g):
def f(elems):
yield elems
elems = []
for i in g():
elems.append(i)
yield from f(elems)