Hw08 题解 (UCB CS61A@2021 Fall)

Q1: My Filter

Write a procedure my-filter, which takes a predicate func and a list lst, and returns a new list containing only elements of the list that satisfy the predicate. The output should contain the elements in the same order that they appeared in the original list.

Note: Make sure that you are not just calling the built-in filter function in Scheme - we are asking you to re-implement this!

写一个可以用在列表上的过滤函数, 如果 func 对元素的判断结果是 #t, 我们就保留这个元素

base case: 空列表, 否则我们就递归分解处理这个问题, 如果当前的元素的值符合条件就把它包括进去否则排除掉

(define (my-filter func lst)
  (cond ((null? lst) '())
        ((func (car lst))
           (cons (car lst) (my-filter func (cdr lst))))
        (else (my-filter func (cdr lst))))
)

Q2: Interleave

Implement the function interleave, which takes a two lists s1 and s2 as arguments. interleave should return a new list that interleaves the elements of the two lists. (In other words, the resulting list should contain elements alternating between s1 and s2.)

If one of the input lists to interleave is shorter than the other, then interleave should alternate elements from both lists until one list has no more elements, and then the remaining elements from the longer list should be added to the end of the new list.

返回一个新的列表, 里面是两个输入的列表的元素交替出现后的结果. 用递归的思路来解决这个问题: 当两个列表都空的时候显然要添加的是 nil.

至于如何递归分解问题: 我们可以采用轮流交换 s1 和 s2 这两个参数. 下面假设我们函数的第一个参数为 first_param, 第二个参数为 second_param. 我们在递归分解的时候就每次都取当前第一个列表的 (car first_param), 然后我们递归调用 (interleave second_param (cdr first_param)). **相当于每次我们递归调用都会往结果里添加一个第一个列表的第一个元素. 那么如果这个第一个列表为空呢?, 我们递归调用 (interleave second_param first_param).

(define (interleave s1 s2)
  (cond ((and (null? s1) (null? s2)) nil)                ; base case: return nil if both are empty
        ((null? s1) (interleave s2 s1))                  ; change the positions of s1 and s2
        (else (cons (car s1) (interleave s2 (cdr s1))))) ; we always insert (car s1) to the result :)
)

Q3: Accumulate

Fill in the definition for the procedure accumulate, which merges the first n natural numbers (ie. 1 to n, inclusive) according to the following parameters:

1. merger: a function of two arguments
2. start: a number with which we start merging with
3. n: the number of natural numbers to merge
4. term: a function of one argument that computes the nth term of a sequence

For example, we can find the product of all the numbers from 1 to 5 by using the multiplication operator as the merger, and starting our product at 1:

算前 n 个数字的“和”(用区间表示是 [1, n]), 给定的参数包括起始值是多少, 两个数之间如何算“和”, 以及如何算出第 i 个数字的值

难点在于, Scheme 里面也没有 while 循环, 我们得把这个算法改为递归的版本. 首先先想一下 base case 是什么, 显然是 n = 1 的时候, 这个时候我们根据 merge 来算 start 和 term(i) 的“和”, 其他情况我们递归分解处理 n - 1 这个子问题

(define (accumulate merger start n term)
  (cond ((= n 1) (merger (term n) start))           ; base case: n = 1
        (else (merger (term n) (accumulate merger start (- n 1) term))))
)

Q4: No Repeats

Implement no-repeats, which takes a list of numbers lst as input and returns a list that has all of the unique elements of lst in the order that they first appear, but no repeats. For example, (no-repeats (list 5 4 5 4 2 2))evaluates to (5 4 2).

Hint: How can you make the first time you see an element in the input list be the first and only time you see the element in the resulting list you return?

Hint: You may find it helpful to use the my-filter procedure with a helper lambda function to use as a filter. To test if two numbers are equal, use the = procedure. To test if two numbers are not equal, use the notprocedure in combination with =.

这一题要求我们对列表做去重工作, 提示说是用 Q1 的 my-filter 函数

显然 base case 是列表为空的时候, 这个时候我们直接返回 nil, 而如果不是空, 我们就要在 (cdr lst) 中删除所有值为 (car lst) 的元素, 这个刚好可以用我们在 Q1 中写的 my-filter 函数

(ps. 因为多了一组括号找 bug 找了好久 😢)

(define (no-repeats lst)
  (cond ((null? lst) nil)
        (else (cons (car lst) 
                    (no-repeats 
                       ; choose the elements that are not equal to `car lst`
                       (my-filter (lambda (x) (not (= x (car lst)))) (cdr lst))))))
)