連想リスト

9章2節、連想リスト。
キーと値のペアで保存しといて、キーを元に値にアクセスするアレ。
多くのスクリプト言語などにも、連想配列という形で実現されてたりするな。


Schemeではキーと値のペアをドット対で表現し、連想リストをドット対のリストとして表現する。

((キー1 . 値1) (キー2 . 値2) ... (キーn . 値n))

こんなん。んで連想リストにアクセスするための手続きassocがあるそうな。

gosh> (define *alist* '((foo . 1) (bar . 2) (baz . 3) (qux . 4)))
*alist*
gosh> (assoc 'baz *alist*)
(baz . 3)
gosh> (assoc 'hoge *alist*)
#f

assocは第一引数にアクセスしたいキーと値のペアのキーを、第二引数に連想リストを指定する。
戻り値は、第一引数で指定されたキーが見つかれば、そのキーと値のドット対を返し、見つからなければ#fを返す。
これもifなどの条件式として使えそうだね。


で、assocを自分で定義してみよう、ということでやってみる。

(define my-assoc
  (lambda (key alist . optionals)
    (let-optionals* optionals ((cmp-fn equal?))
      (define loop
        (lmabda (alist)
          (cond
           ((null? alist) #f)
           ((cmp-fn key (car (car alist))) (car alist))
           (else (loop key (cdr alist))))))
      (loop alist))))

ここで気づくことは、以下の3つの手続きにはあるパターンがあるってこと。

  • my-member(ローカル手続きloopを用いた方)
  • delete-1(練習問題のdelete-1ではなく、要素が見つからない場合もconsするバージョンの方)
  • my-assoc

ってことで、次のテーマ「手続きによるパターンの抽象化」へ。