elispのassocの動作がよくわからないのでマニュアルを読んだんですがよくわからず、
色々と触ってみたところこのような動作だったので、とりあえずはRubyやPerlの連想配列のような物だと理解していて良いのでしょうか?
(assoc "a" '(("a" "b") ("c" "d")))
("a" "b")
(assoc "c" '(("a" "b") ("c" "d")))
("c" "d")
この理解だと問題になるようなことはありますか?
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")
で実行できるはずです。
Yuki Inoueさんの補足として、実際の使い方でassocをRubyのHashと比較してみます。
各要素は("a" "b")
のような形式より、("a" . "b")
のようなドット対のほう扱いやすいと思います。
;; elisp
(setq lst '(("a" . "b") ("c" . "d")))
# Ruby
h = {"a" => "b", "c" => "d"}
すると、値の参照はassocの値のcdrになります。
;; elisp
(cdr (assoc "a" lst)) ;=> "b"
# Ruby
h["a"] #=> "b"
既存のキーの値を書きかえるのはsetfなど。
;; elisp
(setf (cdr (assoc "a" lst)) "x")
lst ;=> (("a" . "x") ("c" . "d"))
# Ruby
h["a"] = "x"
新しいキーはリストに追加することで。
;; elisp
(setq lst (cons '("e" . "f") lst)) ;=> (("e" . "f") ("a" . "x") ("c" . "d"))
# Ruby
h["e"] = "f"
要素削除はdeleteで。
;; elisp
(delete (assoc "c" lst) lst) ;=> (("e" . "f") ("a" . "x"))
# Ruby
h.delete("c")
ちなみにassocでは、キーには文字列やシンボルだけではなく、リストなども使えます。
(assoc '(a b) '(((a b) c) ((d e) f))) ;=> ((a b) c)
さらにちなみに、RubyなどのHashに相当するものとして、Emacs LispでもHash Tableがあります。
(setq h (make-hash-table :test 'equal))
(puthash "a" "b" h)
(gethash "a" h) ;=> "b"
さらに捕捉ですが、elisp の連想リスト(association list)では、キーが一意(uniq)である必要はありません。
(assoc "a" '(("a" "b") ("c" "d") ("a" 1) ("c" '(1 "z" t))))
=> ("a" "b")
emasaka さんの回答にある通り、Hash Table
が Ruby や Perl の連想配列(ハッシュ)に相当するものかと思います。ただ、elisp の場合はテスト関数を指定できるので、例えば equal
ではなく eq
を指定してしまうと、
(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
などとなってしまいますが…(最初の "a" と次の "a" と3番目の "a" は全て別々の Lisp object
)。まぁ、変数にバインドすれば良いだけのことですが。
(setq key "a")
(puthash key "z" h)
(gethash key h) ; => "z"
# これに関連して、assq
とか assoc*
などの関数も調べてみると良いかも知れません。
Ruby
ところで Ruby の場合、デフォルトではハッシュキーは uniq である必要があります。
irb> h1 = {}
irb> h1["a"] = 1
irb> h1["a"] = 2
irb> h1
=> {"a"=>2}
ですが compare_by_identity
メソッドを実行すると、ハッシュキーはオブジェクトIDで区別されるようになるので、
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
となります。これは elisp でハッシュテーブルのテスト関数に eq
を指定した場合と似ています("a"
は全て別個のインスタンス))。
Hash.assoc()
メソッドの結果は elisp と同じです。
irb> h2.assoc("a")
=> ["a", 1]
Perl
Perl の場合は uniq キーのみです。
use Data::Dumper;
$h{a} = 1;
$h{a} = 2;
$h{b} = 3;
print Dumper(\%h);
=>
$VAR1 = {
'b' => 3,
'a' => 2
};