リストの理解

リスト内包表記は、既存のリストに基づいてリストを作成するために一部のプログラミング言語で使用できる構文構造です。これは、マップ関数やフィルター関数 の使用とは異なり、数学的なセットビルダー表記法(セット内包表記)の形式に従います。

数学的な集合構築記法による次の例を考えてみましょう。

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

または頻繁に

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

これは、「 は、 が自然数集合( )の要素またはメンバーであるようなすべての数の「2 倍」の集合であり、その 2乗は より大きい」 と読むことができます。${\displaystyle S}$${\displaystyle x}$${\displaystyle x}$${\displaystyle \mathbb {N} }$${\displaystyle x}$${\displaystyle 3}$

最小の自然数 x = 1 は条件 x ² >3 を満たさない (条件 1 ² >3 は偽) ため、2 ·1 は S に含まれません。次の自然数 2 は、他のすべての自然数と同様に条件 (2 ² >3) を満たします。したがって、x は 2、3、4、5... で構成されます。集合Sはすべての数「2 倍の x」で構成されるため、S = {4、6、8、10、...} で表されます。つまり、S は 2 より大きいすべての偶数の集合です。

この注釈付きバージョンの例は次のとおりです。

${\displaystyle 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{述語}}}\}}$

• ${\displaystyle x}$入力セットのメンバーを表す変数です。
• ${\displaystyle \mathbb {N} }$入力集合を表す。この例では自然数の集合である。
• ${\displaystyle x^{2}>3}$入力セットのメンバーに対するフィルターとして機能する述語式です。
• ${\displaystyle 2\cdot x}$述語式を満たす入力セットのメンバーから新しいセットのメンバーを生成する出力式です。
• ${\displaystyle \{\}}$中括弧は結果が集合であることを示す
• ${\displaystyle \mid}$ ${\displaystyle ,}$縦棒は「SUCH THAT」と読みます。縦棒とコロン「:」は互換的に使用されます。
• 述語はコンマで区切られ、「AND」と読み取れます。

リストの理解には、入力リストまたは反復子から順番にリストを生成することを表す同じ構文コンポーネントがあります。

• 入力リストのメンバーを表す変数。
• 入力リスト (または反復子)。
• オプションの述語式。
• そして、述語を満たす入力反復可能オブジェクトのメンバーから出力リストのメンバーを生成する出力式。

出力リストのメンバーの生成順序は、入力内の項目の順序に基づきます。

Haskell のリスト内包構文では、このセットビルダー構造は次のように同様に記述されます。

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

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

リストの内包表記は、定義された順序で結果を返します (セットのメンバーとは異なります)。また、リストの内包表記は、リスト全体を生成するのではなく、リストのメンバーを順番に生成するため、たとえば、無限リストのメンバーの以前の Haskell 定義が可能になります。

関連する構造は、「リスト内包表記」という用語が使われる前から存在していました。SETLプログラミング言語 ( 1969 ) には、リスト内包表記に似たセット形成構造があります。たとえば、次のコードは 2 からNまでのすべての素数を出力します。

print([n in [2..N] | forall m in {2..n - 1} | n mod m > 0]);

コンピュータ代数システム AXIOM （1973）には、ストリームを処理する同様の構造があります。

このような構造に対して「理解」という用語が最初に使用されたのは、 1977年にロッド・バーストールとジョン・ダーリントンが関数型プログラミング言語NPLを説明した時でした。デビッド・ターナーは回想録「関数型プログラミング言語の歴史」^[1] で次のように回想しています。

NPLはBurstallによってPOP2に実装され、Darlingtonのプログラム変換に関する研究で使用されました（Burstall & Darlington 1977）。この言語は第一階、強い（しかし多態的ではない）型付け、純粋関数型、値渡しでした。また、例えば「セット式」もありました。

setofeven (X) <= <:x : x in X & even(x):>}}

「リスト内包」という用語に付された脚注で、ターナーは次のようにも述べている。

私は最初、これらをツェルメロ-フランケル集合論にちなんで「ZF 式」と呼んでいました。より適切な「リスト内包表記」という用語を考案したのはPhil Wadlerです。

Burstall と Darlington の NPL での研究は 1980 年代の多くの関数型プログラミング言語に影響を与えましたが、リストの内包表記が含まれていたわけではありません。例外は、1985 年にリリースされた Turner の影響力の大きい純粋で遅延のある関数型プログラミング言語Mirandaです。その後開発された標準の純粋で遅延のある関数型言語Haskellには、リストの内包表記を含む Miranda の機能が多数含まれています。

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

Haskell では、モナド内包表記は、関数型プログラミングにおけるリスト内包表記の他のモナドへの一般化です。

