リスト内包表記

リスト内包表記とは、一部のプログラミング言語で使用可能な構文構造であり、既存のリストから新たなリストを作成するために用いられるものである。 これは、 map関数やfilter関数などとは異なり、数学における集合内包表記 (en:) に準拠したものである。 
概要.
次の集合内包表記の例を考える。 
あるいは 
この表記は、「formula_3は、formula_4が自然数の集合 (formula_5) の元であり、かつformula_4の二乗がformula_7より大きいようなすべての『formula_4の2倍』なる数」を意味する。 
最小の自然数x=1は、条件x2>3を満たさない（12>3は偽）ため、2・1はSに含まれない。次の自然数2は、条件を満たす（22>3）。他のすべての自然数も同様である。 したがって、xは 2, 3, 4, 5... で構成される。集合Sは「xの2倍」なるすべての数値で構成されるため、S = {4, 6, 8, 10...} で与えられる。言い換えれば、Sは2より大きいすべての偶数の集合である。 
注釈を加えると以下のようになる。 
リスト内包表記は、入力されたリストまたはイテレータからの新たなリストの生成を表すためにこれと同じ構文構造を用いるものである。 
出力リストのメンバーの生成順序は、入力内のアイテムの順序に基づく。 
Haskellのリスト内包表記では、このような集合内包表記は同様に次のように記述される。 
s = [ 2*x | x <- [0..], x^2 > 3 ] 
 ここで、リストcodice_1はformula_5 、 codice_2は述語式を表し、 codice_3は出力式を表す。 
リスト内包表記は（集合のそれとは異なり）リストで定義された順序で結果を返す。また先のHaskellの例における無限長のリストのような定義を受け入れるために、リスト内包表記はリスト全体を変換するのではなく、リストのメンバを順に生成するようなジェネレータを返却する。 
歴史.
プログラミング言語SETL（1969）には、リスト内包表記に似た集合形成構文が存在する。例えば以下のコードは2からNまでのすべての素数を出力する。 
print([n in [2..N] | forall m in {2..n - 1} | n mod m > 0]); 
 数式処理システムAXIOM（1973）にも、 ストリームを処理するための同様の構文が存在するが、このような構文に対して「内包表記（comprehension）」という用語が用いられたのは、1977年にRod BurstallとJohn Darlingtonが関数型プログラミング言語NPLについて行ったものが最初である。 
少なくともバージョンSmalltalk-80以降のSmalltalkでは、リスト内包を構成するブロックコンテキストメッセージが使用されている。 
NPLに対するBurstallとDarlingtonの貢献は、1980年代に多くの関数型プログラミング言語に影響を与えたが、以後リスト内包表記が関数型言語のスタンダードとなるわけではなかった。例外であったのは、1985年にリリースされ流行した、純粋遅延評価関数型プログラミング言語Mirandaである。その後開発された純粋遅延評価関数型言語Haskellには、リスト内包表記を含む、Mirandaの多くの機能が取り入れられた。 
またリスト内包表記はデータベースのクエリ表記法としても提案され、Kleisliデータベースクエリ言語に実装された。 
類似構文.
モナド内包表記.
Haskellにはという記法が存在する。これは関数型プログラミングにおけるリスト内包表記のモナドへの一般化である。 
集合内包表記.
プログラミング言語Pythonのバージョン3.xおよび2.7では、 集合内包表記の構文が導入されている。これはリスト内包表記と同様の形式をとり、リストの代わりにPythonのsetを生成する。 
»> print(s)
»> type(s)
<class 'set'>
 Racketの集合内包表記は、リストではなくRacketのsetを生成する。 
 v))
辞書型内包表記.
プログラミング言語Pythonのバージョン3.xと2.7では、リスト内包表記に似た形式の辞書型内包表記の新しい構文が導入された。これはリストの代わりにPythonのdictが生成する。 
»> s
 Racketのハッシュテーブル内包表記は、Racketのハッシュテーブル（Racketの辞書型の実装の1つ）を生成する。 
