这是一个创建于 1070 天前的主题，其中的信息可能已经有所发展或是发生改变。
要求是使用函数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 rest 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)  | 1 amlee OP 漏了一个函数定义 ```python identity = lambda x: x ``` |
 | 2 stein42 2022-11-06 01:09:03 +08:00  1 # 先用长度为 1 的链表，带进去展开， # 再用长度为 2 的链表，带进去展开， # 应该就能写出 step 的定义了。 def step(x, g): return lambda z: g(fn(z, x)) |
 | 4 secondwtq 2022-11-06 05:18:41 +08:00 那当然是“显然”“易得”啊 假设原链表是 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) _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) |
| 5 amlee OP 我明白了我思维卡在哪里，说起来有点搞笑。 我写 js 写习惯了，我总是把 fold 函数比作 reduce 函数思考。 然而 js 里面的 reduce 函数所接受的箭头函数的第一个参数是累计结果，第二参数接收的是容器内部的当前值。 而 foldr 函数中的 fn ，第一个参数是容器内函数的当前值，第二个才是累计结果。 他奶奶的，动态类型没提醒就是烦 |
Select Language