elisp の assoc の動作について


elispのassocの動作がよくわからないので[マニュアル](http://www.gnu.org/software/emacs/manual/html_node/elisp/Association-
Lists.html)を読んだんですがよくわからず、

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

[code]

    (assoc "a" '(("a" "b") ("c" "d")))
    ("a" "b")
    (assoc "c" '(("a" "b") ("c" "d")))
    ("c" "d")
    
[/code]

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




まずそもそも: 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 によって構成されます。

[code]

    (a b c)   ===   (a . (b . (c . ())))
    
[/code]

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

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

[code]

    ("a" "b") ==== ("a" . ("b" . ()))
    
[/code]

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

* * *

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

[code]

    (assoc "a" '(("a" . ("b" . ())) ("c" . ( "d" . ()))))
    ;; => ("a" "b")
    
    (assoc "c" '(("a" . ("b" . ())) ("c" . ( "d" . ()))))
    ;; => ("c" "d")
    
[/code]

で実行できるはずです。




まずそもそも: 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 によって構成されます。

[code]

    (a b c)   ===   (a . (b . (c . ())))
    
[/code]

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

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

[code]

    ("a" "b") ==== ("a" . ("b" . ()))
    
[/code]

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

* * *

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

[code]

    (assoc "a" '(("a" . ("b" . ())) ("c" . ( "d" . ()))))
    ;; => ("a" "b")
    
    (assoc "c" '(("a" . ("b" . ())) ("c" . ( "d" . ()))))
    ;; => ("c" "d")
    
[/code]

で実行できるはずです。

