7 キーワード,マップそしてリスト - Keywords, maps and dicts

ある値(あるいは複数の値)をキーにできるデータ構造,すなわち連想データ構造のことについてはまだ何も話していませんね.他の言語では例えばディクショナリ,ハッシュ,連想配列,マップなどと呼ばれているもののことです.

So far we haven't discussed any associative data structures, i.e. data structures that are able to associate a certain value (or multiple values) to a key. Different languages call these different names like dictionaries, hashes, associative arrays, maps, etc.

Elixirにはキーワードリストとマップという2つの主な連想データ構造があります.これからそれらについて学んでいきましょう!

In Elixir, we have two main associative data structures: keyword lists and maps. It's time to learn more about them!

7.1 キーワードリスト - Keyword lists

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

In many functional programming languages, it is common to use a list of 2-item tuples as the representation of an associative data structure. In Elixir, when we have a list of tuples and the first item of the tuple (i.e. the key) is an atom, we call it a keyword list:

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

上で見たように,エリクサーはこのようなリストを定義するのに特別な構文をサポートしており,裏ではタプルのリストへと変えています.これらは単なるリストなので,キーワードリストはリストへ行う操作がどれも可能で,また性能の特徴も同じです.

As you can see above, Elixir supports a special syntax for defining such lists, and underneath they just map to a list of tuples. Since they are simply lists, all operations available to lists, including their performance characteristics, also apply to keyword lists.

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

For example, we can use ++ to add new values to a keyword list:

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

値を取るときは前にある方が取得されることに注意してください:

Note that values added to the front are the ones fetched on lookup:

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

キーワードリストは2つの特別な特徴があるため重要です:

Keyword lists are important because they have two special characteristics:

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

  • They keep the keys ordered, as specified by the developer.

  • They allow a key to be given more than once.

例えば,Ectoライブラリではデータベースクエリーを洗練されたDSLで書けるようにするために2つの機能両方を使っています:

For example, the Ecto library makes use of both features to provide an elegant DSL for writing database queries:

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

この特徴があるため,キーワードリストは関数へオプションを渡すためのデフォルトのメカニズムとなっています.5章ではif/2マクロについて話しましたね,以下のような構文をサポートしていたのでした:

Those features are what prompted keyword lists to be the default mechanism for passing options to functions in Elixir. In chapter 5, when we discussed the if/2 macro, we mentioned the following syntax is supported:

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

doelseの組はキーワードリストです!事実この呼び出しは次と同じです:

The do: and else: pairs are keyword lists! In fact, the call above is equivalent to:

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

一般的に,キーワードリストは関数の引数の最後にあり,角括弧はつけてもつけなくてもいいです.

In general, when the keyword list is the last argument of a function, the square brackets are optional.

キーワードリストを操作するために,ElixirはKeywordモジュールを提供しています.キーワードリストは単にリストであることを思い出してください,そのためリストと同じ線形の性能特性をもっています.より長いリストは,キーを見つけるのがより長くなり,要素を数えるのがより長くなり,などなど.そのため,キーワードリストは主にオプションとして使われています.もし沢山の要素を保持しなければならなかったり,1つのキーが多くとも1つの値しか持たないことが保証したいなら,かわりにマップを使うべきです.

In order to manipulate keyword lists, Elixir provides the Keyword module. Remember though keyword lists are simply lists, and as such they provide the same linear performance characteristics as lists. The longer the list, the longer it will take to find a key, to count the number of items, and so on. For this reason, keyword lists are used in Elixir mainly as options. If you need to store many items or guarantee one-key associates with at maximum one-value, you should use maps instead.

キーワードリストにもパターンマッチできます:

Note we can also pattern match on keyword lists:

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]

ともあれ,パターンマッチにアイテムの数やマッチの順番を必要とするようなリストへパターンマッチすることはほとんどないでしょう.

However this is rarely done in practice since pattern matching on lists require the number of items and their order to match.

7.2 マップ - Maps

あなたがキーバリューストアが必要をするとき,マップはElixirにおける"go to"データ構造です.マップは%{}を使うと作ることができます:

Whenever you need a key-value store, maps are the "go to" data structure in Elixir. A map is created using the %{} syntax:

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

キーワードリストに比べて,すでに2つ違う点がありますね:

Compared to keyword lists, we can already see two differences:

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

  • Maps allow any value as a key.

  • Maps' keys do not follow any ordering.

もしマップを作るときに同じキーを渡すと,最後の一つが勝ちます:

If you pass duplicate keys when creating a map, the last one wins:

iex> %{1 => 1, 1 => 2}
%{1 => 2}

マップのキーが全てアトムの場合は便利なキーワード構文を使うことができます:

