リスト内包表記

リスト内包表記とは、一部のプログラミング言語で使用可能な構文構造であり、既存のリストから新たなリストを作成するために用いられるものである。 これは、 map関数やfilter関数などとは異なり、数学における集合内包表記  に準拠したものである。

1. 概要
-----

次の集合内包表記の例を考える。

あるいは

この表記は、「は、が自然数の集合  の元であり、かつの二乗がより大きいようなすべての『の2倍』なる数」を意味する。

最小の自然数x=1は、条件x2>3を満たさないため、2・1はSに含まれない。次の自然数2は、条件を満たす。他のすべての自然数も同様である。 したがって、xは 2, 3, 4, 5... で構成される。集合Sは「xの2倍」なるすべての数値で構成されるため、S = {4, 6, 8, 10...} で与えられる。言い換えれば、Sは2より大きいすべての偶数の集合である。

注釈を加えると以下のようになる。

は入力された集合の元を表す変数である。
は入力された集合である自然数の集合を表す。
は入力された集合の元に対するフィルターとして機能する述語式である。
は入力された集合の元から新しい集合の元を生成する出力式である。
中括弧 は結果が集合であることを表す。
縦棒 は「SUCH THAT」と読む。 縦棒とコロン 「:」は同じ意味で使用される。
カンマは述語を区切り、「AND」と読まれる。リスト内包表記は、入力されたリストまたはイテレータからの新たなリストの生成を表すためにこれと同じ構文構造を用いるものである。

入力リストのメンバを表す変数。
入力リスト。
述語式。
述語を満たす入力イテラブルのメンバから出力リストのメンバを生成する出力式。出力リストのメンバーの生成順序は、入力内のアイテムの順序に基づく。

Haskellのリスト内包表記では、このような集合内包表記は同様に次のように記述される。 s = [ 2*x | x <- [0..], x^2 > 3 ] ここで、リスト[0..]は 、 x^2>3は述語式を表し、 2*xは出力式を表す。

リスト内包表記はリストで定義された順序で結果を返す。また先のHaskellの例における無限長のリストのような定義を受け入れるために、リスト内包表記はリスト全体を変換するのではなく、リストのメンバを順に生成するようなジェネレータを返却する。

2. 歴史
-----

プログラミング言語SETLには、リスト内包表記に似た集合形成構文が存在する。例えば以下のコードは2からNまでのすべての素数を出力する。 print; 数式処理システムAXIOMにも、 ストリームを処理するための同様の構文が存在するが、このような構文に対して「内包表記」という用語が用いられたのは、1977年にRod BurstallとJohn Darlingtonが関数型プログラミング言語NPLについて行ったものが最初である。

少なくともバージョンSmalltalk-80以降のSmalltalkでは、リスト内包を構成するブロックコンテキストメッセージが使用されている。

NPLに対するBurstallとDarlingtonの貢献は、1980年代に多くの関数型プログラミング言語に影響を与えたが、以後リスト内包表記が関数型言語のスタンダードとなるわけではなかった。例外であったのは、1985年にリリースされ流行した、純粋遅延評価関数型プログラミング言語Mirandaである。その後開発された純粋遅延評価関数型言語Haskellには、リスト内包表記を含む、Mirandaの多くの機能が取り入れられた。

またリスト内包表記はデータベースのクエリ表記法としても提案され、Kleisliデータベースクエリ言語に実装された。

3. 類似構文
-------

3.1. モナド内包表記
------------

Haskellにはモナド内包表記という記法が存在する。これは関数型プログラミングにおけるリスト内包表記のモナドへの一般化である。

3.2. 集合内包表記
-----------

プログラミング言語Pythonのバージョン3.xおよび2.7では、 集合内包表記の構文が導入されている。これはリスト内包表記と同様の形式をとり、リストの代わりにPythonのsetを生成する。 >>> s = {v for v in 'ABCDABCD' if v not in 'CB'} >>> print {'A', 'D'} >>> type >>> Racketの集合内包表記は、リストではなくRacketのsetを生成する。 )) v))

3.3. 辞書型内包表記
------------

