3

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

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

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

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

3 件の回答 3

3

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

で実行できるはずです。

1
  • 詳しい解説ありがとうございます。listcons cell の特殊な形態でassoclistではなくcons cellに使えるもっと汎用性の高い関数なのでドキュメントにはそう書かれているということですね。
    – ironsand
    Commented 2015年11月10日 16:39
2

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"
1
  • ありがとうございます。なるほどドット対の方がすっきりと書けそうですね。
    – ironsand
    Commented 2015年11月10日 18:34
1

さらに捕捉ですが、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
        };
1
  • 1
    解説ありがとうございます。正直assocの動作を初めて確認した自分には情報過多でイッパイイッパイなのですが、hashを使う時の比較関数にequalを使うとか、キーが重複しても初めの要素しかとってこないなどは知らないと引っかかりそうなので忘れないようにします。
    – ironsand
    Commented 2015年11月10日 18:38

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。