リスト内包表記

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

概要

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

S=\{2\cdot x\mid x\in \mathbb {N} ,\ x^{2}>3\}

あるいは

S=\{2\cdot x:x\in \mathbb {N} ,\ x^{2}>3\}

この表記は、「 $S$ は、 $x$ が自然数の集合 ( $\mathbb {N}$ ) の元であり、かつ $x$ の二乗が $3$ より大きいようなすべての『 $x$ の2倍』なる数」を意味する。

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

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

S=\{\underbrace {2\cdot x} _{\color {Violet}{\text{出力}}}\mid \underbrace {x} _{\color {Violet}{\text{変数}}}\in \underbrace {\mathbb {N} } _{\color {Violet}{\text{入力}}},\ \underbrace {x^{2}>3} _{\color {Violet}{\text{述語}}}\}

$x$ は入力された集合の元を表す変数である。
$\mathbb {N}$ は（この例においては）入力された集合である自然数の集合を表す。
$x^{2}>3$ は入力された集合の元に対するフィルターとして機能する述語式である。
$2\cdot x$ は入力された集合の元から新しい集合の元を生成する出力式である。
中括弧 $\{\}$ は結果が集合であることを表す。
縦棒 $\mid$ は「SUCH THAT」と読む。縦棒とコロン「:」は同じ意味で使用される。
カンマは述語を区切り、「AND」と読まれる。

リスト内包表記は、入力されたリストまたはイテレータからの新たなリストの生成を表すためにこれと同じ構文構造を用いるものである。

入力リストのメンバを表す変数。
入力リスト（またはイテレーター）。
述語式（任意）。
述語を満たす入力イテラブルのメンバから出力リストのメンバを生成する出力式。

出力リストのメンバーの生成順序は、入力内のアイテムの順序に基づく。

Haskellのリスト内包表記では、このような集合内包表記は同様に次のように記述される。

s = [ 2*x | x <- [0..], x^2 > 3 ]

ここで、リスト[0..]は $\mathbb {N}$ 、 x^2>3は述語式を表し、 2*xは出力式を表す。

リスト内包表記は（集合のそれとは異なり）リストで定義された順序で結果を返す。また先の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の多くの機能が取り入れられた。

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

類似構文

モナド内包表記

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

集合内包表記

プログラミング言語Pythonのバージョン3.xおよび2.7では、集合内包表記の構文が導入されている。これはリスト内包表記と同様の形式をとり、リストの代わりにPythonのsetを生成する。

>>> s = {v for v in 'ABCDABCD' if v not in 'CB'}
>>> print(s)
{'A', 'D'}
>>> type(s)
<class 'set'>
>>>

Racketの集合内包表記は、リストではなくRacketのsetを生成する。

(for/set ([v "ABCDABCD"] #:unless (member v (string->list "CB")))
      v))

辞書型内包表記

プログラミング言語Pythonのバージョン3.xと2.7では、リスト内包表記に似た形式の辞書型内包表記の新しい構文が導入された。これはリストの代わりにPythonのdictが生成する。

>>> s = {key: val for key, val in enumerate('ABCD') if val not in 'CB'}
>>> s
{0: 'A', 3: 'D'}
>>>

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), ...

# 並列 (zipによる) 内包表記
>>> 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']

は概念的には一連の「ステップ」として評価される。各ステップはリストを生成し、次のステップは前のステップの出力の各要素にフィルターとなる関数を適用する^[3]。 XQueryではXPathの機能はすべて使うことができるが、それに加えて、より強力な内包表記構造であるFLWOR構文も同時に使用される^[4]。

 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は出力のソート順序を指定し、その後に続く<shortBook>...</shortBook> 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は

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

C++

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

#include <algorithm>
#include <list>
#include <numeric>

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++に提供するための試みがいくつか存在する。

Boostのrange^[5]ライブラリには、アダプタ記法^[6]が存在し、フィルタや変換などを任意のrangeに適用することができる。このライブラリーを使用すると、上のHaskellのコード例は次のように書ける（匿名フィルタと変換関数のためにBoost.Lambda^[7]を用いている）（完全な例）。
```
counting_range(1,10) | filtered( _1*_1 > 3 ) | transformed(ret<int>( _1*2 ))
```
ある実装^[8]では、マクロと、<<演算子のオーバーロードを使用する。これは条件文の中の任意の式を有効と評価するため、条件文中では任意の変数名を選択できる。ただし、スレッドセーフではない。以下のように使用される。
```
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)
```

