在 Scheme 中操作可变数据中的列表

Question

我刚刚开始学习可变数据，在使用 set! 命令时遇到了一些递归处理列表的问题。虽然我的大多数方法在此函数中都能正常工作，但删除和基数函数却不能，而且我不确定如何在此类函数中解决此问题。

(define (basic-set)
  (let ((set '()))
    (define (empty?)
      (null? set))
    (define (insert s)
      (set! set (cons s set)))
    (define (delete s)
      (cond ((equal? (car set) s)(set! set (cons (cdr set)'())))
            (else ((delete s)(cdr set)))))
    (define (element? s)
      (cond ((equal? (car set) s)#t)
            (else ((element? s)(cdr set)))))
    (define (cardinality)
      (cond ((null? set)0)
            (else
            (+ 1 ((cardinality)(cdr set))))))
    (lambda (method)
      (cond ((eq? method 'empty) empty?)
            ((eq? method 'insert) insert)
            ((eq? method 'delete) delete)
            ((eq? method 'element) element?)
            ((eq? method 'cardinality) cardinality)))))

Answer 1

您必须小心实施 delete、element? 和 cardinality 的方式 - 这些过程必须迭代存储为可变数据的集合，为此你必须将集合作为参数传递，我会使用命名的 let.

此外，实现delete是有技巧的，正确的做法是消除元素，然后在最后更新状态。这就是我的意思：

(define (basic-set)
  (let ((set '()))
    (define (empty?)
      (null? set))
    (define (insert s)
      (set! set (cons s set)))
    (define (delete s)
      (define (helper set)
        (cond ((null? set) '())
              ((equal? (car set) s) (cdr set))
              (else (cons (car set) (helper (cdr set))))))
      (set! set (helper set)))
    (define (element? s)
      (let loop ((set set))
        (cond ((null? set) #f)
              ((equal? (car set) s) #t)
              (else (loop (cdr set))))))
    (define (cardinality)
      (let loop ((set set))
        (cond ((null? set) 0)
              (else (+ 1 (loop (cdr set)))))))
    (lambda (method)
      (cond ((eq? method 'empty) empty?)
            ((eq? method 'insert) insert)
            ((eq? method 'delete) delete)
            ((eq? method 'element) element?)
            ((eq? method 'cardinality) cardinality)))))

例如：

(define s (basic-set))

((s 'insert) 'x)
((s 'insert) 'y)
((s 'element) 'x)
=> #t
((s 'cardinality))
=> 2
((s 'delete) 'x)
((s 'cardinality))
=> 1
((s 'empty))
=> #f

Answer 2

这里的另一种方法是匿名函数将外部接口数量与内部方法数量相匹配。当然比 Oscar 的解决方案更难看，但有时最好在担心漂亮之前让它发挥作用。

(define (basic-set)
  (let ((set '()))
    (define (empty?)
      (null? set))
    (define (insert s)
      (set! set (cons s set)))
    (define (delete s L)
     (set! set 
       (let loop ((L L))
         (cond ((null? L) '())            
               ((equal? (car L) s) (cdr L))
               (else (cons (car L) (loop (cdr L)))))))
    (define (element? s L)
      (cond ((equal? (car L) s) #t)
            (else (element? s  (cdr L)))))
    (define (cardinality L)
      (cond ((null? L) 0)
            (else
             (+ 1 ((cardinality)(cdr L))))))
    (lambda (method)
      (cond ((eq? method 'empty) empty?)
            ((eq? method 'insert) insert)
            ((eq? method 'delete) (lambda (s) (delete s set)))
            ((eq? method 'element) (lambda (s) (element? s set)))
            ((eq? method 'cardinality) (lambda () (cardinality set)))))))

在 Scheme 中操作可变数据中的列表

Manipulating Lists in Mutable Data in Scheme

scheme

mutable