プログラミング言語Pythonのバージョン3.xと2.7では、リスト内包表記に似た形式の辞書型内包表記の新しい構文が導入された。これはリストの代わりにPythonの[1]が生成する。 >>> s = {key: val for key, val in enumerate if val not in 'CB'} >>> s {0: 'A', 3: 'D'} >>> Racketのハッシュテーブル内包表記は、Racketのハッシュテーブルを生成する。  ]

unless )))<WtXmlEndTag />

3.4. 並列リスト内包表記
--------------

Glasgow Haskell Compilerには、リスト内包表記の構文において複数の独立した修飾子  の分割を許可する、並列リスト内包表記と呼ばれる拡張構文が存在する。カンマで区切られた変数は依存関係にあるが、パイプ文字で区切られた修飾子は並列に評価される。 -- 通常のリスト内包表記 a = [ | x <- [1..5], y <- [3..5]] -- [,,,, ...

-- zipによるリスト内包表記 b = [ |  <- zip [1..5] [3..5]] -- [,,]

-- 並列リスト内包表記 c = [ | x <- [1..5] | y <- [3..5]] -- [,,]<WtXmlEndTag /> Racketの標準ライブラリには、「for」と「for*」いう2つのキーワードで区別される、並列バージョンと多重ループバージョンの2つの内包表記が含まれている。例えば、ベクトル内包表記「for/vector」および「for*/vector」は、入力シーケンスに対してそれぞれ並列および多重ループによってベクトルを作成する。以下は、上のHaskellのリスト内包表記の例をRacketコードに書き下したものである。 > ] [y ]) ) '              ) > ] [y ]) ) '  ) また、Pythonでは次のように書ける。

通常のリスト内包表記>>> a = [ for x in range for y in range] [, , , , , ...

並列  内包表記>>> b = [x for x in zip, range)] [, , ]<WtXmlEndTag />

3.5. XQueryとXPath
-----------------

これらの言語は基本的にデータベースアクセス言語である。リスト全体を取得して操作することは計算時間的に不可能であるため、内包表記の概念がより重要となる。

XPathでは、式 /library/book//paragraph[@style='first-in-chapter'] は概念的には一連の「ステップ」として評価される。各ステップはリストを生成し、次のステップは前のステップの出力の各要素にフィルターとなる関数を適用する。

XQueryではXPathの機能はすべて使うことができるが、それに加えて、より強力な内包表記構造であるFLWOR構文も同時に使用される。 for $b in //book where $b[@pages < 400] order by $b//title return{$b//title}{[1]} ここでは//bookというXPathが評価され、新たなシーケンスが作成される。where句は「フィルタ」として機能し、orderは出力のソート順序を指定し、その後に続くshortBook}} XMLスニペットは、他の関数型言語におけるmapのようなアプローチを用いてシーケンスの各要素のXMLを構築する匿名関数として機能する。

したがって、他の関数型言語では、上記のFLWORによる記述を次のように実装できる。 map, newXML) filter, xpath ) )

3.6. LINQ
---------

C# 3.0には、LINQと呼ばれる関連機能のセットが存在し、オブジェクト列挙子を操作するためのクエリ演算子が定義されている。 var s = Enumerable.Range.Where.Select; また、SQLに似た別の内包表記構文も存在する。 var s = from x in Enumerable.Range where x*x > 3 select x*2; LINQは、典型的なリスト内包表記の実装よりも優れた機能を提供する。内包表記のルートオブジェクトがIQueryableインターフェイスを実装する場合、単に内包表記の中のチェーンメソッドを実行するだけでなく、命令のシーケンス全体を抽象構文木オブジェクトに変換し、IQueryableオブジェクトに渡して解釈・実行する。

これにより、とりわけIQueryableは

非互換または非効率的な内包表記を書き直すことができる。
抽象構文木を実行用の別のクエリ言語に翻訳することができる。

3.7. C++
--------

C++にはリスト内包表記を直接サポートする言語機能は存在しないが、 演算子オーバーロードを使用して、「埋め込み」クエリDSLの構文を提供するということがしばしば行われる。また、erase-removeイディオムを使用してコンテナ内の要素を選択し、STLのfor_eachアルゴリズムを使用して要素を変換することでもリスト内包表記を構築できる。

