URL

試した環境

Ubuntu Server 14.04 LTS
Erlang/OTP 18
Elixir 1.0.4

Keyword lists

多くの関数型言語では、廉造データ構造を2要素のタプルをリストにしたものとして表現することが一般的。Elixirでは、最初の要素がアトム(つまりキー)、になっているタプルのリストがある場合に、それをキーワードリストと呼ぶ。

iex> list = [{:a, 1}, {:b, 2}]
[a: 1, b: 2]
iex> [a: 1, b: 2]          
[a: 1, b: 2]
iex> list == [a: 1, b: 2]
true
iex> list[:a]
1
iex> list[:b] 
2

キーワードリストの形式の場合、特別な構文を用意している。
内部ではタプルのリストとして扱っている。
これらは単なるリストなので、キーワードリストはリストで行える操作を同じように適用でき、性能も特徴も同じ。

例えば、++を使ってキーワードリストへ新しい値を追加することができる。

iex> list ++ [e: 3]
[a: 1, b: 2, e: 3]
iex> [a: 0] ++ list
[a: 0, a: 1, b: 2]

キーワードリストから値を取得するときは、前にある方が取得されることに注意すること。

iex> new_list = [a: 0] ++ list
[a: 0, a: 1, b: 2]
iex> new_list[:a]
0

キーワードリストは、次の２つの特別な特徴が在るため重要。

キーの順序を開発者が指定した通りに保持する
キーを複数回与えることができる

例えば、Echoライブラリでは、データベースクエリをDSLで書けるように、上記の2つの特徴を使っている。

query = from w in Weather,
      where: w.prcp > 0,
      where: w.temp < 20,
     select: w

このような特徴が、キーワードリストを関数へオプションを渡すためのデフォルトで使われる仕組みにする。

これまでにif/2マクロを紹介しましたが、次のような構文をサポートしていました。

iex> if false, do: :this, else: :that
:that

実は、doとelseの組はキーワードリスト。事実、この呼び出しは次の構文と等価。

iex> if(false, [do: :this, else: :that])
:that

一般的に、キーワードリストは、関数の引数の最後にあり、角括弧は付けなくても良い。

キーワードリストを操作するために、Keywordモジュールがある。
キーワードは単なるリストであるため、リストと同じ線形の性能特性を持っている。より長いリストは、キーを見つけるのがより長くなり、要素の数えるのがより長くなる。そのため、キーワードリストは主にオプションとして使われる。もし多くの要素を保持しなければならないかったり、１つのキーが多くても１つの要素しか持たないことを保証したい場合は、mapを使うべき。

キーワードリストにもパターンマッチさせることができる。

iex> [a: a] = [a: 1]
[a: 1]
iex> a
1
iex> [a: a] = [a: 1, b: 2]
** (MatchError) no match of right hand side value: [a: 1, b: 2] 
iex> [b: b, a: a] = [a: 1, b: 2]
** (MatchError) no match of right hand side value: [a: 1, b: 2]

しかし、リストでのパターンマッチは、マッチさせるためにアイテムの数や順番が必要なため、実際に上記のようなマッチをするのは稀と考えられる。

Maps

キーバリューストアを必要とするときに、Elixirでは"go to"データ構造であるマップが利用できる。マップは%{}構文を使うとつくることができる。

iex> map = %{:a => 1, 2 => :b}
%{2 => :b, :a => 1}
iex> map[:a]
1
iex> map[2] 
:b
iex> map[1]
nil
iex> map[:b]
nil

キーワードリストに比べて、既に2つ違うことがある。

マップはキーをどんな値にもできる
マップのキーは順番通りにならない

キーワードリストとは違い、マップに同じキーを渡した場合、最後のものが勝つ。

iex> map = %{1 => 1, 1 => 2}
%{1 => 2}
iex> map[1] 
2

マップのキーが全てアトムの場合は、次のような便利なキーワード構文を使うことができる。=>を省略できる。

iex> map = %{a: 1, b: 2}
%{a: 1, b: 2}
iex> map[:a]
1
iex> map[:b]
2

キーワードリストとは対照的に、マップはパターンマッチがとても有効。

iex> %{} = %{:a => 1, 2 => :b}
%{2 => :b, :a => 1}
iex> %{:a => a} = %{:a => 1, 2 => :b}
%{2 => :b, :a => 1}
iex> a
1
iex> %{:c => c} = %{:a => 1, 2 => :b}
** (MatchError) no match of right hand side value: %{2 => :b, :a => 1}

上記のように、与えられたマップに存在するキーがある部分だけにマッチする。
そのため、空のマップには全てのマップがマッチする。

マップの面白い特徴として、更新やアトムのキーにアクセスための特定の構文が提供されている。

iex> map = %{:a => 1, 2 => :b}
%{2 => :b, :a => 1}
iex> map.a                    
1
iex> map.2                    
** (SyntaxError) iex:52: syntax error before: 2
iex> map2 = %{map | :a => 2}
%{2 => :b, :a => 2}
iex> map2.a
2
iex> map.a
1
iex> %{map | :c => 3}
** (KeyError) key :c not found in: %{2 => :b, :a => 1}
    (stdlib) :maps.update(:c, 3, %{2 => :b, :a => 1})
    (stdlib) erl_eval.erl:255: anonymous fn/2 in :erl_eval.expr/5
    (stdlib) lists.erl:1262: :lists.foldl/3

アクセスと更新のどちらの場合でも、既にあるキーを必要とする。
最後の行は、マップに:cが無いので、失敗している。
これは、マップに既にキーがあることが期待できる場合は有用。

マップを操作するには、Mapモジュールを使う。Keywordモジュールによく似ている。これはどちらもDictという振る舞いを実装しているため。

マップは最近のEEP43でErlang VMに導入された。Erlang 17では、EEP43の一部の"small maps"だけサポートされている。これは最大でも数十キー程度のマップを格納した場合のみ性能特性が良好であることを意味する。このギャップを埋めるため、Elixirでは、数十万のキーでも性能が良いハッシュアルゴリズムを使うHashDictモジュールを提供している。

Dicts

Elixirでは、キワードリストもマップのどちらもディクショナリと呼ばれる。
言い換えると、ディクショナリはインタフェース(Elixrではこれをビヘイビアと呼んでいる)のようなもので、キーワードリストとマップの両方はこのインタフェースの実装のようなもの。

このインタフェースはAPIを提供しているDictモジュールで定義されている。このAPIは実際には基本的な実装にデリゲートしている。

iex> keyword = []
[]
iex> map = %{}
%{}
iex> Dict.put(keyword, :a, 1)
[a: 1]
iex> Dict.put(map, :a, 1)    
%{a: 1}

Dictモジュールは、開発者が特定の特性を持つDictの独自のバリエーションを実装し、既存のElixirコードにフックすることができる。Dictモジュールは他のディクショナリ同士でも動作するような関数を提供している。
例えば、Dict.equal?/2関数は任意の種類の2つの辞書を比較することができる。

Keyword, Map, Dictモジュールのどれを使うべきか。
答えは、場合による。

もしも、引数としてキーワードを期待しているのであれば、明示的にKeywordモジュールを使う。もし、mapを操作するならMapモジュールを使う。しかし、どのディクショナリでも動作するようなAPIの場合はDictモジュールを使う（そして、異なるディクショナリの実装を引数に渡してテストをパスすることも確かめておく）。

連想データ構造の話はおしまい。これで連想データ構造を必要とする問題に取り組むめの適切なツールであるキーワードリスト、マップを持った。