Scheme Difficulty Understanding output of my function 'concat lists' 输出

Question

我写了一个名为 'my-append' 的函数，它接受两个列表 L1、L2 并将 L2 的每个元素附加到 L1 的末尾。（换句话说，它将 L1 与 L2 连接起来）

该函数似乎运行正常，但我似乎得到了一个奇怪的输出。

(my-append '(a b '(1 2 3)) (list '(4 5 6) 7 8 9)) ==>

(list 'a 'b (list 'quote (list 1 2 3)) (list 4 5 6) 7 8 9)

我是 scheme 的新手，不知道这是正确的还是现在。请注意，我在 dr racket 中使用高级学生语言。这是函数的代码。（它使用了两个辅助函数）

;my-append
;takes two lists L1,L2 and returns concat of L2 to L1
;it first checks if either list is empty if so it returns the non empty one
;if both are empty returns empty
;if both are non empty determine which list has smaller length
;calls my-append-helper with first arg as smaller second larger
;append-element
;takes a list L and element x and adds x
; to the end of L
; I am super limited on which operations i can use
; so i must resort to this O(n) algorithm

;my-append-helper
;takes either two non empty lists L1 L2 then
;builds the concatenation of L1 L2
;by stripping of first element of L2
;and adding it to L1

(define (append-element L x)
  (cond ((equal? L '())    
         (list x) )          
        (else           
         (cons (first L)    
                (append-element (rest L) x)))))

(define my-append-helper
  (lambda (L1 L2)
    (cond ( (equal? '() L2)
            L1)
          (else (my-append-helper (append-element L1 (first L2)) (rest L2))))))

(define my-append
  (lambda (L1 L2)
    (cond ( (and (equal? L1 '()) (equal? L2 '()))
            '() )
          ( (equal? L1 '() )
            L2 )
          ( (equal? L2 '() )
            L1)
          ( else
            (my-append-helper L1 L2)))))

Answer 1

这个算吗？

(define (myappend lst1 lst2)
  (cond
    ((null? lst2) lst1)
    (else (myappend (cons lst1 (cons (car lst2) '())) (cdr lst2)))))

这是一个迭代过程（而不是递归）。

注意如果

列表 2 为空，您可以简单地 return 列表 1。
由于您的基本情况要求您 return 您的 list1，只需使用基于不变量的证明，您将 list1 定义为不变量。

如果这不起作用，请告诉我，我会尽力帮助您调试代码。

Answer 2

是的，输出是正确的。

> (my-append '(a b '(1 2 3)) (list '(4 5 6) 7 8 9))
(list 'a 'b (list 'quote (list 1 2 3)) (list 4 5 6) 7 8 9)

它以样式打印，因此在提示时粘贴回时结果相同：

> (list 'a 'b (list 'quote (list 1 2 3)) (list 4 5 6) 7 8 9)
(list 'a 'b (list 'quote (list 1 2 3)) (list 4 5 6) 7 8 9)  ; compare below     vvvvv

我们如何确定它没问题？通过对两个部分执行相同的操作：

> '(a b '(1 2 3))
(list 'a 'b (list 'quote (list 1 2 3)))
;     --------------------------------
>  (list '(4 5 6) 7 8 9)
                                 (list (list 4 5 6) 7 8 9)  ; aligned vertically  ^^^
;                                      ------------------

append只是将两部分放在一个列表中，转

      (list a b c ... n) (list o p q ... z)

进入

      (list a b c ... n        o p q ... z)

或者，象征性地 ("in pseudocode")，

           [a b c ... n]      [o p q ... z]   ; is turned into:
           [a b c ... n        o p q ... z]

关于你的算法。它通过重复步骤

附加两个列表

           [a b c ... n]      [o p q ... z]  
           [a b c ... n]    o   [p q ... z]   
           [a b c ... n o]        [q ... z]

直到第二个列表用完。在列表末尾重复添加一个元素非常适合具有这种原语的语言，例如 Clojure 的 conj，它使用起来很便宜。但在 Scheme 中，它在算法上是不利的，因为重复遍历第一个列表以将元素附加到它会导致 quadratic 行为 w.r.t。时间复杂度（输入数据大小增加两倍，执行时间将增加四倍）。

另一种方法是

           [a b ... m n]      [o p q ... z]  
           [a b ... m]    n   [o p q ... z]   
           [a b ... m]      [n o p q ... z]

直到第一个列表用完：

(define my-append-helper
  (lambda (L1 L2)
    (cond ( (equal? '() L1)
            L2)
          (else (my-append-helper (but-last L1) (cons (last L1) L2))))))
                                           ;     ^^^^ !

cons 在 Scheme 中很便宜，所以很好。但是从列表的末尾重复删除一个元素（使用尚未实现的 but-last）在算法上是不利的，因为重复遍历第一个列表以删除其最后一个元素会导致二次行为 w.r.t。时间复杂度（输入数据大小增加两倍，执行时间将增加四倍）。

虽然我们在 cons 方面走在正确的轨道上，但当我们注意到附加可以按步骤进行时

           [a b ... m n]          [o p q ... z] 
         ( [a]   [b ... m n] )    [o p q ... z]  
           [a] ( [b ... m n]      [o p q ... z] )
                ................................
           [a]   [b ... m n        o p q ... z] 
           [a     b ... m n        o p q ... z]

当我们搁置 first 列表的 first 元素时，追加剩下的内容，然后再添加剩下的所有内容做的是 cons 把第一个元素放到结果上！

Scheme Difficulty Understanding output of my function 'concat lists' 输出

Scheme Difficulty Understanding output of my function 'concat lists' output

scheme

racket

quote