代码之家 › 专栏 › 技术社区 › Drawkcab Esrever

方案难以理解我的函数“concat list”输出的输出

quote racket scheme

Drawkcab Esrever · 技术社区 · 6 年前

我编写了一个名为“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)

我对这个计划还不熟悉,不知道这是正确的还是现在。请注意,我在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)))))

2 回复 | 直到 6 年前

Will Ness Derri Leahy 6 年前

是,输出正确。

> (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  ^^^
;                                      ------------------

这个追加将这两部分放在一个列表中

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

进入

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

或者,象征性地(“在 伪代码 “”,

           [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中,它在算法上是不利的,因为重复遍历第一个列表以将元素附加到其中会导致 二次型 行为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 这个计划很便宜,所以这很好。但重复地从列表末尾删除一个元素(尚未实现 but-last )在算法上是不利的,因为重复遍历第一个列表以删除其最后一个元素会导致 二次型 行为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] )
                ................................
           [a]   [b ... m n        o p q ... z] 
           [a     b ... m n        o p q ... z]

当我们把第一的元素第一列出,附加剩下的内容,然后我们要做的就是 缺点 结果上的第一个元素!

Haris Nadeem 6 年前

这算吗?

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

这是一个迭代过程(而不是递归过程)。

请注意,如果

列表2为空,只需返回列表1即可。
由于基本情况要求您返回list1,因此只需使用基于不变量的证明,将list1定义为不变量即可。

如果这不起作用,请告诉我,我将尝试帮助您调试代码。