Scheme 中的列表（或其他内容）的副本

问题描述 投票：0回答：3

我是计划的新手，发现如果我用 set-car!/set-cdr! 更改列表（甚至在本地）父列表也被修改。这是我的意思的一个例子：

(define my-list '(1 2 3 4 5)) ; Original list

(define (function list) ; Some example function
   (let ((copy list))
        (set-car! copy 'new)
   (display copy)
)

(function my-list); will display (new 2 3 4 5)

my-list; but the original is changed "forever" and will be also '(new 2 3 4 5)


我的问题是： 有没有办法复制原始列表并仅对其进行处理，这样最终原始列表就不会被更改？

list copy scheme racket
3个回答
9
投票

您的代码

(let ((copy list))
允许通过名称副本访问列表。因此，当您
set-car!
复制时，您实际上是
set-car!
正在复制原始列表。

类 Lisp 语言中的突变现象一开始有点令人困惑。

由于您已经发现的原因，突变通常是应该避免的。部分列表和事物四处浮动。这是因为列表中的每个节点在内部都有两个部分 - 

car
是它的值，可能指向另一个列表，而它的 
cdr
是它后面的部分 - 通常这是一些类似于值的东西在
car
。

这可以使用 SRFI1 的列表复制功能解决您的问题 (让((复制(列表-复制列表)))

这是复制列表（创建新列表）的一种方法。这段代码并不完整。当我们在内部查看它时，它会在每个递归调用中添加列表的各个部分。每个新列表部分的片段来自哪里？ 

cdr
是通过调用 
(list-copy (cdr list))
生成的，而 
car
只是简单地获取 - 而不是复制！ - 来自其他列表。

(define (list-copy list)
  (if (null? list) '() (cons (car list) (list-copy (cdr list)))))

您实验时的结果是，您的清单中的汽车

copy
是从
my-list
借来的。

这里有一个更合适的版本：

(define (full-copy list)
(if (null? list) 
  '() 
  (if (list? list) 
      (cons (full-copy (car list)) (full-copy (cdr list)))
      list)))

仅 

car
的代码已更改。现在，汽车被改装成。唯一借用的部分是数字（因此当数字更特殊时，此副本就不合适）。我不确定 srfi1 版本如何工作。

let 语句仅将一个标识符绑定到一个对象 - 该对象不会被复制，您只需通过另一种方式来访问它。因此，任何更改（使用突变，如在以“！”结尾的函数中）都会影响两者。

4
投票

我建议你在学习Scheme或Racket时，避免使用所有

!
功能，例如
set-car!
、
set-cdr!
和
set!
。

不要改变事物，而是尝试从旧事物创造新事物的角度思考。

例如，如果您有一个列表并希望从一开始就有一些新内容：

;; Return a new list with `x` replacing the head of the list `xs`.
(define (replace-head xs x) ; list? any? -> list?
  (cons x (cdr xs)))

;; Using it:
(replace-head '(1 2 3 4 5) 100)
; => '(100 2 3 4 5)

附注可以处理 

replace-head
为空的 
xs
版本可能是：

(define (replace-head xs x) ; list? any? -> list?
  (cond [(empty? xs) (list x)]
        [else        (cons x (cdr xs))]))

(replace-head '(1 2 3 4 5) 100)
; => '(100 2 3 4 5)
(replace-head '() 100)
; => '(100)

您可能还会发现查看如何设计程序很有帮助，其中包含在Scheme或Racket中设计和思考的好方法的示例。

0
投票

其实这可以是一般性的。 MIT/GNU 方案提供了一个参考实现，它考虑了不正确的列表输入，其中包括数字输入等。恕我直言，数字等不能被深度复制，这也意味着它们不是由 

cons
构造的（ 
cons
正如文档所说“返回一个新分配的一对”。）。

注意这与文档中给出的实现不同，它与user3125280的

list-copy
相同。

(define (list-copy items)
  (if (pair? items)
    (let ((head (cons (car items) '())))
      (let loop ((list (cdr items)) (previous head))
        (if (pair? list)
          (let ((new (cons (car list) '())))
            (set-cdr! previous new)
            (loop (cdr list) new))
          (set-cdr! previous list)))
      head)
    items))

跟user3125280说的一样

虽然汽车只是被拿走-而不是复制！ - 来自其他列表。

因此我们可以通过用 

list-copy
包装所有复制操作来进行与 user3125280 相同的更改。以上都是
(car ...)
部分。

然后我们就有了

(define nested-pair (cons (cons 1 2) 3))
(eqv? (car nested-pair) (car (list-copy nested-pair)))
; #f

实际上，我们还可以使用表支持循环列表，这是一种不正确的列表（MIT/GNU 方案中的哈希表不适用于这种情况），如 this QA 所示。

;; 0. https://stackoverflow.com/a/67626797/21294350
;; Here we don't have (id children) structure, so the traversal method needs small modification.
;; The basic ideas are same.
;; 1. See http://community.schemewiki.org/?sicp-ex-4.34 LisScheSic's 2nd comment point 1.
;; Notice make-hash-table in MIT/GNU Scheme can't work one for one key being infinite list or circular.
;; One workaround is to use one naive alist, but that may be inefficient then...
;; Anyway this manipulation should be done for hash-table APIs, so I won't dig into that.
(define (list-copy items)
  ;; These 2 both won't work for circular list at least.
  ; (define get hash-table-ref/default)
  ; (define put! hash-table-set!)
  ; (define constructor make-hash-table)

  ; (define get 1d-table/get)
  ; (define put! 1d-table/put!)
  ; (define constructor make-1d-table)

  ;; similar to wiki
  (define constructor (lambda () (list 'ignore)))
  ;; last-pair returns one reference which can be checked by
  ; (define tmp-table (list 1 2))
  ; (set-cdr! (last-pair tmp-table) (list (cons 2 3)))
  (define (put! table k v) 
    (let ((val (assq k (cdr table))))
      (if val 
        (set-cdr! val v)
        (set-cdr! (last-pair table) (list (cons k v)))))
    )
  (define (get table k default) 
    (let ((val (assq k (cdr table))))
      (or (and val (cdr val)) default)))

  (define (list-copy-internal items visited)
    ;; Here we ensure all car/cdr won't be duplicately visited.
    (if (pair? items)
      (or 
        (get visited items #f)
        (let ((head (cons (list-copy-internal (car items) visited) '())))
          ;; mark as visited and store the value which will be fulfilled later.
          (put! visited items head)
          (let loop ((list (cdr items)) (previous head))
            (if (pair? list)
              (let ((res (get visited list #f)))
                (if res
                  ;; avoid duplicately visiting the same sub-list.
                  (set-cdr! previous res)
                  ;; 0. The original one doesn't consider the case where (car list) is also one list. 
                  ;; 1. The new object is implied by cons.
                  (let ((new (cons (list-copy-internal (car list) visited) '())))
                    (set-cdr! previous new)
                    (loop (cdr list) new))))
              (set-cdr! previous list)))
          head)
        )
      ;; 0. non-pair input. This is general.
      ;; 1. This can't cause the circular case, so no need to track that by hash-table.
      ;; And it is allowed to duplicately visit one number in one traversal.
      items))
  (list-copy-internal items (constructor))
  )

预期结果：

(define circular-list (cons 1 2))
(set-cdr! circular-list circular-list)
(list-copy circular-list)
; #0=(1 . #0#)
(eqv? (list-copy circular-list) circular-list)
; #f
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.