Python言語では、バージョン 2.7 以降、 セット内包表記の構文が導入されています。リスト内包表記と形式が似ていますが、セット内包表記はリストではなく Python セットを生成します。

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

Racketセットの理解は、リストではなく Racket セットを生成します。

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

Python言語では、バージョン 2.7 で辞書内包表記の新しい構文が導入されました。これはリスト内包表記と形式は似ていますが、リストではなく Python 辞書を生成します。

>>> 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 コンパイラには、リスト内包構文内で修飾子の複数の独立した分岐を許可する並列リスト内包( zip 内包とも呼ばれる)と呼ばれる拡張機能があります。カンマで区切られた修飾子は依存 (「ネスト」) しますが、パイプで区切られた修飾子の分岐は並列で評価されます (これは、マルチスレッドの形式を指すものではなく、単に分岐がzip されていることを意味します)。

-- 通常のリストの理解
a = [( x , y ) | x <- [ 1 .. 5 ], y <- [ 3 .. 5 ]] -- [(1,3),(1,4),(1,5),(2,3),(2,4) ...         


-- 圧縮リストの内包表記
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*」で区別されます。たとえば、ベクトル内包表記の「for/vector」と「for*/vector」は、シーケンスに対する並列反復とネスト反復によってベクトルを作成します。以下は、Haskell リスト内包表記の例の Racket コードです。

> ( for*/list ([ x (範囲内1 6 )] [ y (範囲内3 6 )]) (リスト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 (範囲内1 6 )] [ y (範囲内3 6 )]) (リスト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)]

Julia では、次のようにして実質的に同じ結果を達成できます。

# 通常の配列の理解
>>> a = [( x , y ) for x in 1 : 5 for y in 3 : 5 ]            

# 並列/圧縮配列の理解
>>> b = [ x for x in zip ( 1 : 3 , 3 : 5 )]        

唯一の違いは、Julia ではリストの代わりに配列が使われることです。

元の NPL での使用と同様に、これらは基本的にデータベース アクセス言語です。

リスト全体を取得して操作することは計算上不可能であるため、理解の概念がより重要になります (最初の「リスト全体」は XML データベース全体である可能性があります)。

XPath では、次の式:

/ライブラリ/書籍//段落[ @style = 'first-in-chapter' ]

概念的には一連の「ステップ」として評価され、各ステップでリストが生成され、次のステップでは前のステップの出力の各要素にフィルター関数が適用されます。^[4]

XQueryでは完全なXPathが利用可能ですが、より強力な理解構造であるFLWORステートメントも使用されます。 ^[5]

for $ b in // book where $ b [ @pages < 400 ] order by $ b // title return <shortBook> <title> { $ b // title } </title> <firstPara> {( $ book // paragraph )[ 1 ]} </firstPara> </shortBook>   
   
 

  
    
    
  

ここで、XPath //book が評価されてシーケンス (リストとも呼ばれます) が作成されます。where 句は関数型の「フィルター」であり、order by は結果を並べ替えます。XML<shortBook>...</shortBook>スニペットは、実際には他の関数型言語に見られる「マップ」アプローチを使用して、シーケンス内の各要素の XML を構築/変換する匿名関数です 。

したがって、別の関数型言語では、上記の FLWOR ステートメントは次のように実装できます。

