17

有问题的代码是这样的：

(define multirember&co
  (lambda (a lat col)
    (cond
     ((null? lat)
      (col (quote ()) (quote ())))
     ((eq? (car lat) a)
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col newlat
                             (cons (car lat) seen)))))
     (else
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col (cons (car lat) newlat)
                             seen))))))

我整天盯着这个，但我似乎不太明白。当您重新定义您正在重新定义的函数时，col但在示例中它们似乎使用了原始定义。为什么不改。如果不传入参数newlat和seen.

很难解释我的问题，因为我似乎只是错过了一块。如果也许有人可以提供比这本书更明确的演练，我也许能够理解它是如何工作的。

4

7 回答 7

21

让我们通过一个例子来说明；也许这会有所帮助。:-) 为简单起见，我将list用作收集器/延续，它只会返回一个包含延续参数的列表。

(multirember&co 'foo '(foo bar) list)

在开始时，

a = 'foo
lat = '(foo bar)
col = list

在第一次迭代中，(eq? (car lat) a)条件匹配，因为lat不是空的，并且第一个元素lat是'foo。这将下一个递归设置为multirember&co：

a = 'foo
lat = '(bar)
col = (lambda (newlat seen)
        (list newlat (cons 'foo seen))

在下一次迭代中，elsematches: sincelat不为空，并且第一个元素lat是'bar（而不是'foo）。因此，对于下一次递归，我们有：

a = 'foo
lat = '()
col = (lambda (newlat seen)
        ((lambda (newlat seen)
           (list newlat (cons 'foo seen)))
         (cons 'bar newlat)
         seen))

为了便于人类阅读（并避免混淆），我们可以重命名参数（由于词法作用域），而不改变程序的语义：

col = (lambda (newlat1 seen1)
        ((lambda (newlat2 seen2)
           (list newlat2 (cons 'foo seen2)))
         (cons 'bar newlat1)
         seen1))

最后，(null? lat)子句匹配，因为lat现在是空的。所以我们叫

(col '() '())

扩展为：

((lambda (newlat1 seen1)
   ((lambda (newlat2 seen2)
      (list newlat2 (cons 'foo seen2)))
    (cons 'bar newlat1)
    seen1))
 '() '())

其中（当替换newlat1 = '()and时seen1 = '()）变为

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 (cons 'bar '())
 '())

或（评估(cons 'bar '())）

((lambda (newlat2 seen2)
   (list newlat2 (cons 'foo seen2)))
 '(bar)
 '())

现在，替换值newlat2 = '(bar)和seen2 = '()，我们得到

(list '(bar) (cons 'foo '()))

或者，换句话说，

(list '(bar) '(foo))

给出我们的最终结果

'((bar) (foo))
于 2011-08-10T01:43:32.707 回答
8

我在这里找到了一个很好的答案：http: //www.michaelharrison.ws/weblog/?p=34

我也一直在为此苦苦挣扎。关键是理解词法作用域（对我来说，à la Javascript）和传递给 eq 而不是 eq 分支上的 multirember&co 的内部函数。明白这一点，你就会明白整个过程。

于 2011-09-07T14:15:24.367 回答
4

上面的链接（http://www.michaelharrison.ws/weblog/?p=34）很好地解释了整个练习如何避免命令式编程（C、Java）需要声明两个“持有者”或“收集者” " 变量（或列表、向量）显式存储在内存中，以便在您遍历列表时捕获您的答案。使用 FP 语言 Scheme 的 continuation，您不会在逐步将测试结果（草莓金枪鱼和箭鱼）“推送”到任何单独创建的“篮子”中；相反，您在发送适当的 consing 函数时将两个列表组合在一起 - 一个用于 eq? 是的，另一个为 eq？false - 通过递归。. . 最后以第三个 col 函数结束，在 TLS 的第一个示例中，它是“a-friend” 它询问为保存所有匹配而构建的列表是否为空（null？）。然后，TLS 要求您再次“运行”multirember&co，使用一个新的“last”col，它只询问包含所有“not tuna”原子的列表它包含多少（“last-friend”）。因此，有两个“第一类”函数用于处理收集任务，即构建两个单独的列表，然后在递归展开结束时，原始 col（“a-friend”）提出最后一个问题。也许“multirember&co”这个名字不是最伟大的名字，因为它确实没有重建列表减去要删除的原子；相反，它构建了两个单独的列表——它们永远不会被显示——然后应用最后的 col (a-friend or last-friend) 。. . 显示#t 或#f，

这是一些输出：

> (multirember&co 'tuna '(and tuna) a-friend)
#f
> (multirember&co 'tuna '(and not) a-friend)
#t

这是一个返回不匹配列表的 col：

(define list-not  (lambda (x y) x))

及其用途：

> (multirember&co 'tuna '(and not) list-not)
(and not)
于 2012-05-19T04:25:07.003 回答
4

multirember&co很长一段时间以来，我一直在努力了解内部发生的事情。问题是，当我认为我已经得到它的那一刻 - 下一个任务/示例证明我没有。

帮助我的是对正在发生的事情进行可视化表示（对我来说，文本演练很难掌握，出于某种原因）。

所以，我整理了两张流程图：

一张，只是展示了不同的递归步骤之间的关系：

显示关系的可视化演练

还有一个，反映实际价值： 现在，每当我觉得我再次失去了“争论的线索”时，我只需参考这个流程图，它就会让我回到正轨。

带有值的可视化演练



通过流程图查看“全图”后，我理解的另一件事是，该a-friend函数只是检查是否seen保存任何值（尽管它以相反的方式返回它，即#f当有值时seen以及#t何时seen为空，这可能会令人困惑。

PS：我做了类似的流程图evens-only*&co，本书后面会出现。

于 2017-09-21T05:44:50.800 回答
2

让我们使用一些等式伪代码，为了清楚起见省略了一些括号（因此，我们f x y为 call编写(f x y)，这是明确的）：

multirember&Co a lat col
    = col [] []                                , IF lat == [] 

    = multirember&Co a (cdr lat)
         ( newlat seen => 
             col newlat
                 (cons (car lat) seen) )       , IF (car lat) == a

    = multirember&Co a (cdr lat)
         ( newlat seen => 
             col (cons (car lat) newlat)
                 seen )                        , OTHERWISE

不言自明，这是做什么的？：） 还没有？:) 用想象中的模式匹配伪代码（带警卫）再次重写，我们有

multirember&Co  =  g   where
    g a [b, ...lat] col | b == a  =  g a lat ( n s =>  col     n     [b, ...s] )
                        | else    =  g a lat ( n s =>  col [b, ...n]     s     )
    g a []          col           =                    col     []        []

模式匹配的语义应该很明显：[b, ...lat]匹配[1,2,3]whereb = 1和lat = [2,3]. 因此，这只是一个三种情况的方程：

  • 当第二个参数是一个空列表时，“收集器”函数col会立即输入两个空列表作为它的两个参数；

  • 当第二个参数（它是一个列表）的头部元素与第一个参数相同时，结果与使用列表尾部递归的结果相同，修改后的收集器 --之后将接收其两个参数,n和s, --将当前头元素（即a）添加到s列表中，并将两个列表提供给此调用的收集器函数col；

  • 否则，头元素将被添加到n列表中，之后被构造的收集器接收，n并且s两者都将被进一步馈送到电流收集器函数中。

换句话说，我们正在处理从递归调用返回的两个结果，如果 head 是a，则将 head 添加到第二个结果，如果不是，则将其添加到第一个。

因此调用

    (g 1 [ 2, 1, 3, 1, 4, 5 ] col)

与（将导致）调用相同

    (col [ 2, ...[3, ...[4, ...[5, ...[]]]]]
         [    1, ...[1,            ...[]]  ])

IE

    (col [ 2,     3,     4,     5          ]
         [    1,     1                     ])

另一种看待它的方式是，以下是另一种等效的表述：

multirember&Co a lat col  =  g a lat id id   where
    id      x  =  x              ; identity function  
    (f ∘ g) x  =  f (g x)        ; function composition
    g a [b, ...lat] c d 
               | b == a  =  g a lat  c     (d ∘ (x => cons b x))  ;    (d ∘ {cons b})
               | else    =  g a lat (c ∘ (x => cons b x))   d     ; (c ∘ {cons b})
    g a []          c d  =  col     (c [])                (d [])

因此

multirember&Co 1 [ 2, 1, 3, 1, 4, 5 ] col 
=
col (((((id ∘ {cons 2}) ∘ {cons 3}) ∘ {cons 4}) ∘ {cons 5}) [])   ; { } is for
    ( ( (id ∘       {cons 1}) ∘ {cons 1}                  ) [])   ;  partial application
=
col     (id   (cons 2     (cons 3     (cons 4    (cons 5   [])))))
        (id         (cons 1     (cons 1                    []) ) )

这显然是一回事。

在另一个伪代码（带有列表推导）中，这表明自己是

multirember&Co a lat col  
   = col [ b for b in lat if (b /= a) ] 
         [ b for b in lat if (b == a) ] 
   = ( ((n,s) => col n s) ∘ {partition {/= a}} ) lat

除了只对列表进行一次lat遍历（在原始代码中），高效地构建模仿原始列表结构的 lambda 函数的嵌套链；然后评估哪个链以创建两个结果，并将它们传递给最顶层的收集器函数col。

所有这些都向我们展示了连续传递样式（就是这样）的力量，它实际上创建了自己的函数调用协议，例如，从每个递归函数调用传回两个结果，即使通常在 lambda 演算中函数只能有一个结果（即使是一对）。

于 2018-01-21T19:51:46.333 回答
1

代码不会像通常那样构建解决方案，但它会构建一个计算解决方案的代码，就像您使用低级操作（如cons、+、-等）而不是使用高级累加器或过滤器来构建树时一样.

这就是为什么很难说过程是迭代的还是递归的，因为根据迭代过程的定义，它们使用有限的内存来存储本地状态。但是，这种进程使用的内存很多，但这是在环境中分配的，而不是在本地参数中。

首先，我在这里复制代码，以便能够在不滚动太多的情况下看到对应关系：

(define multirember&co
  (lambda (a lat col)
    (cond
     ((null? lat)
      (col (quote ()) (quote ())))
     ((eq? (car lat) a)
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col newlat
                             (cons (car lat) seen)))))
     (else
      (multirember&co a
                      (cdr lat)
                      (lambda (newlat seen)
                        (col (cons (car lat) newlat)
                             seen)))))))

让我们尝试拆分问题，看看真正发生了什么。

  • 情况1：
(multirember&co 'a
                '()
                (lambda (x y) (list x y)))

is the same as    

(let ((col (lambda (x y) (list x y))))
  (col '() '()))

这是一个微不足道的案例，它永远不会循环。

现在有趣的案例：

  • 案例二：
(multirember&co 'a
                '(x)
                (lambda (x y) (list x y)))

is the same as    

(let ((col
       (let ((col (lambda (x y) (list x y)))
             (lat '(x))
             (a 'a))
         (lambda (newlat seen)
           (col (cons (car lat) newlat)
                seen)))))
  (col '() '()))

在这种情况下，该过程将生成此代码作为结果，并最终对其进行评估。请注意，在本地它仍然是尾递归的，但在全局上它是一个递归过程，它需要内存不是通过分配某些数据结构，而是让评估器仅分配环境帧。每个循环通过添加 1 个新帧来加深环境。

  • 案例3
(multirember&co 'a
                '(a)
                (lambda (x y) (list x y)))

is the same as    

(let ((col
       (let ((col (lambda (x y) (list x y)))
             (lat '(a))
             (a 'a))
         (lambda (newlat seen)
           (col newlat
                (cons (car lat) seen))))))
  (col '() '()))

这将构建代码，但在另一个分支上，它将结果累积到另一个变量中。

所有其他情况都是这 3 种情况中的 1 种的组合，并且通过添加新层可以清楚地知道每个 1 的作用。

于 2014-08-22T23:00:41.110 回答
0

我希望这个演练有帮助

正如克里斯建议的那样，我已将 newlat/seen 重命名为 n/s 并添加了一个索引。这本书给函数（a-friend new-friend latest-fried）起了可怕的名字，所以我只保留了 L（代表 lambda）和定义。

multirember&co 'tuna '(strawberries tuna and swordfish) a-friend)
  multirember&co 'tuna '(tuna and swordfish) (L(n1 s1)(a-friend (cons 'strawberries n1) s1))
    multirember&co 'tuna '(and swordfish) (L(n2 s2)((L(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))
      multirember&co 'tuna '(swordfish) (L(n3 s3)((L(n2 s2)((L(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2)) (cons 'and n3) s3))
        multirember&co 'tuna '() (L(n4 s4)((L(n3 s3)((L(n2 s2)((L(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2)) (cons 'and n3) s3)) (cons 'swordfish n4) s4))

((lambda(n4 s4)((lambda(n3 s3)((lambda(n2 s2)((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))) (cons 'and n3) s3)) (cons 'swordfish n4) s4)) '() '())
               ((lambda(n3 s3)((lambda(n2 s2)((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))) (cons 'and n3) s3)) '(swordfish) '())
                              ((lambda(n2 s2)((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) n2 (cons 'tuna s2))) '(and swordfish) '())
                                             ((lambda(n1 s1)(a-friend (cons 'strawberries n1) s1)) '(and swordfish) '(tuna))
                                                            (a-friend '(strawberries and swordfish) '(tuna))
于 2014-06-14T14:03:11.263 回答