When all the keys in a map are atoms, you can use the keyword syntax for convenience:

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

キーワードリストとは対照的に,マップはパターンマッチングに使いやすいです:

In contrast to keyword lists, maps are very useful with pattern matching:

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

上でみたように,マップは与えられたマップのキーがある部分にだけマッチします.したがって,空のマップは全てのマップにマッチします.

As shown above, a map matches as long as the given keys exist in the given map. Therefore, an empty map matches all maps.

マップの興味深い特質に更新やアトムのキーにアクセスするための特定の構文が提供されているところがあります:

One interesting property about maps is that they provide a particular syntax for updating and accessing atom keys:

iex> map = %{:a => 1, 2 => :b}
%{:a => 1, 2 => :b}
iex> map.a
1
iex> %{map | :a => 2}
%{:a => 2, 2 => :b}
iex> %{map | :c => 3}
** (ArgumentError) argument error

上にあるアクセスと更新のどちらの構文でも既にあるキーを必要とします.例えば最後の行ではマップにcがないので失敗しています.これはマップに既にキーがあることをあなたが期待している場合にすごく便利に使うことができます.

Both access and update syntaxes above require the given keys to exist. For example, the last line failed because there is no :c in the map. This is very useful when you are working with maps where you only expect certain keys to exist.

後の章で,私たちはコンパイル時の保証やエリクサーのポリモーフィズムの基礎となる構造体について学びます.構造体は上で書いたような更新の保証が便利であることがわかっているマップの上に構築されています.

In future chapters, we will also learn about structs, which provide compile-time guarantees and the foundation for polymorphism in Elixir. Structs are built on top of maps where the update guarantees above are proven to be quite useful.

マップを操作するにはMapモジュールを使います,APIはKeywordモジュールに良く似ています.どちらもDictという振舞いを実装しているためです.

Manipulating maps is done via the Map module, it provides a very similar API to the Keyword module. This is because both modules implement the Dict behaviour.

メモ: マップは最近EEP 43でErlang VMに導入されました.Erlang 17はEEPの実装の一部,"small maps"だけのサポートを提供しています.これは最大数ダース程度のキーを持つマップの場合にだけ性能が良いことを意味しています.この溝を埋めるため,Elixirでは数十万のキーでも性能が良いアルゴリズムを利用するHashDictモジュールも提供しています.

Note: Maps were recently introduced into the Erlang VM with EEP 43. Erlang 17 provides a partial implementation of the EEP, where only "small maps" are supported. This means maps have good performance characteristics only when storing at maximum a couple of dozens keys. To fill in this gap, Elixir also provides the HashDict module which uses a hashing algorithm to provide a dictionary that supports hundreds of thousands keys with good performance.

7.3 ディクショナリ - Dicts

エリクサーではキーワードリストとマップのどちらもディクショナリと呼ばれています.言いかえると,ディクショナリはインターフェースのようなもの(Elixirではビヘイビアと呼んでいます)で,キーワードリストもマップのどちらのモジュールもこのインターフェースを実装しています.

In Elixir, both keyword lists and maps are called dictionaries. In other words, a dictionary is like an interface (we call them behaviours in Elixir) and both keyword lists and maps modules implement this interface.

このインターフェースはAPIを提供(実際の実装は移譲)しているDictモジュールで定義されています.

This interface is defined in the the Dict module module which also provides an API that delegates to the underlying implementations:

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つのディクショナリであっても比較できます.

The Dict module allows any developer to implement their own variation of Dict, with specific characteristics, and hook into existing Elixir code. The Dict module also provides functions that are meant to work across dictionaries. For example, Dict.equal?/2 can compare two dictionaries of any kind.

そうすると,KeywordMapDictのどのモジュールを使うべきなのかなあ?と思うでしょう.答えは: 場合によるです.

that said, you may be wondering, which of Keyword, Map or Dict modules should you use in your code? The answer is: it depends.

もしあなたのコードが引数としてキーワードを期待しているなら,明示的にKeywordモジュールを使いましょう.もしあなたがmapを操作するならMapモジュールを使いましょう.しかしながら,どのディクショナリでも動作するようなAPIの場合はDictモジュールを使いましょう(そして異なるディクショナリ実装を引数に渡してテストをパスすることも確かめておきましょう).

If your code is expecting a keyword as an argument, explicitly use the Keyword module. If you want to manipulate a map, use the Map module. However, if your API is meant to work with any dictionary, use the Dict module (and make sure to write tests that pass different dict implementations as arguments).

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

This concludes our introduction to associative data structures in Elixir. You will find out that given keyword lists and maps, you will always have the right tool to tackle problems that require associative data structures in Elixir.