我如何在不创建点对的情况下附加到列表

Question

我如何将 (1 2 3) 附加到 () 的末尾以使 ((1 2 3))
我如何将 (4 5 6) 附加到 that 的末尾以使 ((1 2 3) (4 5 6))
我如何将 "|" 附加到 that 的末尾以使 ((1 2 3) (4 5 6) "|")

没有点对。

我正在使用 Chicken Scheme，但此时我将从任何方案中获取答案。请注意，这些列表中的任何一个也可以是谁知道什么的嵌套列表......我只是在写一个简单的例子。

注意：@sjamaan 展示了 a 使用 append 的解决方案，该解决方案涉及将所有内容包装在另一个列表中以补偿 append 做的事情，而不是名称所说的内容。

(append (list 1 2 3) "|" ) ;=> (1 2 3 . "|") ;^^ didn't actually append, created a dotted pair (append '(1 2 3) (list 4 5 6)) ;=> (1 2 3 4 5 6) ; don't want unwrapped list ;^^ didn't actually append the list i gave it but appended the contents of the list.

基本上我希望有一个附加方法，它实际上附加你给它的东西，而不是附加它的内容，或者接受它并形成一个点对。也许我只是一个梦想家......我可以写一个 "no really append" 方法，它只接受你给它的任何参数并将它们包装在一个外部列表中以补偿但这只是愚蠢的......当然 scheme 有一些方法可以没有这种疯狂的追加。

Answer 1

您正在寻找的程序毫不奇怪地称为 append（来自 SRFI-1）。它将事物列表附加到另一个列表上。这确实意味着如果您只想添加一个项目，则需要将其列为一个列表：

(append '() '((1 2 3))) => ((1 2 3))
(append '((1 2 3)) '((4 5 6))) => ((1 2 3) (4 5 6))
(append '((1 2 3) (4 5 6)) '("|") ) => ((1 2 3) (4 5 6) "|")

它接受多个参数，这些参数将按顺序相互附加，所以你也可以这样做：

(append '() '((1 2 3)) '((4 5 6)) '("|")) => ((1 2 3) (4 5 6) "|")

希望对您有所帮助！

Answer 2

append 不会将原子附加到列表中。它连接列表。在连接有意义之前，您必须将原子提升到列表中。

(append xs (list y))

但指出具有相同结果的(reverse (cons y (reverse xs)))是有意义的。 reverse 建议如果您需要将原子追加到末尾，您可能会反向构建列表。

Answer 3

这里是追加的方式：

(define (append2 lst1 lst2)
  (if (null? lst1)
      lst2                               ; the second list is unaltered
      (cons (car lst1)
            (append2 (cdr lst1) lst2))))

生成一个由 lst1 和 lst2 中的所有元素组成的对链。它不会在 lst2 中没有的地方成对所以：

(append2 '(1 2 3) '(4 5)) ; ==> (1 2 3 4 5)
(append2 '(1 2 3) '())    ; ==> (1 2 3) and not (1 2 3 ())
(append2 '(1 2 3) '5)     ; ==> (1 2 3 . 5)

请注意，每个像 (1 2 3) 这样的列表实际上是 (1 2 3 . ()) 甚至更正确 (1 . (2 . (3 . ())))

how do i append (1 2 3) to the end of () to make ((1 2 3))

(define (insert-last e lst)
  (let helper ((lst lst))
    (if (pair? lst)
        (cons (car lst)
              (helper (cdr lst)))
        (cons e '()))))

(insert-last '(1 2 3) '())                    
; ==> ((1 2 3))

how do i append (4 5 6) to the end of that to make ((1 2 3) (4 5 6))

(insert-last '(4 5 6) '((1 2 3)))  
; ==> ((1 2 3) (4 5 6))

how do i append "|" to the end of that to make ((1 2 3) (4 5 6) "|")

(insert-last "|" '((1 2 3) (4 5 6)))  
; ==> ((1 2 3) (4 5 6) "|")

知道这很像append。这是制作该列表的最糟糕方法，因为您每次都在制作新列表。每个插入是 O(n)，n 个元素是 O(n^2)。如果您可以按相反的顺序执行此操作，那么您会得到为每个插入执行此 O(1) 而不是 O(n) 的操作。而不是 insert-last 你使用 cons:

(cons '"|" '())               ; ==> ("|")
(cons '(4 5 6) '("|"))        ; ==> ((4 5 6) "|")
(cons '(1 2 3) '((4 5 6) "|") ; ==> ((1 2 3) (4 5 6) "|")

这是 O(1)，处理 n 个元素的 O(n)。如果需要按原顺序做可以累加，然后反转..

(cons '(1 2 3) '())                ; ==> ((1 2 3))
(cons '(4 5 6) '((1 2 3)))         ; ==> ((4 5 6) (1 2 3))
(cons '"|" '((4 5 6) (1 2 3)))   ; ==> ("|" (4 5 6) (1 2 3))
(reverse '("|" (4 5 6) (1 2 3))  ; ==> ((1 2 3) (4 5 6) "|")

这是 O(1)，然后是 O(n)，但它仍然是 O(1) 摊销的。您处理的 n 个元素的复杂度为 O(n)。

Answer 4

无论您是否需要，都会创建缺点单元格，因为列表由缺点单元格组成。

how do i append (1 2 3) to the end of () to make ((1 2 3))

CL-USER 24 > (list '(1 2 3))
((1 2 3))

how do i append (4 5 6) to the end of that to make ((1 2 3) (4 5 6))

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

how do i append "|" to the end of that to make ((1 2 3) (4 5 6) "|")

CL-USER 26 > (append '((1 2 3) (4 5 6)) (list "|"))
((1 2 3) (4 5 6) "|")

我如何在不创建点对的情况下附加到列表

how can i append to a list without creating a dotted pair

scheme

chicken-scheme