私が最初にコレクションということばを聞くと、切手の収集を思い出す。 それから、パリコレということばがあることも思い出す。パリコレとは パリ・コレクションの略で、 パリで開かれるファッションブランドの新作発表会の総称である。 ついでにいうと、パリ・コレクションは日本でしか通用しないことばだという。
さて、コンピュータの分野でコレクションというと、複数のデータをひとつにまとめる働きをもつデータ構造である。 コレクションは、関数やパラメータによって個別の要素を操作する。
以下、コレクションの例を挙げるにあたって注意点を述べる。
C 言語の構造体やオブジェクト指向言語のクラスも、 複数のデータをひとつにまとめる働きをもつが、その操作の手段がメンバを指定することのみでしか得られないからか、 コレクションにはふつう含めないようだ。
Java などでは配列をコレクションには含まないが、ここでは配列をコレクションに含む。
古典的な手続き型言語で、コレクションを実現するほとんど唯一の構造である。インデックスで個別の要素を操作する。 順序構造をもっていて、要素の数を n とするとき、 要素は 0 から始まり n - 1 で終わるタイプの言語がほとんどだが、Fortran や Julia のように 1 から始まり n で終わるタイプの言語もある。
関数型言語におけるリストは、他のコレクションにすべてに優越する基本構造である。順序構造をもっている。 古典的なリストでは、先頭要素の追加・削除がリストの要素の数のいかんにかかわらず定数時間で可能である。 先頭要素の追加・削除が容易であり、スタックという名前で言及されることもある。
Python では、リストに似た構造としてタプル(Tuple)がある。タプルがリストが異なる点として、 破壊的な操作ができないことがある。
集合(Set)は順序構造をもたないデータ構造である。また、要素の重複は許されない。
マップ(Map)とは、キーと値を結び付けて管理するデータ構造である。キーの重複は許されない(値の重複は許される)。 このマップに相当するデータ構造の名称は、コンピュータ言語によってまちまちである。
先頭要素への追加と末端要素の削除が定数時間で可能である構造をいう。これに加え、 先頭要素の削除と末端要素の追加も定数時間で可能である構造をデク(Deque)という。
コレクションに対する操作で基本的なものはコレクションの列挙である。では、 列挙に次いで重要なものは何かということになると、次の三種類だと私は思う。
関数型言語に限らず、最近の言語ではこれらを実装しているものが多い。以下、簡単に説明する。
写像というのは、コレクションに対して特定の関数が与えられて、結果がその関数の値のコレクションとなることをいう。
従って得られた結果はもとのコレクションの構造をサイズを含めて保つ。名称に関していえば、
Map (higher-order function)(en.wikipedia.org)
によれば、写像を表す名称も map
となっている言語が多い。これは、写像のことを英語で map
というからだろう(連想配列を表す map とは混同しないこと)。他には、Common
Lisp では mapcar が、C++ では transform が、C# では select が使われる。
折り畳みとは、コレクションの要素に対して指定された順序で再帰的に指定された演算を繰り返すことをいう。 得られた結果の構造は、コレクションの要素の構造と演算によって変わりうる。
この折り畳みを表す関数の名称も言語によってまちまちだ。
Fold (higher-order function)(en.wikipedia.org)
を見てみると、全体的には reduce が多く、また関数型言語では fold や foldl
が多い。 C# では Aggregate() 、C++ では accumulate()、Ruby や Smalltalk は
inject() である。なお、 Ruby は reduce でもいい。また、演算にあたって、
初期値を与える関数と与えない関数で名称を区別している例もある。
コレクションの濾過またはフィルター ( filter ) とは、コレクションの要素に対して外部から条件を与え、その条件を満たす要素だけ集めて新たなコレクションとすることである。
Filter (higher-order function)(en.wikipedia.org)
かなりの言語はこの働きに対して filter の語を用いているが、 Common LISP
では remove-if や remove-if-not をこれに当てている。C++ では
remove_copy_if や copy_if などがある。また、言語によっては
find_all(findAll) や select を使う場合もある。
上記三種類の操作はコレクションが対象であるように説明したが、実はコレクションを含む広い概念に対してこれらの操作が適用できる。 たとえば、C# では IEnumerable という概念をもつデータに対して操作が可能である。 IEnumerable はインターフェイス(Interface)の Enumerable(列挙可能)という意味と考えられる。また C++ ではイテレータ(反復子)をもつデータに対して同じように操作が可能だ。