連想リスト・ハッシュテーブル

数学的でアルゴリズム的なものは背伸び感が否めないので、自分で実際に使いそうなもので練習することにします。今回は、辞書を作ります。これは、過去ネタの流用でもあります。
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>
だいこん
$

まとめ

今回扱ったコードは勉強不足であやふやな点も多々あり、今後も改善・調査の余地ありですね。~~特に、連想リスト版での同じキーが追加されたときの挙動は、「上書き」になるようにすべきでしょう。~~
でも、すべてのバージョンで「データ登録」以降のコードを変えずに実装できたのは、小さな成果だったかなと思います。

*1:詳しくは、schemeの「等価性」についての仕様を参照してください。

argius note

プログラミング関連

連想リスト・ハッシュテーブル

CommonLisp + alist

Scheme + alist

CommonLisp + hash-table

scheme + hash-table

まとめ