如何在Dr.Racket中重新赋值

Question

我正在尝试实现Scheme中的二叉树-Dr.racket，但我在插入时遇到了一些问题！函数。

这是源代码

(define (makeTree leftSubTree root rightSubTree)
  (list leftSubTree root rightSubTree))

(define (subTree part tree)
  (if (null? tree)
      '()
      (part tree)))

(define (root tree)
  (subTree cadr tree))

(define (leftSubTree tree)
  (subTree car tree))

(define (rightSubTree tree)
  (subTree caddr tree))

(define (leaf? tree)
  (and (null? (leftSubTree tree))
       (null? (rightSubTree tree))))

; (define tree (makeTree (makeTree '() 1 '()) 2 (makeTree '() 3 '()))) 

(define (member? tree element)
  (if (null? tree)
      #f
      (or (= (root tree) element)
          (member? (leftSubTree tree) element)
          (member? (rightSubTree tree) element))))

(define (insert! tree element)
  (if (null? tree)
      (set! tree (makeTree '() element '()))
      (if (leaf? tree)
          (cond
            ((> (root tree) element) (set! tree (makeTree (makeTree '() element '()) (root tree) '())))
            ((< (root tree) element) (set! tree (makeTree '() (root tree) (makeTree '() element '()))))
            ((= (root tree) element) '()))
          (cond
            ((= (root tree) element) '())
            ((> (root tree) element) (insert! (leftSubTree tree) element))
            (else  (insert! (rightSubTree tree) element))))))

据我所知布景是这样的！函数更改id所指向的对象的值或

(set! tree (makeTree '() val '()))

会将tree的值更改为只有一个节点的树- val。有人能试着解释一下为什么我错了吗？

Answer 1

您的insert!函数仅影响其自己的名为tree的参数的绑定。

当函数返回时，它的参数绑定将被销毁。

您希望影响对参数tree引用的内存对象结构的更改。这不是set!所做的。它只改变变量的绑定值。

在Scheme中有set-car!和set-cdr!的原语，但是球拍的列表是不可变的。可变列表是用mcons创建的，而不是用cons或list创建的。球拍甚至没有set-car!和朋友，取而代之的是叫它们set-mcar!等等，而且它们不能在用list创建的列表上工作。

您可以使用define-struct将树表示从列表切换到结构。

或者，选择适当的#lang指令放在源文件的开头，例如#lang r5rs so set-car!等；或者使用mcons创建列表，这样如果在#lang racket下工作，就可以使用set-mcar!等

> (define y (mcons 1 (mcons 2 '())))
> y
(mcons 1 (mcons 2 '()))
> (set-mcar! y 11)
> y
(mcons 11 (mcons 2 '()))

Answer 2

怎么啦？

想象一下这段C代码：

void test (int n) {
  n = 6;
}

int v = 1;
test(v);
printf("%d", v)

现在，根据您的Scheme代码，您希望6是打印值，但实际情况并非如此。n是test中的局部变量，就像tree是insert!中的局部变量一样。当您使用set!时，您并没有改变这个值，但是您将标识符应该指向的内容重定向到一个新的(可能是不相关的)值。指向相同值的所有其他绑定仍将指向原始值，因为更改的是绑定n，而不是v。

如何修复它？

最好的办法是根本不变异。

(define (insert tree element)
  (if (tree-empty? tree)
      (make-tree tree-empty element tree-empty)
      (let ((value (tree-value tree))
            (left (tree-left tree))
            (right (tree-right tree)))
        (if (< value element)
            (make-tree (insert left element) value right)
            (make-tree left value (insert right element))))))

您仍然可以像这样替换绑定：

(set! root (insert root 2))

你可以改变节点..这使得你的树是单例的，你需要特别处理一个空根，因为你不能把null变成一个值。解决方案可以是具有空指示的特殊根。

(define tree-left-place values)
(define tree-right-place cddr)
(define tree-value-place cdr)
(define +root-value (list 'root))
(define root (make-tree tree-empty %root-value tree-empty))
(define (insert! tree element)
  (define (insert-helper place)
    (if (tree-empty? (place-value place))
        (set-car! place (make-tree empty-tree element empty-tree))
        (insert! (place-var place) element)))
        
  (let ((value (tree-value tree)))
    (cond ((eq? value +root-value) (set-car! (tree-value-place tree) element))
          ((< element value) (insert-helper (tree-left-place tree)))
          (else (insert-helper (left-right-place tree))))))