リスト内包表記のソースを表示

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

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

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

あるいは 

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

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

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

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

: <math>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{述語}}}\}</math>

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

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

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

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

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

リスト内包表記は（集合のそれとは異なり）リストで定義された順序で結果を返す。また先のHaskellの例における無限長のリストのような定義を受け入れるために、リスト内包表記はリスト全体を変換するのではなく、リストのメンバを順に生成するような[[ジェネレータ (プログラミング)|ジェネレータ]]を返却する。 

== 歴史 ==
プログラミング言語[[ SETL |SETL]]（1969）には、リスト内包表記に似た集合形成構文が存在する。例えば以下のコードは2からNまでのすべての素数を出力する。 <syntaxhighlight lang="text">
print([n in [2..N] | forall m in {2..n - 1} | n mod m > 0]); 
</syntaxhighlight> [[数式処理システム]][[Axiom (数式処理システム)|AXIOM]]（1973）にも、 [[ストリーム (プログラミング)|ストリーム]]を処理するための同様の構文が存在するが、このような構文に対して「内包表記（comprehension）」という用語が用いられたのは、1977年にRod BurstallとJohn Darlingtonが関数型プログラミング言語[[ NPLプログラミング言語|NPL]]について行ったものが最初である。 

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

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

またリスト内包表記はデータベースのクエリ表記法としても提案され<ref>[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=135271 Comprehensions, a query notation for DBPLs]</ref>、[[ハインリッヒ・クライスリ|Kleisli]]データベースクエリ言語に実装された<ref>[http://portal.acm.org/citation.cfm?id=351241&dl=ACM&coll=portal The functional guts of the Kleisli query system]</ref>。 

== 類似構文 ==

=== モナド内包表記 ===
Haskellには[[モナド (プログラミング)#構文糖衣: do記法|モナド内包表記]]という記法が存在する。これは関数型プログラミングにおけるリスト内包表記の[[モナド (プログラミング)|モナド]]への一般化である。 

=== 集合内包表記 ===
プログラミング言語Pythonのバージョン3.xおよび2.7では、 [[セット (抽象データ型)|集合]]内包表記の構文が導入されている。これはリスト内包表記と同様の形式をとり、リストの代わりにPythonのsetを生成する。 <syntaxhighlight lang="python">
>>> s = {v for v in 'ABCDABCD' if v not in 'CB'}
>>> print(s)
{'A', 'D'}
>>> type(s)
<class 'set'>
>>>
</syntaxhighlight> [[Racket]]の集合内包表記は、リストではなくRacketのsetを生成する。 <syntaxhighlight lang="scheme">
(for/set ([v "ABCDABCD"] #:unless (member v (string->list "CB")))
      v))
</syntaxhighlight>

=== 辞書型内包表記 ===
プログラミング言語Pythonのバージョン3.xと2.7では、リスト内包表記に似た形式の[[連想配列|辞書型]]内包表記の新しい構文が導入された。これはリストの代わりにPythonの[https://docs.python.org/library/stdtypes.html#dict dict]が生成する。 <syntaxhighlight lang="python">
>>> s = {key: val for key, val in enumerate('ABCD') if val not in 'CB'}
>>> s
{0: 'A', 3: 'D'}
>>>
</syntaxhighlight> Racketのハッシュテーブル内包表記は、Racketのハッシュテーブル（Racketの辞書型の実装の1つ）を生成する。 <syntaxhighlight lang="scheme">
(for/hash ([(val key) (in-indexed "ABCD")]
      #:unless (member val (string->list "CB")))
 (values key val)) 
</syntaxhighlight>

=== 並列リスト内包表記 ===
[[Glasgow Haskell Compiler]]には、リスト内包表記の構文において複数の独立した修飾子 (qualifier) の分割を許可する、'''並列リスト内包表記'''（あるいは'''zip-comprehension'''）と呼ばれる拡張構文が存在する。カンマで区切られた変数は依存関係にある（すなわち、ネストされる）が、パイプ文字で区切られた修飾子は並列に評価される（マルチスレッドで動作するという意味でなく、単に修飾子が[[高階関数#zip|zip]]されるという意味である）。 <syntaxhighlight lang="haskell">
-- 通常のリスト内包表記
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)]
</syntaxhighlight> Racketの標準ライブラリには、「for」と「for*」いう2つのキーワードで区別される、並列バージョンと多重ループバージョンの2つの内包表記が含まれている。例えば、ベクトル内包表記「for/vector」および「for*/vector」は、入力シーケンスに対してそれぞれ並列および多重ループによってベクトルを作成する。以下は、上のHaskellのリスト内包表記の例をRacketコードに書き下したものである。 <syntaxhighlight lang="scheme">
> (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)) 
</syntaxhighlight> また、Pythonでは次のように書ける。 <syntaxhighlight lang="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)]
</syntaxhighlight>

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



XPathでは、式 <syntaxhighlight lang="xquery">
/library/book//paragraph[@style='first-in-chapter'] 
</syntaxhighlight> は概念的には一連の「ステップ」として評価される。各ステップはリストを生成し、次のステップは前のステップの出力の各要素にフィルターとなる関数を適用する<ref>{{Cite web|url=http://www.w3.org/TR/xpath#section-Location-Steps|title=2.1 Location Steps|website=XML Path Language (XPath)|date=16 November 1999|publisher=[[W3C]]|accessdate=24 December 2008|archiveurl=https://web.archive.org/web/20121209085946/http://www.w3.org/TR/xpath/#section-Location-Steps|archivedate=9 December 2012}}</ref>。  

XQueryではXPathの機能はすべて使うことができるが、それに加えて、より強力な内包表記構造である[[FLWOR]]構文も同時に使用される<ref>{{Cite web|url=https://www.w3schools.com/XQuery/xquery_flwor.asp|title=XQuery FLWOR Expressions|website=[[W3Schools]]|archiveurl=https://web.archive.org/web/20111008001258/http://w3schools.com/xquery/xquery_flwor.asp|archivedate=2011-10-08|accessdate=2020-04-17|publisher=}}</ref>。 <syntaxhighlight lang="xquery">
 for $b in //book
 where $b[@pages < 400]
 order by $b//title
 return
  <shortBook>
   <title>{$b//title}</title>
   <firstPara>{($book//paragraph)[1]}</firstPara>
  </shortBook> 
</syntaxhighlight> ここでは//bookというXPathが評価され、新たなシーケンス（リスト）が作成される。where句は「フィルタ」として機能し、orderは出力のソート順序を指定し、その後に続く{{Tag|shortBook}} XMLスニペットは、他の関数型言語におけるmapのようなアプローチを用いてシーケンスの各要素のXMLを構築（変換）する匿名関数として機能する。 

したがって、他の関数型言語では、上記のFLWORによる記述を次のように実装できる。 <syntaxhighlight lang="xquery">
 map(
  newXML(shortBook, newXML(title, $1.title), newXML(firstPara, $1...))
  filter(
   lt($1.pages, 400),
   xpath(//book)
  )
 ) 
</syntaxhighlight>

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

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

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

=== C++ ===
C++にはリスト内包表記を直接サポートする言語機能は存在しないが、 [[利用者定義演算子|演算子オーバーロード]]（例えば、|、>>、>>=など）を使用して、「埋め込み」クエリ[[ドメイン固有言語|DSL]]の構文を提供するということがしばしば行われる。また、[[消去-削除イディオム|erase-remove]]イディオムを使用してコンテナ内の要素を選択し、STLのfor_eachアルゴリズムを使用して要素を変換することでもリスト内包表記を構築できる。 <syntaxhighlight lang="cpp">
#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が代入される
}
</syntaxhighlight> また、集合内包表記と似たリスト内包表記の構文・記法をC++に提供するための試みがいくつか存在する。 

* [[Boost C++ライブラリ|Boost]]のrange<ref>{{Cite web|title=Chapter 1. Range 2.0|url=https://www.boost.org/doc/libs/1_72_0/libs/range/doc/html/index.html|website=www.boost.org|accessdate=2020-04-16}}</ref>ライブラリには、アダプタ記法<ref>{{Cite web|title=Range Adaptors|url=https://www.boost.org/doc/libs/1_72_0/libs/range/doc/html/range/reference/adaptors.html|website=www.boost.org|accessdate=2020-04-16}}</ref>が存在し、フィルタや変換などを任意のrangeに適用することができる。このライブラリーを使用すると、上のHaskellのコード例は次のように書ける（匿名フィルタと変換関数のためにBoost.Lambda<ref>{{Cite web|title=Chapter 20. Boost.Lambda - 1.72.0|url=https://www.boost.org/doc/libs/1_72_0/doc/html/lambda.html|website=www.boost.org|accessdate=2020-04-16}}</ref>を用いている）（[http://codepad.org/y4bpgLJu 完全な例] ）。 <syntaxhighlight lang="cpp">
counting_range(1,10) | filtered( _1*_1 > 3 ) | transformed(ret<int>( _1*2 )) 
</syntaxhighlight>
* ある実装<ref>{{Cite web|url=http://mfoliveira.org/blog/2011/01/04/simple-list-comprehension-in-cp-using-preprocessor-macros/|title=Single-variable List Comprehension in C++ using Preprocessor Macros|accessdate=2011-01-09|archiveurl=https://web.archive.org/web/20110821211656/http://mfoliveira.org/blog/2011/01/04/simple-list-comprehension-in-cp-using-preprocessor-macros/|archivedate=2011-08-21}}</ref>では、マクロと、<<演算子のオーバーロードを使用する。これは条件文の中の任意の式を有効と評価するため、条件文中では任意の変数名を選択できる。ただし、[[スレッドセーフ]]ではない。以下のように使用される。 <syntaxhighlight lang="cpp">
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) 
</syntaxhighlight>
* ある実装<ref>{{Cite web|url=http://www.tedunangst.com/listcc.html|title=C++ list comprehensions|accessdate=2011-01-09|archiveurl=https://web.archive.org/web/20170707125836/http://www.tedunangst.com/listcc.html|archivedate=2017-07-07}}</ref>では、クラスと演算子のオーバーロードを使用して、head/tailスライスの機能と、関数を用いてリストをフィルタするための | 演算子を提供する。以下のように用いられる。 <syntaxhighlight lang="cpp">
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; 
</syntaxhighlight>
* Language for Embedded Query and Traversal（LEESA<ref>{{Cite web|url=http://www.dre.vanderbilt.edu/LEESA/|title=Language for Embedded Query and Traversal (LEESA)|accessdate=2020-04-17|publisher=}}</ref>）は、演算子のオーバーロードを用いてXPathに似たクエリを実装するC++の埋め込みDSLである。クエリは、XMLからC++へのバインディングを使用してXSDから取得された、型付けされたXMLツリーの上で実行される。文字列としては変換されない。XMLタグの名前までもがクラスとなるので、タイプミスによるバグが発生しにくくなる。LEESA式がデータモデルに存在しない誤ったパスを生成する場合、C++コンパイラはコンパイルに失敗する。 <br /> <catalog>なるXMLについて考えてみる。 <syntaxhighlight lang="xml">
<catalog>
 <book>
  <title>Hamlet</title>
  <price>9.99</price>
  <author>
   <name>William Shakespeare</name>
   <country>England</country>
  </author>
 </book>
 <book>...</book>
...
</catalog> 
</syntaxhighlight>
 LEESAは、XPathの/セパレータに対応する演算子として>>を提供する。 XPathにおいてツリーの中間ノードを「スキップ」する//セパレーターは、LEESAでは戦略的プログラミングと呼ばれる手法を用いて実装される。以下の例では、catalog_、およびbook_、author_、name_は、それぞれ、catalog、およびbook、author、nameクラスのインスタンスである。 <syntaxhighlight lang="cpp">
// 対応する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_);
</syntaxhighlight>

== 関連項目 ==

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

== 脚注・参考文献 ==
{{Reflist}}

* The Free On-line Dictionary of Computingの[https://web.archive.org/web/20050125080818/http://ftp.sunet.se/foldoc/foldoc.cgi?list+comprehension List Comprehension]の項、編集: Denis Howe 
* {{Cite conference|first1=Phil|last=Trinder|url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=135271|title=Comprehensions, a query notation for DBPLs|book-title=Proceedings of the third international workshop on Database programming languages: bulk types & persistent data, Nafplion, Greece|pages=55–68|year=1992}} 
* {{Cite conference|first1=Philip|last=Wadler|url=http://citeseer.ist.psu.edu/wadler92comprehending.html|title=Comprehending Monads|book-title=Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice|year=1990}} 
* {{Cite conference|first1=Limsoon|last=Wong|url=http://portal.acm.org/citation.cfm?id=351241&dl=ACM&coll=portal|title=The Functional Guts of the Kleisli Query System|conference=International Conference on Functional Programming|book-title=Proceedings of the fifth ACM SIGPLAN international conference on Functional programming|pages=1–10|year=2000}} 

=== Haskell ===

* The Haskell 98 Report, chapter [http://haskell.org/onlinereport/exps.html#list-comprehensions 3.11 List Comprehensions].
* The Glorious Glasgow Haskell Compilation System User's Guide, chapter [https://web.archive.org/web/20051129140339/http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#parallel-list-comprehensions 7.3.4 Parallel List Comprehensions].
* The Hugs 98 User's Guide, chapter [https://web.archive.org/web/20140515114545/http://cvs.haskell.org/Hugs/pages/users_guide/hugs-ghc.html#ZIP-COMPREHENSION 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions)].

=== OCaml ===

* [http://batteries.forge.ocamlcore.org/ OCaml Batteries Included]
* [http://batteries.forge.ocamlcore.org/doc.preview:batteries-alpha3/html/extensions.html Language extensions introduced in OCaml Batteries Included]

=== Python ===

* The Python Tutorial, [https://docs.python.org/tutorial/datastructures.html#list-comprehensions List Comprehensions].
* Python Language Reference, [https://docs.python.org/reference/expressions.html#list-displays List displays].
* Python Enhancement Proposal [https://www.python.org/peps/pep-0202.html PEP 202: List Comprehensions].
* Python Language Reference, [https://docs.python.org/reference/expressions.html#generator-expressions Generator expressions].
* Python Enhancement Proposal [https://python.org/peps/pep-0289.html PEP 289: Generator Expressions].

=== Common Lisp ===

* [http://rali.iro.umontreal.ca/rali/?q=en/node/886 Implementation of a Lisp comprehension macro] by Guy Lapalme

=== Clojure ===

* [https://clojuredocs.org/clojure.core/for Clojure API documentation - ''for'' macro]

=== Axiom ===

* [https://web.archive.org/web/20051018040438/http://page.axiom-developer.org/zope/mathaction/Streams Axiom stream examples]

== 外部リンク ==

* [http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/159974 Python Cookbook]のSQLライクな集合演算子にはリスト内包表記のワンライナーが含まれている。
* [http://lambda-the-ultimate.org/classic/message11326.html Discussion on list comprehensions in Scheme and related constructs]
* [https://langexplr.blogspot.com/2007/02/list-comprehensions-across-languages_18.html List Comprehensions across languages]
[[Category:プログラミング言語の構文]]
[[Category:未査読の翻訳があるページ]]
{{DEFAULTSORT:りすとないほうひようき}}