球拍中的可变堆栈

Question

我正在学习Racket，并实现了一个可变堆栈，它只是包含一个大小和缓冲区列表的底层struct的一堆包装器(因此，就计算复杂性而言，它并不是最优的)。在查阅了#racket并阅读了Greg的对宏的恐惧的前半部分之后，我能够为实现编写我想要的语法转换。

(module stack racket
  (module stack-implementation racket
    (struct stack (size buffer) #:mutable)

    ;; size :: stack -> integer
    (define (size stack) (stack-size stack))

    ;; non-empty-stack? :: stack -> boolean
    (define (non-empty-stack? stack)
      (and
        (stack? stack)
        (positive? (stack-size stack))))

    ;; push! :: stack -> any (new item) -> integer (size)
    (define (push! stack item)
      (set-stack-buffer! stack
        (append (list item) (stack-buffer stack)))

      (set-stack-size! stack (+ (stack-size stack) 1))

      (stack-size stack))

    ;; pop! :: (non-empty) stack -> any (head)
    (define (pop! stack)
      (let ([head (car (stack-buffer stack))]
            [tail (cdr (stack-buffer stack))])

        (set-stack-buffer! stack tail)
        (set-stack-size! stack (- (stack-size stack) 1))

        head))

    ;; make
    (define-syntax-rule (make name)
      (define name (stack 0 '())))

    (provide make
             stack?
             (contract-out
               [size  (-> stack?            integer?)]
               [push! (-> stack? any/c      integer?)]
               [pop!  (-> non-empty-stack?  any)])))

  (require 'stack-implementation
           (for-syntax racket/syntax))

  ;; make-stack
  ;  Defines a stack under the specified symbol <name>
  ;  Plus defines <name>-size, <name>-empty?, <name>-push! and <name>-pop!
  (define-syntax (make-stack stx)
    (syntax-case stx ()
      [(_ name)
        (with-syntax ([(size-fn empty-fn push-fn pop-fn)
                       (map (lambda (fn) (format-id stx "~a-~a" #'name fn))
                            '("size" "empty?" "push!" "pop!"))])
          #'(begin
              (make name)
              (define (size-fn)      (size name))
              (define (empty-fn)     (zero? (size-fn)))
              (define (push-fn item) (push! name item))
              (define (pop-fn)       (pop!  name))))]))

  (provide make-stack
           stack?))

我对Racket和Lisp完全陌生，所以我猜想这里除了使用更好的底层数据结构之外，还有很多改进(例如，在宏中定义助手函数ID的复制)。

Answer 1

许多Lisp程序非常自由地使用cons单元，而不是添加单独的堆栈结构，从这个意义上说，您对复杂性的关注可能不那么关键。由于堆栈还包含列表的长度，它实际上至少很好地支持附加大小运算符。当然，为底层(可调整大小的)向量编写更多代码可能是有意义的，但我也不认为这是必要的。

对于代码，我只有一些小建议，因为它写得很好，并且清楚每个部分的含义；虽然我不太熟悉Racket，但我很容易读懂它。

• 对于模式(+/- x 1)，还有可以使用的函数add1和sub1。
• non-empty-stack?只需检查buffer是null?还是empty?。positive?听起来似乎存在一些风险，即堆栈大小可能会因为某种原因而变为负值。出于同样的原因，合同可能也可以收紧，以检查非负整数。
• (append (list x) y)比(cons x y)短一点。