map ( 
newXML ( shortBook 、newXML ( title 、$ 1. title )、newXML ( firstPara 、$ 1...)) filter ( lt ( $ 1. pages 、400 )、xpath (// book ) ) )      
  
     
    
  

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インターフェイスを実装すると、内包の連鎖メソッドを単に実行するだけでなく、コマンドのシーケンス全体が抽象構文ツリー(AST) オブジェクトに変換され、IQueryable オブジェクトに渡されて解釈および実行されます。

これにより、IQueryableは

• 互換性のない、または非効率的な理解を書き直す
• ASTを別のクエリ言語（SQLなど）に変換して実行する

C++ にはリスト内包表記を直接サポートする言語機能はありませんが、演算子のオーバーロード(たとえば、、のオーバーロード|)>>は、「埋め込み」クエリ ドメイン固有言語>>=(DSL)の表現力豊かな構文を提供するために効果的に使用されてきました。あるいは、コンテナ内の要素を選択するために消去削除イディオムを使用し、それらを変換するために STL アルゴリズム for_each を使用して、リスト内包表記を構築することもできます。

#include <アルゴリズム> #include <リスト> #include <数値> 
 
 

名前空間std を使用します。  

template < class C , class P , class T > C comprehend ( C && source , const P & predicate , const T & transformation ) { // destination Cを初期化d = forward < C > ( source );     
        

  
     

  // 要素をフィルタリング
d .erase ( remove_if ( begin ( d ) , end ( d ), predicate ), end ( d ) );     

  // 変換を適用する
for_each ( begin ( d ), end ( d ), transformation );    

  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 ; }); // 結果には 4、6、...、20 が含まれます}   
      
               
            
      

C++ にセット ビルダー表記法に似たリスト内包構造/構文を提供する取り組みが進められています。

• Boost.Range [1]ライブラリには、任意の範囲に適用してフィルタリングや変換などを実行できるアダプタ[2]の概念があります。このライブラリを使用すると、元のHaskellの例は次のようになります（匿名フィルタリングおよび変換関数にBoost.Lambda[3]を使用）（完全な例）：

  counting_range ( 1 , 10 ) |フィルタリング( _1 * _1 > 3 ) |変換済み( ret < int > ( _1 * 2 ))          
  

• この^[6]の実装ではマクロを使用し、<<演算子をオーバーロードします。これは、'if'内で有効な任意の式を評価し、任意の変数名を選択できます。ただし、スレッドセーフではありません。使用例:

リスト< int > N ;リスト< double > S ; 
 

( int i = 0 ; i < 10 ; i ++ ) N .push_back ( i )の場合。        
    

S <<リストの理解( 3.1415 * x 、x 、N 、x * x > 3 )           

• この^[7]の実装は、クラスと演算子のオーバーロードを使用したヘッド/テールスライスと、リストをフィルタリングするための|演算子（関数を使用）を提供します。使用例：

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

リスト< 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 |偶数| x2 ;    
        

• 埋め込みクエリおよびトラバーサル言語 (LEESA ^[8] ) は、演算子のオーバーロードを使用して X-Path のようなクエリを実装する C++ の埋め込み DSL です。クエリは、XSD から xml-to-c++ バインディングを使用して取得された、豊富な型付けの xml ツリーに対して実行されます。文字列のエンコードは一切ありません。xml タグの名前もクラスであるため、タイプミスは起こりません。LEESA 式がデータ モデルに存在しない不正なパスを形成する場合、C++ コンパイラはコードを拒否します。
  カタログ xml を考えてみましょう。

<catalog> 
<book> <title>ハムレット</title> <price> 9.99 </price> <author> <name>ウィリアムシェイクスピア</name> <country>イギリス</country> </author> </book> <book> ... </book>  
    
    
    
       
      
    
  
  
...
</カタログ>

LEESA は、>>XPath の / セパレーターを提供します。ツリー内の中間ノードを「スキップ」する XPath の // セパレーターは、戦略的プログラミングと呼ばれるものを使用して LEESA に実装されています。以下の例では、catalog_、book_、author_、name_ は、それぞれ catalog、book、author、name クラスのインスタンスです。

// 同等の X-Path: "catalog/book/author/name" 
std :: vector < name > author_names = assess ( root , catalog_ >> book_ >> author_ >> name_ );   
       

// 同等の X-Path: "catalog//name" 
std :: vector < name > author_names = assess ( root , catalog_ >> DescendantsOf ( catalog_ , name_ ));   
    

// 同等の X-Path: "catalog//author[country=="England"]" 
std :: vector < name > author_names = assess ( root , catalog_ >> DescendantsOf ( catalog_ , author_ ) >> Select ( author_ , []( const author & a ) { return a . country () == "England" ; }) >> name_ );   
     
                                    
                          

• 集合構築記法
• SQLのSELECT文とFROM句およびWHERE句の組み合わせ

• リストの理解については、Denis Howe 編集者の「The Free On-line Dictionary of Computing」を参照してください。
• Wadler, Philip (1990)。「モナドの理解」。1990 ACM LISP および関数型プログラミング会議の議事録、ニース。

• Python クックブックのリスト内包ワンライナーによる SQL のようなセット操作
• Scheme のリスト内包表記と関連構造に関する議論
• 言語間のリスト理解

• 公理ストリームの例

• Clojure API ドキュメント - マクロ用

• Guy Lapalme による Lisp 理解マクロの実装

• Haskell 98 レポート、第 3.11 章「リストの内包表記」。
• Glorious Glasgow Haskell コンパイル システム ユーザーズ ガイド、第 7.3.4 章「並列リストの内包表記」。
• Hugs 98 ユーザーズ ガイド、第 5.1.2 章「並列リストの内包表記 (別名 zip 内包表記)」。

• OCaml バッテリー付属
• OCaml に導入された言語拡張機能 Batteries Included

• Python チュートリアル、リストの内包表記。
• Python 言語リファレンス、リストが表示されます。
• Python 機能拡張提案 PEP 202: リストの内包表記。
• Python 言語リファレンス、ジェネレータ式。
• Python 機能拡張提案 PEP 289: ジェネレータ式。