連想リスト・ハッシュテーブル
数学的でアルゴリズム的なものは背伸び感が否めないので、自分で実際に使いそうなもので練習することにします。今回は、辞書を作ります。これは、過去ネタの流用でもあります。
Lispの連想リスト(association list)はalistとも呼ばれ、良く使われるデータ構造のひとつ。構造は「ペア」の「リスト」になっています(詳しくは、「Lisp 連想リスト」で検索)。ハッシュテーブルは、詳しくは知りませんが、いわゆるそれでしょう。
では、まず連想リストを使って実装します。処理イメージは、Rubyだと以下のような感じです。
class Dictionary < Hash def add_entry (key, value) self[key] = value end def lookup (key) self[key] end end dictionary = Dictionary.new dictionary.add_entry("carrot", "にんじん") dictionary.add_entry("radish", "だいこん") dictionary.add_entry("burdock", "ごぼう") p dictionary p dictionary.lookup("radish")
命名規則や慣例などのLispの流儀は未だよく分かってないのですが、それっぽいと思われるものをつけています。
(12/18)id:smegheadさんより頂いたコメントを参考に追記しました。
CommonLisp + alist
最初は連想リストを使って書いてみます。
;; ※これは上手くいかない (defvar *dictionary* nil) ;; 辞書のインタフェース (defun dictionary-add-entry (key value) (push (cons key value) *dictionary*)) (defun dictionary-lookup (key) (cdr (assoc key *dictionary*))) ;; 辞書データ登録 (dictionary-add-entry "carrot" "にんじん") (dictionary-add-entry "radish" "だいこん") (dictionary-add-entry "burdock" "ごぼう") (print *dictionary*) ;; 辞書を参照 (print (dictionary-lookup "radish"))
$ clisp dictionary.lisp (("burdock" . "ごぼう") ("radish" . "だいこん") ("carrot" . "にんじん")) NIL $
最後は"だいこん"が表示されると思いきや、表示されません。連想リストは上手く出来ているように見えます。何がいけないのでしょう?
参考書やサイトで見られるコード例では、キーも値もシンボルが使われています。ここではキーだけシンボルにしてみましょう。
(defvar *dictionary* nil) ;; 辞書のインタフェース (defun dictionary-add-entry (key value) (push (cons key value) *dictionary*)) (defun dictionary-lookup (key) (cdr (assoc key *dictionary*))) ;; 辞書データ登録 (dictionary-add-entry 'carrot "にんじん") (dictionary-add-entry 'radish "だいこん") (dictionary-add-entry 'burdock "ごぼう") (print *dictionary*) ;; 辞書を参照 (print (dictionary-lookup 'radish))
$ clisp dictionary.lisp ((BURDOCK . "ごぼう") (RADISH . "だいこん") (CARROT . "にんじん")) "だいこん" $
こちらは上手く行きました。
結論から言うと、assocで文字列の比較による照合が上手く行っていなかったようです。assocは、指定したキーと連想リストの中にあるペアの先の要素(キーに当たる部分)をそれぞれ調べて、最初に一致したペアを返します。実装例では文字列がキーになっていますが、文字列では一致とみなされません。シンボルの場合は、シンボルテーブル上で一意となり、検索時に一致とみなされます。
これを文字列のまま行うには、"intern"関数を使ってシンボルテーブルに登録すれば、シンボルの時と同じ動作にできます。
(defvar *dictionary* nil) ;; 辞書のインタフェース (defun dictionary-add-entry (key value) (push (cons (intern key) value) *dictionary*)) (defun dictionary-lookup (key) (cdr (assoc (intern key) *dictionary*))) ;; 辞書データ登録 (dictionary-add-entry "carrot" "にんじん") (dictionary-add-entry "radish" "だいこん") (dictionary-add-entry "burdock" "ごぼう") (print *dictionary*) ;; 辞書を参照 (print (dictionary-lookup "radish"))
今度はinteractionモードで使ってみます。新しく定義を追加しています。
$ clisp -i dictionary.lisp ;;;;(中略) ;; Loading file dictionary.lisp ... ((|burdock| . "ごぼう") (|radish| . "だいこん") (|carrot| . "にんじん")) "だいこん" ;; Loaded file dictionary.lisp [1]> (dictionary-lookup "carrot") "にんじん" [2]> (dictionary-lookup "onion") NIL [3]> (dictionary-add-entry "onion" "たまねぎ") ((|onion| . "たまねぎ") (|burdock| . "ごぼう") (|radish| . "だいこん") (|carrot| . "にんじん")) [4]> (dictionary-lookup "onion") "たまねぎ" [5]>
これでひとまず完成です。
EmacsLispでも全く同じコードが使用できます。EmacsLispの場合は、最初のバージョンでもちゃんと動作します。
(追記)assocに比較関数を指定する方法についてコメントいただきましたので、書き換えてみます。ついでに、上書き機能も頑張ってみます。
(defvar *dictionary* nil) ;; 辞書のインタフェース (defun dictionary-get-entry (key) (assoc key *dictionary* :test 'equal)) (defun dictionary-add-entry (key value) (let ((entry)) (setf entry (dictionary-get-entry key)) (if (null entry) (push (cons key value) *dictionary*) (rplacd entry value)))) (defun dictionary-lookup (key) (cdr (dictionary-get-entry key))) ;; 辞書データ登録 (dictionary-add-entry "carrot" "にんじん") (dictionary-add-entry "radish" "だいこん") (dictionary-add-entry "burdock" "ごぼう") (print *dictionary*) ;; 辞書を参照 (print (dictionary-lookup "radish"))
$ clisp -i dictionary.lisp (中略) ;; Loading file dictionary.lisp ... (("burdock" . "ごぼう") ("radish" . "だいこん") ("carrot" . "にんじん")) "だいこん" ;; Loaded file dictionary.lisp [1]> (dictionary-add-entry "carrot" "人参") "人参" [2]> *dictionary* (("burdock" . "ごぼう") ("radish" . "だいこん") ("carrot" . "人参")) [3]>
Scheme + alist
Schemeの場合も、internを気にせずにassocが使用できるようです。
こちらは別の問題になりますが、alistに要素を追加する"acons"は破壊的に作用しないので、結果を"set!"で破壊的に設定しなければなりません。それ以外は似たようなコードになりました。
(define *dictionary* ()) ;; 辞書のインタフェース (define (dictionary-add-entry key value) (set! *dictionary* (acons key value *dictionary*))) (define (dictionary-lookup key) (cdr (assoc key *dictionary*))) ;; 辞書データ登録 (dictionary-add-entry "carrot" "にんじん") (dictionary-add-entry "radish" "だいこん") (dictionary-add-entry "burdock" "ごぼう") (print *dictionary*) ;; 辞書を参照 (print (dictionary-lookup "radish"))
$ gosh dictionary.scm ((burdock . ごぼう) (radish . だいこん) (carrot . にんじん)) だいこん $
CommonLisp + hash-table
今度は、連想リストの代わりにハッシュテーブルを使用します。但しインタフェースは変えずに実装します。
こちらはEmacsLisp非対応です。
(defvar *dictionary* (make-hash-table)) ;; 辞書のインタフェース (defun dictionary-add-entry (key value) (setf (gethash (intern key) *dictionary*) value)) (defun dictionary-lookup (key) (gethash (intern key) *dictionary*)) ;; 辞書データ登録 (dictionary-add-entry "carrot" "にんじん") (dictionary-add-entry "radish" "だいこん") (dictionary-add-entry "burdock" "ごぼう") (print *dictionary*) ;; 辞書を参照 (print (dictionary-lookup "radish"))
こちらもinternを使用しています。ややこしいのは、"gethash"に対して"sethash"とは"puthash"がありそうなのに無くて、登録する時も"gethash"を使う点です。"gethash"が返した値(シンボル?)に対して値を設定します。
$ clisp hashtable.lisp #S(HASH-TABLE :TEST FASTHASH-EQL (|burdock| . "ごぼう") (|radish| . "だいこん") (|carrot| . "にんじん")) "だいこん" $
(追記)hash-tableに比較関数を指定する方法についてコメントいただきましたので、書き換えてみます。
(defvar *dictionary* (make-hash-table :test 'equal)) ;; 辞書のインタフェース (defun dictionary-add-entry (key value) (setf (gethash key *dictionary*) value)) (defun dictionary-lookup (key) (gethash key *dictionary*)) ;; 辞書データ登録 (dictionary-add-entry "carrot" "にんじん") (dictionary-add-entry "radish" "だいこん") (dictionary-add-entry "burdock" "ごぼう") (print *dictionary*) ;; 辞書を参照 (print (dictionary-lookup "radish"))
$ clisp hashtable.lisp #S(HASH-TABLE :TEST FASTHASH-EQUAL ("burdock" . "ごぼう") ("radish" . "だいこん") ("carrot" . "にんじん")) "だいこん" $
scheme + hash-table
こちらの方がハッシュテーブルに対する操作は直感的です。注意が必要なのは、テーブルタイプの指定です。このハッシュテーブルのデフォルトの比較関数*1では、文字列がキーの場合に想定した動きになりません。文字列をキーにする場合は、キーの比較関数に"string=?"述語を使うように設定します。
(define *dictionary* (make-hash-table 'string=?)) ;; 辞書のインタフェース (define (dictionary-add-entry key value) (hash-table-put! *dictionary* key value)) (define (dictionary-lookup key) (hash-table-get *dictionary* key)) ;; 辞書データ登録 (dictionary-add-entry "carrot" "にんじん") (dictionary-add-entry "radish" "だいこん") (dictionary-add-entry "burdock" "ごぼう") (print *dictionary*) ;; 辞書を参照 (print (dictionary-lookup "radish"))
$ gosh hashtable.scm #<hash-table string=? 0x8f91528> だいこん $
まとめ
今回扱ったコードは勉強不足であやふやな点も多々あり、今後も改善・調査の余地ありですね。特に、連想リスト版での同じキーが追加されたときの挙動は、「上書き」になるようにすべきでしょう。
でも、すべてのバージョンで「データ登録」以降のコードを変えずに実装できたのは、小さな成果だったかなと思います。