(for/hash ([(val key) (in-indexed "ABCD")]
 #:unless (member val (string->list "CB")))
 (values key val)) 
並列リスト内包表記.
Glasgow Haskell Compilerには、リスト内包表記の構文において複数の独立した修飾子 (qualifier) の分割を許可する、並列リスト内包表記（あるいはzip-comprehension）と呼ばれる拡張構文が存在する。カンマで区切られた変数は依存関係にある（すなわち、ネストされる）が、パイプ文字で区切られた修飾子は並列に評価される（マルチスレッドで動作するという意味でなく、単に修飾子がzipされるという意味である）。 
-- 通常のリスト内包表記
a = [(x,y) | x <- [1..5], y <- [3..5]]
-- [(1,3),(1,4),(1,5),(2,3),(2,4) ...
-- zipによるリスト内包表記
b = [(x,y) | (x,y) <- zip [1..5] [3..5]]
-- [(1,3),(2,4),(3,5)]
-- 並列リスト内包表記
c = [(x,y) | x <- [1..5] | y <- [3..5]]
-- [(1,3),(2,4),(3,5)]
 Racketの標準ライブラリには、「for」と「for*」いう2つのキーワードで区別される、並列バージョンと多重ループバージョンの2つの内包表記が含まれている。例えば、ベクトル内包表記「for/vector」および「for*/vector」は、入力シーケンスに対してそれぞれ並列および多重ループによってベクトルを作成する。以下は、上のHaskellのリスト内包表記の例をRacketコードに書き下したものである。 
> (for*/list ([x (in-range 1 6)] [y (in-range 3 6)]) (list x y))
'((1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 3) (3 4) (3 5) (4 3) (4 4) (4 5) (5 3) (5 4) (5 5))
> (for/list ([x (in-range 1 6)] [y (in-range 3 6)]) (list x y))
'((1 3) (2 4) (3 5)) 
 また、Pythonでは次のように書ける。 
»> a = [(x, y) for x in range(1, 6) for y in range(3, 6)]
[(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), ...
»> b = [x for x in zip(range(1, 6), range(3, 6))]
[(1, 3), (2, 4), (3, 5)]
XQueryとXPath.
これらの言語は基本的にデータベースアクセス言語である。リスト全体（時としてXMLデータベース全体）を取得して操作することは計算時間的に不可能であるため、内包表記の概念がより重要となる。 
XPathでは、式 
/library/book//paragraph[@style='first-in-chapter'] 
 は概念的には一連の「ステップ」として評価される。各ステップはリストを生成し、次のステップは前のステップの出力の各要素にフィルターとなる関数を適用する。 
XQueryではXPathの機能はすべて使うことができるが、それに加えて、より強力な内包表記構造であるFLWOR構文も同時に使用される。 
 for $b in //book
 where $b[@pages < 400]
 order by $b//title
 return
 <shortBook>
 <title>{$b//title}</title>
 <firstPara>{($book//paragraph)[1]}</firstPara>
 </shortBook> 
 ここでは//bookというXPathが評価され、新たなシーケンス（リスト）が作成される。where句は「フィルタ」として機能し、orderは出力のソート順序を指定し、その後に続く XMLスニペットは、他の関数型言語におけるmapのようなアプローチを用いてシーケンスの各要素のXMLを構築（変換）する匿名関数として機能する。 
したがって、他の関数型言語では、上記のFLWORによる記述を次のように実装できる。 
 map(
 newXML(shortBook, newXML(title, $1.title), newXML(firstPara, $1...))
 filter(
 lt($1.pages, 400),
 xpath(//book)
 ) 
LINQ.
C# 3.0には、LINQと呼ばれる関連機能のセットが存在し、オブジェクト列挙子を操作するためのクエリ演算子が定義されている。 
var s = Enumerable.Range(0, 100).Where(x => x*x > 3).Select(x => x*2); 
 また、SQLに似た別の内包表記構文も存在する。 
var s = from x in Enumerable.Range(0, 100) where x*x > 3 select x*2; 
 LINQは、典型的なリスト内包表記の実装よりも優れた機能を提供する。内包表記のルートオブジェクトがIQueryableインターフェイスを実装する場合、単に内包表記の中のチェーンメソッドを実行するだけでなく、命令のシーケンス全体を抽象構文木オブジェクトに変換し、IQueryableオブジェクトに渡して解釈・実行する。 
これにより、とりわけIQueryableは 
C++.
C++にはリスト内包表記を直接サポートする言語機能は存在しないが、 演算子オーバーロード（例えば、|、»、»=など）を使用して、「埋め込み」クエリDSLの構文を提供するということがしばしば行われる。また、erase-removeイディオムを使用してコンテナ内の要素を選択し、STLのfor_eachアルゴリズムを使用して要素を変換することでもリスト内包表記を構築できる。 
using namespace std;
template<class C, class P, class T>
C comprehend(C&& source, const P& predicate, const T& transformation)
 // 出力を初期化
 C d = forward<C>(source);
 // 要素をフィルタ
 d.erase(remove_if(begin(d), end(d), predicate), end(d));
 // 変換を適用
 for_each(begin(d), end(d), transformation);
 return d;
int main()
 list<int> range(10); 
 // rangeはサイズ10のリストで、初期値はゼロ
 iota(begin(range), end(range), 1);
 // rangeに1,2...,10を代入
 list<int> result = comprehend(
 range,
 [](int x){return x*x <= 3;},
 [](int &x){x *= 2;});
 // resultに4,6...,20が代入される
 また、集合内包表記と似たリスト内包表記の構文・記法をC++に提供するための試みがいくつか存在する。 
counting_range(1,10) | filtered( _1*_1 > 3 ) | transformed(ret<int>( _1*2 )) 
list<int> N;
list<double> S;
for (int i = 0; i < 10; i++)
 N.push_back(i);
S « list_comprehension(3.1415 * x, x, N, x*x > 3) 
list<int> l, t;
int x, y;
for (int i = 0; i < 10; i++)
 l.push_back(i);
(x, t) = l | x2;
(t, y) = t;
t = l < 9;
t = t < 7 | even | x2; 
<catalog>
 <book>
 <title>Hamlet</title>
 <price>9.99</price>
 <author>
 <name>William Shakespeare</name>
 <country>England</country>
 </author>
 </book>
 <book>...</book>
</catalog> 
 LEESAは、XPathの/セパレータに対応する演算子として»を提供する。 XPathにおいてツリーの中間ノードを「スキップ」する//セパレーターは、LEESAでは戦略的プログラミングと呼ばれる手法を用いて実装される。以下の例では、catalog_、およびbook_、author_、name_は、それぞれ、catalog、およびbook、author、nameクラスのインスタンスである。 
// 対応するXPath: "catalog/book/author/name"
std::vector<name> author_names = 
evaluate(root, catalog_ » book_ » author_ » name_);
// 対応するXPath: "catalog//name"
std::vector<name> author_names = 
evaluate(root, catalog_ » DescendantsOf(catalog_, name_));
// 対応するXPath: "catalog//author[country=="England"]"
std::vector<name> author_names = 
evaluate(root, catalog_ » DescendantsOf(catalog_, author_)
 » Select(author_, [](const author & a) { return a.country()=="England"; })
 » name_);