在方案中追加程序

Question

我最近一直在学习 Scheme，在一个教程中我发现了一个名为 append

的过程

(define append
(lambda (ls1 ls2)
(if (null? ls1)
    ls2
    (cons (car ls1) (append (cdr ls1) ls2)))))

我不明白这背后的逻辑，但明白它将第一个列表的成员一个一个地附加到第二个 list.Can 谁能解释一下程序的最后一行？这两个参数的 cons 是什么意思？

我运行

(trace (append '( a b c) '(d e f)))

并以

结束

[Entering #[compound-procedure 4 append]
Args: (a b c)
      (d e f)]
[Entering #[compound-procedure 4 append]
Args: (b c)
      (d e f)]
[Entering #[compound-procedure 4 append]
Args: (c)
      (d e f)]
[Entering #[compound-procedure 4 append]
Args: ()
      (d e f)]
[(d e f)
  <== #[compound-procedure 4 append]
Args: ()
      (d e f)]
[(c d e f)
  <== #[compound-procedure 4 append]
Args: (c)
      (d e f)]
[(b c d e f)
  <== #[compound-procedure 4 append]
Args: (b c)
      (d e f)]
[(a b c d e f)
  <== #[compound-procedure 4 append]
Args: (a b c)
      (d e f)]
;The object (a b c d e f), passed as an argument to procedure-lambda, is not a procedure.

如果您能解释一下如何阅读这个跟踪结果，那就太好了！

Answer 1

这一行：

(cons (car ls1) (append (cdr ls1) ls2))

只是将第一个列表中的当前元素添加到将第一个列表的其余部分附加到第二个列表的结果中。要理解为什么这最终会起作用，请看一下当第一个列表中的所有元素都被 consed 时递归是如何结束的，我们将第二个列表放在最后：

(if (null? ls1) ls2

这就是它的工作原理！正如您所见，这是一个递归过程。

Answer 2

首先你用错了trace。您需要在要跟踪的过程中调用它，而不是表达式。像这样：

(trace append)

最后一行是 trace 抱怨它无法跟踪列表 (a b c d e f)。您看到的跟踪输出来自之前对 trace 的调用 done right!

现在是如何阅读.. 每个条目看起来像：

[Entering #[compound-procedure 4 append]
Args: (a b c)
      (d e f)]

意思和(append '(a b c) '(d e f))一样。这是同一实例的退出跟踪：

[(a b c d e f)
  <== #[compound-procedure 4 append]
Args: (a b c)
      (d e f)]

这就是 returns (a b c d e f)，电话是 (append '(a b c) '(d e f))。

请注意，这两个并不是紧随其后的。原因是cons步骤需要先等递归步骤做(b c d e f)。所有列表都是从头到尾制作的。

如果我们调用 (append '(a b c) '(d e f)) 会发生以下情况：

(append '(a b c) '(d e f))                          ; ==>
(cons 'a (append '(b c) '(d e f)))                  ; ==>
(cons 'a (cons 'b (append '(c) '(d e f))))          ; ==>
(cons 'a (cons 'b (cons 'c (append '() '(d e f))))) ; <==
(cons 'a (cons 'b (cons 'c '(d e f))))              ; <==
(cons 'a (cons 'b '(c d e f)))                      ; <==
(cons 'a '(b c d e f))                              ; <==
'(a b c d e f)                                      ; result

实际上，参数表达式的计算结果为值，但我在这里引用它们，以便您可以将它们粘贴到 REPL 中，并在所有行上获得相同的结果。

此处的评估顺序与您跟踪中的相同。

在方案中追加程序

Append procedure in scheme

scheme

mit-scheme