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

[amlee]

要求是使用函数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)

[amlee]

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

[stein42]

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

[amlee]

@stein42 没看懂😖

[secondwtq]

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

假设原链表是 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]

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

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