cs61a 的一道题，有大佬讲解一下吗？

This topic created in 1299 days ago, the information mentioned may be changed or developed.

要求是使用函数foldr来完成函数foldl2，函数说明在 doctest 。

完成foldl2里面的 step 函数就可以了。

我大概能看出来 fold 函数其实就是 reduce 函数，但是还是没头绪。主要是想知道这类问题该怎么思考。

class Link: """A linked list. >>> s = Link(1) >>> s.first 1 >>> s.rest is Link.empty True >>> s = Link(2, Link(3, Link(4))) >>> s.first = 5 >>> s.rest.first = 6 >>> s.rest.rest = Link.empty >>> s # Displays the contents of repr(s) Link(5, Link(6)) >>> s.rest = Link(7, Link(Link(8, Link(9)))) >>> s Link(5, Link(7, Link(Link(8, Link(9))))) >>> print(s) # Prints str(s) <5 7 <8 9>> """ empty = () def __init__(self, first, rest=empty): assert rst is Link.empty or isinstance(rest, Link) self.first = first self.rest = rest def __repr__(self): if self.rest is not Link.empty: rest_repr = ", " + repr(self.rest) else: rest_repr = "" return "Link(" + repr(self.first) + rest_repr + ")" def __str__(self): string = "<" while self.rest is not Link.empty: string += str(self.first) + " " self = self.rest return string + str(self.first) + ">" def foldr(link, fn, z): """Right fold >>> lst = Link(3, Link(2, Link(1))) >>> foldr(lst, sub, 0) # (3 - (2 - (1 - 0))) 2 >>> foldr(lst, add, 0) # (3 + (2 + (1 + 0))) 6 >>> foldr(lst, mul, 1) # (3 * (2 * (1 * 1))) 6 """ if link is Link.empty: return z return fn(link.first, foldr(link.rest, fn, z)) identity = lambda x: x def foldl2(link, fn, z): """Write foldl using foldr >>> list = Link(3, Link(2, Link(1))) >>> foldl2(list, sub, 0) # (((0 - 3) - 2) - 1) -6 >>> foldl2(list, add, 0) # (((0 + 3) + 2) + 1) 6 >>> foldl2(list, mul, 1) # (((1 * 3) * 2) * 1) 6 """ def step(x, g): "*** YOUR CODE HERE ***" return foldr(link, step, identity)(z)

5 replies 2022-11-06 17:52:52 +08:00

amlee

Nov 6, 2022

漏了一个函数定义
```python
identity = lambda x: x
```

stein42

Nov 6, 2022

# 先用长度为 1 的链表，带进去展开，
# 再用长度为 2 的链表，带进去展开，
# 应该就能写出 step 的定义了。
def step(x, g):
return lambda z: g(fn(z, x))

amlee

Nov 6, 2022

@stein42 没看懂

secondwtq

Nov 6, 2022

那当然是“显然”“易得”啊

假设原链表是 x_1 => x_2 => x_3 => x_4 => ... => x_n
根据最后一行可知 step 一定返回一个有一个参数的函数，进而可知在 foldr 执行过程中每一步都要生成一个函数
根据 foldl 的示例，设最后生成的，用 z 为参数调用的函数为：
foo_0 z = ... fn(fn(fn(fn z x_1) x_2) x_3) x_4 ...
（注意以上的 fn 是 foldl 传入的，即示例中的 add/sub/mul ...，z 也是 foldl 传入的）

现在来推导 foldr 执行过程中间生成的那些函数，观察 foo_0 的形态，设其中的 (fn z x_1) 为 rest_1 ，进而有 fn(fn z x_1) x_2 为 rest_2 ，etc. 于是有：
foo_1 rest_1 = ... fn(fn(fn rest_1 x_2) x_3) x_4 ...
...
foo_m rest_m = ... fn(fn(fn rest_m x_m+1) x_m+2) x_m+3 ...
...
foo_n-1 rest_n-1 = fn rest_n-1 x_n
foo_n rest_n = rest_n
其中运行时的参数 rest_m 应等于 fn(... fn(fn z x_1) x_2) ...) x_m (m <= n)，z 也就是 rest_0 了

然后看看 foo_m 能不能套在 foldr 上，foldr 的 inductive case 可以写成：bar x_m (foldr ...)
因为最后返回的是 foo_0 ，所以上面说的“中间生成的那些函数”其实就是这里每次 (foldr ...) 递归调用返回的函数，即：
foo_0 = bar x_1 foo_1
...
foo_m = bar x_m+1 foo_m+1
...
foo_n = identity
那 foo_m+1 是啥呢：
foo_m+1 rest_m+1 = ... fn(fn(fn rest_m+1 x_m+2) x_m+3) x_m+4 ...

最后就是 bar 怎么写的问题，其实到这比较明显了，就是想办法用 foo_m+1 实现 foo_m
把 foo_m 展开：
bar x_m+1 foo_m+1 = \rest_m -> [ ... fn(fn(fn rest_m x_m+1) x_m+2) x_m+3 ... ]
需要替换掉大括号里面那块，这里唯一可以利用的函数是 foo_m+1 ，两边 x_m+2) x_m+3 ... 这些在 foo_m+1 里面都有，而 rest_m+1 = fn rest_m x_m+1 ，所以 bar x_m+1 foo_m+1 = \rest_m -> foo_m+1 (fn rest_m x_m+1)

amlee

Nov 6, 2022

我明白了我思维卡在哪里，说起来有点搞笑。
我写 js 写习惯了，我总是把 fold 函数比作 reduce 函数思考。
然而 js 里面的 reduce 函数所接受的箭头函数的第一个参数是累计结果，第二参数接收的是容器内部的当前值。
而 foldr 函数中的 fn ，第一个参数是容器内函数的当前值，第二个才是累计结果。

他奶奶的，动态类型没提醒就是烦