18634


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]

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


CC BY-SA 3.0
2015-11-10T15:23:11.170
18631
2015-11-10T18:09:07.317
3271
question
elisp
elisp の assoc の動作について


まずそもそも: 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]

で実行できるはずです。


CC BY-SA 3.0
2015-11-10T16:11:32.247
18634
2015-11-10T16:26:11.700
2015-11-10T16:26:11.700
754
754
18631
answer


Yuki Inoueさんの補足として、実際の使い方でassocをRubyのHashと比較してみます。

各要素は`("a" "b")`のような形式より、`("a" . "b")`のようなドット対のほう扱いやすいと思います。

[code]

    ;; elisp
    (setq lst '(("a" . "b") ("c" . "d")))
    
    # Ruby
    h = {"a" => "b", "c" => "d"}
    
[/code]

すると、値の参照はassocの値のcdrになります。

[code]

    ;; elisp
    (cdr (assoc "a" lst))   ;=> "b"
    
    # Ruby
    h["a"]      #=> "b"
    
[/code]

既存のキーの値を書きかえるのはsetfなど。

[code]

    ;; elisp
    (setf (cdr (assoc "a" lst)) "x")
    lst     ;=> (("a" . "x") ("c" . "d"))
    
    # Ruby
    h["a"] = "x"
    
[/code]

新しいキーはリストに追加することで。

[code]

    ;; elisp
    (setq lst (cons '("e" . "f") lst))  ;=> (("e" . "f") ("a" . "x") ("c" . "d"))
    
    # Ruby
    h["e"] = "f"
    
[/code]

要素削除はdeleteで。

[code]

    ;; elisp
    (delete (assoc "c" lst) lst)    ;=> (("e" . "f") ("a" . "x"))
    
    # Ruby
    h.delete("c")
    
[/code]

ちなみにassocでは、キーには文字列やシンボルだけではなく、リストなども使えます。

[code]

    (assoc '(a b) '(((a b) c) ((d e) f)))   ;=> ((a b) c)
    
[/code]

さらにちなみに、RubyなどのHashに相当するものとして、Emacs LispでもHash Tableがあります。

[code]

    (setq h (make-hash-table :test 'equal))
    (puthash "a" "b" h)
    (gethash "a" h)     ;=> "b"
    
[/code]


CC BY-SA 3.0
2015-11-10T17:01:24.307
18637
2015-11-10T17:01:24.307
4010
18631
answer


さらに捕捉ですが、elisp の連想リスト(association list)では、キーが一意(uniq)である必要はありません。

[code]

    (assoc "a" '(("a" "b") ("c" "d") ("a" 1) ("c" '(1 "z" t))))
    => ("a" "b")
    
[/code]

emasaka さんの回答にある通り、`Hash Table` が Ruby や Perl
の連想配列(ハッシュ)に相当するものかと思います。ただ、elisp の場合はテスト関数を指定できるので、例えば `equal` ではなく `eq`
を指定してしまうと、

[code]

    (setq h (make-hash-table :test 'eq))
    (puthash 1 '(a b) h)
    (puthash 1 '(x y) h)
    (gethash 1 h)     ; => (x y)
    (puthash "a" "b" h)
    (puthash "a" "c" h)
    (gethash "a" h)   ; => nil
    ;;
    (eq 1 1)     ; => t
    (eq "a" "a") ; => nil
    
[/code]

などとなってしまいますが…(最初の "a" と次の "a" と3番目の "a" は全て別々の `Lisp
object`)。まぁ、変数にバインドすれば良いだけのことですが。

[code]

    (setq key "a")
    (puthash key "z" h)
    (gethash key h)   ; => "z"
    
[/code]

# これに関連して、`assq` とか `assoc*` などの関数も調べてみると良いかも知れません。

**Ruby**

ところで Ruby の場合、デフォルトではハッシュキーは uniq である必要があります。

[code]

    irb> h1 = {}
    irb> h1["a"] = 1
    irb> h1["a"] = 2
    irb> h1
    => {"a"=>2}
    
[/code]

ですが `compare_by_identity` メソッドを実行すると、ハッシュキーはオブジェクトIDで区別されるようになるので、

[code]

    irb> h2 = {}
    irb> h2.compare_by_identity
    irb> h2["a"] = 1
    irb> h2["a"] = 2
    irb> h2
    => {"a"=>1, "a"=>2}
    irb> h2["a"]
    => nil
    
[/code]

となります。これは elisp でハッシュテーブルのテスト関数に `eq` を指定した場合と似ています(`"a"` は全て別個のインスタンス))。

`Hash.assoc()` メソッドの結果は elisp と同じです。

[code]

    irb> h2.assoc("a")
    => ["a", 1]
    
[/code]

**Perl**

Perl の場合は uniq キーのみです。

[code]

    use Data::Dumper;
    $h{a} = 1;
    $h{a} = 2;
    $h{b} = 3;
    print Dumper(\%h);
    =>
    $VAR1 = {
              'b' => 3,
              'a' => 2
            };
    
[/code]


CC BY-SA 3.0
2015-11-10T17:51:52.103
18638
2015-11-10T18:09:07.317
2015-11-10T18:09:07.317
18631
answer