Racketで抽象データ型を作る

Racketで抽象データ型（実装を捨象して、コンストラクタとデータを操作する関数だけを意識して使えるデータ型）を定義するのどうやればいいんだろう、となり、とりあえずスタックを書いてみた。

structを使うやり方と、classを使うやり方、両方試してみる。

例題

• pop! push!が可能なスタックを作る。
• リストとベクタによる二種類の実装を提供し、それぞれのコンストラクタも用意する。

structによる解法

• define-genericsでインターフェースを定義
• データの表現をstructとして定義し、#:methodsキーワードでインターフェースを実装
• コンストラクタは関数として用意

#lang racket
(require racket/generic)
(require racket/vector)

(define-generics stack
  (pop! stack)
  (push! stack v))
(provide stack? pop! push!)

(struct list-stack (lst)
  #:mutable
  #:transparent
  #:methods gen:stack
  [(define (pop! s)
     (define lst (list-stack-lst s))
     (define ret (car lst))
     (set-list-stack-lst! s (cdr lst))
     ret)
   (define (push! s v)
     (set-list-stack-lst!
      s
      (cons v (list-stack-lst s))))])

(define (make-list-stack)
 (list-stack '()))
(provide make-list-stack)

(struct vector-stack (vec top)
  #:mutable
  #:transparent
  #:methods gen:stack
  [(define (pop! s)
     (define top (vector-stack-top s))
     (define ret
       (vector-ref (vector-stack-vec s) top))
     (set-vector-stack-top! s (sub1 top))
     ret)
   (define (push! s v)
     (set-vector-stack-top! s 
      (add1 (vector-stack-top s)))
     (vector-set!
      (vector-stack-vec s)
      (vector-stack-top s)
      v))])

(define (make-vector-stack)
  (vector-stack (make-vector 1000) -1))
(provide make-vector-stack)

classによる解法

Javaとかに慣れてる人はこっちの方がわかりやすいかも？

• interfaceでインターフェースを定義
• クラス定義の一部で、フィールド初期化方法としてコンストラクタを用意
• クラス定義の一部で、メソッドとしてインターフェースを実装
• （必要なら）クラスであることを隠蔽する関数を用意

#lang racket
(require racket/vector)

(define stack<%>
  (interface () pop! push!))

(define (pop! s)
  (send s pop!))

(define (push! s v)
  (send s push! v))

(define (stack? v)
  (is-a? v stack<%>))
(provide pop! push! stack?)

(define list-stack%
  (class* object%
    (stack<%>)
    (super-new)
    (define current-lst '()); フィールド初期化
    (define/public (pop!)
      (define ret (car current-lst))
      (set! current-lst (cdr current-lst))
      ret)
    (define/public (push! v)
      (set! current-lst (cons v current-lst)))))

(define (make-list-stack) (new list-stack%))
(provide make-list-stack)

(define vector-stack%
  (class* object%
    (stack<%>)
    (super-new)
    (define current-vec (make-vector 1000)); フィールド初期化
    (define current-top -1); 初期化続き
    (define/public (pop!)
      (define ret
        (vector-ref current-vec current-top))
      (set! current-top (sub1 current-top))
      ret)
    (define/public (push! v)
      (set! current-top (add1 current-top))
      (vector-set! current-vec current-top v))))

(define (make-vector-stack) (new vector-stack%))
(provide make-vector-stack)

感想

コンストラクタを関数として別に用意しなくてよいところはclassを使う記法のほうが綺麗な気がするが、記法としてはstructの方がずっとスッキリしている。

継承が必要になったりするとclassの方が楽だったりするのかな。