计划附加到列表而不附加？

Question

我一直在尝试在不使用附加运算符的情况下将 s 表达式附加到方案中的列表。到目前为止，我已经尝试使用一个名为 'next-member' 的辅助函数来迭代列表的下一项。这可能是一个基本的递归问题，由于我是 Scheme 语法的新手，所以我无法理解它：

(define next-member
  (lambda lst
    (cond
      ((not (null? lst)) (car lst))
      (else (next-member (cdr lst)))
      )))

(define append-item
  (lambda (a b)
    (cond
      ((null? b) (list a))
      ((null? a) b)
      (else (list (car b) (next-member (cdr b)) a))
      )))

Answer 1

您不需要任何辅助函数 - 您需要了解函数 cons 以及它如何用于创建列表。

函数 cons 调用从两个参数创建一个点对：

> (cons 1 2)
'(1 . 2)

第二个参数可以是列表，然后第一个参数作为该列表的第一个元素的新列表是 returned:

> (cons 1 '())
'(1)
> '(1 . ())
'(1)
> (cons 1 '(2 3))
'(1 2 3)
> '(1 . (2 3))
'(1 2 3)

列表构建为 cons 调用链，其中最后一对的最后一个元素是空列表：

> (cons 1 (cons 2 (cons 3 '())))
'(1 2 3)
> '(1 . (2 . (3 . ())))
'(1 2 3)

那么，想象一下这个任务的解决方案：

如果第一个参数为空，return 第二个参数。
如果第二个参数为空，return 第一个参数。
否则使用第一个列表中的元素递归构建点对链，当你到达末尾时，将第二个列表放在末尾。像这样：

> (cons 1 (cons 2 (cons 3 '(4 5 6))))
'(1 2 3 4 5 6)

整个解决方案：

(define (append-list lst1 lst2)
  (cond ((null? lst1) lst2)
        ((null? lst2) lst1)
        (else (cons (car lst1)
                    (append-list (cdr lst1) lst2)))))

示例：

> (append-list '() '(1 2 3))
'(1 2 3)
> (append-list '(1 2 3) '())
'(1 2 3)
> (append-list '(1 2 3) '(4 5 6))
'(1 2 3 4 5 6)

Answer 2

你的问题不是语法，而是语义。

您的第一个函数说“non-empty 列表的 'next element' 是它的头部；空列表的 'next element' 是它的尾部的 'next element'”。
这没有意义 - 一个空列表没有尾巴（并且不清楚您希望此函数完成什么）。

你的第二个函数说“为了将 a 附加到 b，创建一个包含三个元素的列表：b 的第一个元素，'next element' (cdr b)、a”。

看起来您真正想要做的是在列表末尾添加一个元素。

你可以用最基本的list-recursion“模式”来做到这一点：

如果列表为空，请执行某些操作
否则，做一些涉及列表头部和尾部递归结果的事情。

在你的问题中，基本情况很简单；它是 a:

的单例列表

(define (append-item a bs)
    (if (null? bs)
        (list a)

为了递归，你意识到可以通过last-appending元素到bs的尾部然后将bs的第一个元素添加到前面：

        (cons (car bs) (append-item a (cdr bs)))))

附带说明一下，此函数的传统名称是 snoc，即“cons”的倒数。
（另一方面，“s-expression”是源代码；您不能将其附加到任何内容。）

Answer 3

另一种方法是定义带有突变的追加（有时调用append!或有时调用nconc）。这个想法是改变最后一个列表元素的 cdr 指向第二个列表而不是指向 '().

其他方法是use folding。

Answer 4

Append 不是原语； cons 是。您可以使用 cons 轻松创建 append。这是两个参数版本的直接实现：

(define (my-append a b)
  (if (null? a)
      b
      (cons (car a) 
            (my-append (cdr a) b))))

list 以及其余参数也在幕后使用 cons 。如果是成对的，它们是用 cons 创建的，没有别的！

计划附加到列表而不附加？

Scheme appending to a list without append?

scheme

racket