这是一个创建于 747 天前的主题，其中的信息可能已经有所发展或是发生改变。
要求是使用函数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) 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) |
|
5
amlee OP 我明白了我思维卡在哪里，说起来有点搞笑。
我写 js 写习惯了，我总是把 fold 函数比作 reduce 函数思考。 然而 js 里面的 reduce 函数所接受的箭头函数的第一个参数是累计结果，第二参数接收的是容器内部的当前值。 而 foldr 函数中的 fn ，第一个参数是容器内函数的当前值，第二个才是累计结果。 他奶奶的，动态类型没提醒就是烦 |
Select Language