include
include
include using namespace std;

template C comprehend { // 出力を初期化 C d = forward;

// 要素をフィルタ d.erase, end, predicate), end);

// 変換を適用 for_each, end, transformation);

return d; }

int main { list range; // rangeはサイズ10のリストで、初期値はゼロ iota, end, 1); // rangeに1,2,...,10を代入

list result = comprehend{return x*x <= 3;}, []{x *= 2;}); // resultに4,6,...,20が代入される }<WtXmlEndTag /> また、集合内包表記と似たリスト内包表記の構文・記法をC++に提供するための試みがいくつか存在する。

Boostのrangeライブラリには、アダプタ記法が存在し、フィルタや変換などを任意のrangeに適用することができる。このライブラリーを使用すると、上のHaskellのコード例は次のように書ける。 counting_range | filtered | transformed)<WtXmlEndTag />

ある実装では、マクロと、<<演算子のオーバーロードを使用する。これは条件文の中の任意の式を有効と評価するため、条件文中では任意の変数名を選択できる。ただし、スレッドセーフではない。以下のように使用される。 list N; list S;

for  N.push_back;

S << list_comprehension<WtXmlEndTag />

ある実装では、クラスと演算子のオーバーロードを使用して、head/tailスライスの機能と、関数を用いてリストをフィルタするための | 演算子を提供する。以下のように用いられる。 bool even { return x % 2 == 0; } bool x2 { x *= 2; return true; }

list l, t; int x, y;

for  l.push_back;

 = l | x2;  = t;

t = l < 9; t = t < 7 | even | x2;<WtXmlEndTag />

Language for Embedded Query and Traversalは、演算子のオーバーロードを用いてXPathに似たクエリを実装するC++の埋め込みDSLである。クエリは、XMLからC++へのバインディングを使用してXSDから取得された、型付けされたXMLツリーの上で実行される。文字列としては変換されない。XMLタグの名前までもがクラスとなるので、タイプミスによるバグが発生しにくくなる。LEESA式がデータモデルに存在しない誤ったパスを生成する場合、C++コンパイラはコンパイルに失敗する。
なるXMLについて考えてみる。 Hamlet9.99William ShakespeareEngland... ...<WtXmlEndTag /> LEESAは、XPathの/セパレータに対応する演算子として>>を提供する。 XPathにおいてツリーの中間ノードを「スキップ」する//セパレーターは、LEESAでは戦略的プログラミングと呼ばれる手法を用いて実装される。以下の例では、catalog_、およびbook_、author_、name_は、それぞれ、catalog、およびbook、author、nameクラスのインスタンスである。 // 対応するXPath: "catalog/book/author/name" std::vector author_names = evaluate;

// 対応するXPath: "catalog//name" std::vector author_names = evaluate);

// 対応するXPath: "catalog//author[country=="England"]" std::vector author_names = evaluate >> Select { return a.country=="England"; }) >> name_);<WtXmlEndTag />

4. 関連項目
-------

SELECT文: SQLにおいてFROM句およびWHERE句と組み合わせて用いられる。

5. 脚注・参考文献
----------

The Free On-line Dictionary of Computingの[2]の項、編集: Denis Howe
first1=Phil
first1=Philip
first1=Limsoon

5.1. Haskell
------------

The Haskell 98 Report, chapter [3].
The Glorious Glasgow Haskell Compilation System User's Guide, chapter [4].
The Hugs 98 User's Guide, chapter [5].

5.2. OCaml
----------

[6]
[7]

5.3. Python
-----------

The Python Tutorial, [8].
Python Language Reference, [9].
Python Enhancement Proposal [10].
Python Language Reference, [11].
Python Enhancement Proposal [12].

5.4. Common Lisp
----------------

[13] by Guy Lapalme

5.5. Clojure
------------

[14]

5.6. Axiom
----------

[15]

6. 外部リンク
--------

[16]のSQLライクな集合演算子にはリスト内包表記のワンライナーが含まれている。
[17]
[18]