V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
amlee
V2EX  ›  问与答

cs61a 的一道题,有大佬讲解一下吗?

  •  
  •   amlee · 2022-11-06 00:46:30 +08:00 · 1041 次点击
    这是一个创建于 509 天前的主题,其中的信息可能已经有所发展或是发生改变。

    要求是使用函数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)
    
    5 条回复    2022-11-06 17:52:52 +08:00
    amlee
        1
    amlee  
    OP
       2022-11-06 00:51:20 +08:00
    漏了一个函数定义
    ```python
    identity = lambda x: x
    ```
    stein42
        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))
    amlee
        3
    amlee  
    OP
       2022-11-06 01:24:31 +08:00
    @stein42 没看懂😖
    secondwtq
        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)
    amlee
        5
    amlee  
    OP
       2022-11-06 17:52:52 +08:00
    我明白了我思维卡在哪里,说起来有点搞笑。
    我写 js 写习惯了,我总是把 fold 函数比作 reduce 函数思考。
    然而 js 里面的 reduce 函数所接受的箭头函数的第一个参数是累计结果,第二参数接收的是容器内部的当前值。
    而 foldr 函数中的 fn ,第一个参数是容器内函数的当前值,第二个才是累计结果。

    他奶奶的,动态类型没提醒就是烦
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2823 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:58 · PVG 22:58 · LAX 07:58 · JFK 10:58
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.