ある実装^[9]では、クラスと演算子のオーバーロードを使用して、head/tailスライスの機能と、関数を用いてリストをフィルタするための | 演算子を提供する。以下のように用いられる。

bool even(int x) { return x % 2 == 0; }
bool x2(int &x) { x *= 2; return true; }

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;

Language for Embedded Query and Traversal（LEESA^[10]）は、演算子のオーバーロードを用いてXPathに似たクエリを実装するC++の埋め込みDSLである。クエリは、XMLからC++へのバインディングを使用してXSDから取得された、型付けされたXMLツリーの上で実行される。文字列としては変換されない。XMLタグの名前までもがクラスとなるので、タイプミスによるバグが発生しにくくなる。LEESA式がデータモデルに存在しない誤ったパスを生成する場合、C++コンパイラはコンパイルに失敗する。
<catalog>なるXMLについて考えてみる。
```
<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_);

脚注・参考文献

^ Comprehensions, a query notation for DBPLs
^ The functional guts of the Kleisli query system
^ “2.1 Location Steps”. XML Path Language (XPath). W3C (16 November 1999). 9 December 2012時点のオリジナルよりアーカイブ。24 December 2008閲覧。
^ “XQuery FLWOR Expressions”. W3Schools. 2011年10月8日時点のオリジナルよりアーカイブ。2020年4月17日閲覧。
^ “Chapter 1. Range 2.0”. www.boost.org. 2020年4月16日閲覧。
^ “Range Adaptors”. www.boost.org. 2020年4月16日閲覧。
^ “Chapter 20. Boost.Lambda - 1.72.0”. www.boost.org. 2020年4月16日閲覧。
^ “Single-variable List Comprehension in C++ using Preprocessor Macros”. 2011年8月21日時点のオリジナルよりアーカイブ。2011年1月9日閲覧。
^ “C++ list comprehensions”. 2017年7月7日時点のオリジナルよりアーカイブ。2011年1月9日閲覧。
^ “Language for Embedded Query and Traversal (LEESA)”. 2020年4月17日閲覧。

The Free On-line Dictionary of ComputingのList Comprehensionの項、編集: Denis Howe
Trinder, Phil (1992). "Comprehensions, a query notation for DBPLs". Proceedings of the third international workshop on Database programming languages: bulk types & persistent data, Nafplion, Greece. pp. 55–68.
Wadler, Philip (1990). "Comprehending Monads". Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice.
Wong, Limsoon (2000). "The Functional Guts of the Kleisli Query System". Proceedings of the fifth ACM SIGPLAN international conference on Functional programming. International Conference on Functional Programming. pp. 1–10.

Haskell

The Haskell 98 Report, chapter 3.11 List Comprehensions.
The Glorious Glasgow Haskell Compilation System User's Guide, chapter 7.3.4 Parallel List Comprehensions.
The Hugs 98 User's Guide, chapter 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions).

OCaml

Python

The Python Tutorial, List Comprehensions.
Python Language Reference, List displays.
Python Enhancement Proposal PEP 202: List Comprehensions.
Python Language Reference, Generator expressions.
Python Enhancement Proposal PEP 289: Generator Expressions.

外部リンク

Python CookbookのSQLライクな集合演算子にはリスト内包表記のワンライナーが含まれている。
Discussion on list comprehensions in Scheme and related constructs
List Comprehensions across languages

[1] Comprehensions, a query notation for DBPLs

[2] The functional guts of the Kleisli query system

[3] “2.1 Location Steps”. XML Path Language (XPath). W3C (16 November 1999). 9 December 2012時点のオリジナルよりアーカイブ。24 December 2008閲覧。

[4] “XQuery FLWOR Expressions”. W3Schools. 2011年10月8日時点のオリジナルよりアーカイブ。2020年4月17日閲覧。

[5] “Chapter 1. Range 2.0”. www.boost.org. 2020年4月16日閲覧。

[6] “Range Adaptors”. www.boost.org. 2020年4月16日閲覧。

[7] “Chapter 20. Boost.Lambda - 1.72.0”. www.boost.org. 2020年4月16日閲覧。

[8] “Single-variable List Comprehension in C++ using Preprocessor Macros”. 2011年8月21日時点のオリジナルよりアーカイブ。2011年1月9日閲覧。

[9] “C++ list comprehensions”. 2017年7月7日時点のオリジナルよりアーカイブ。2011年1月9日閲覧。

[10] “Language for Embedded Query and Traversal (LEESA)”. 2020年4月17日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

概要

歴史