elisp の assoc の動作について

投稿者: Anonymous

elispのassocの動作がよくわからないのでマニュアルを読んだんですがよくわからず、

色々と触ってみたところこのような動作だったので、とりあえずはRubyやPerlの連想配列のような物だと理解していて良いのでしょうか?

(assoc "a" '(("a" "b") ("c" "d")))
("a" "b")
(assoc "c" '(("a" "b") ("c" "d")))
("c" "d")

この理解だと問題になるようなことはありますか?

解決

まずそもそも: association list は、特殊な形のリストにすぎず、 assoc はそのような特殊な形のリストに対して動作する関数です。


実用上、問題になることはないとおもいます。ただ、 list は、下に示すように、線形なデータ構造ですので、 hash map 的に実装された連想配列が O(1) なのに対して、 O(n) の計算量がかかるはずです。(ruby や perl の連想配列が hash map であるのではないか、と仮定して話をしています)

動作がよくわからない

おそらく、わかっていないのは、 alist (association list) とは何ぞ?ということだと思います。具体的に、 alist は cons cell のリストだとマニュアルには説明されていますが、 cons cell と list の関係がわかっていないのかと思いました。

一般的な lisp では、 list は実際には cons cell によって構成されます。

(a b c)   ===   (a . (b . (c . ())))

どいういうことかというと、 cons cell というより原始的なデータ型があって、それの特殊系がリストとして取り扱われている、という構造になっています。

assoc 関数は、 cons cell の最初の要素が、一致している cons cell を取り出しています。
たとえば、

("a" "b") ==== ("a" . ("b" . ()))

であって、 "a"("b".()) でからなる cons cell です。なので assoc で取り扱えています。


与えられた例を cons cell に書き直してみると、

(assoc "a" '(("a" . ("b" . ())) ("c" . ( "d" . ()))))
;; => ("a" "b")

(assoc "c" '(("a" . ("b" . ())) ("c" . ( "d" . ()))))
;; => ("c" "d")

で実行できるはずです。

回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *