리스트 캄프리헨션

리스트 캄프리헨션은 기존의 리스트에 기반한 리스트를 만들기 위해 일부 프로그래밍 언어에서 사용 가능한 문법적 구조다. 덕분에 map과 filter 함수의 용도와는 다르게 수학적인 "집합 작성 표기법" ("집합 캄프리헨션")의 형태를 따른다.
개요.
다음 예제에서 집합 작성 표기법의 다음과 같은 예제를 보자.
이것은 "&lt;math /&gt;는 &lt;math /&gt; &lt;math /&gt; 자연수 (&lt;math /&gt;) 집합의 요소이다"라고 읽을 수 있다.
가장 작은 자연수, x = 1일 때, x2&gt;3 라는 조건을 만족시키지 못하므로 (12&gt;3는 거짓) 2·1은 S에 포함되지 않는다. 다음 자연수, 2는 다른 모든 자연수가 그러하듯 조건을 만족한다 (22&gt;3). 따라서 S는 2·2, 2·3, 2·4...로 구성되며,  S= 4, 6, 8, 10...이므로 2보다 큰 모든 짝수를 나타낸다.
예제에 대한 주석을 보면:
리스트 캄프리헨션은 입력 리스트 또는 반복자(iterator)의 순서로 리스트를 생성하는 것을 나타내는 구문 상의 구성 요소와 같다:
출력 리스트 멤버의 생성 순서는 입력의 항목 순서에 기반한다.
이와 유사하게 하스켈의 리스트 이해 구문에서는, 이러한 집합 빌더 구성을 다음과 같이 작성한다:여기서,리스트 codice_1는 &lt;math /&gt;, codice_2는 술어를, codice_3는 출력 표현식을 나타낸다.
리스트 캄프리헨션은 (집합 멤버와는 달리) 정의된 순서로 결과를 낸다; 그리고 리스트 캄프리헨션은 리스트 전체를 생성하기 보다는, 예를 들어, 무한 리스트 에 대한 예전 하스켈 정의를 허용하기 위해 리스트 멤버를 순서대로 생성할 수도 있다.
역사.
SETL 프로그래밍 언어 (1969)는 리스트 캄프리헨션과 유사한 집합 형성 구조를 가지고 있다. 이 코드는 2부터 N까지의 모든 소수(prime number)를 출력한다:
 print([n in [2..N] | forall m in {2..n - 1} | n mod m &gt; 0]);
컴퓨터 알게브라 시스템 AXIOM (1973)은 스트림을 처리하는 유사한 구조를 가지고 있지만, 그 구조를 위한 "캄프리헨션"이라는 용어는 1977년 Rod Burstall과 John Darlington의 프로그래밍 언어인 NPL의 명세서에서 처음 사용되었다.
리스트 캄프리헨션을 구성하는 스몰토크 블록 컨텍스트 메시지는 적어도 스몰토크-80 이후부터 해당 언어에 탑재되기 시작했다.
Burstall과 Darlington의 NPL 연구는 1980대에 많은 프로그래밍 언어에 영향을 주었지만, 모두가 리스트 캄프리헨션을 포함한 것은 아니었다. 1985년에 발표된, 영향력 있는 순수 함수형 언어인 Miranda는 예외였다. 이후에 개발된 표준 순수 함수형 언어 Haskell은 Miranda의 수많은 장점은 물론, 리스트 캄프리헨션도 포함한다.
캄프리헨션은 데이터베이스를 위한 쿼리 표기법으로 제안되었으며&lt;ref&gt;Comprehensions, a query notation for DBPLs&lt;/ref&gt; "Kleisli"   데이터베이스 쿼리 언어로 구현되었다.&lt;ref&gt;The functional guts of the Kleisli query system&lt;/ref&gt;
유사 구조.
모나드 캄프리헨션.
Haskell에서, 모나드 캄프리헨션은 함수형 프로그래밍의 다른 모나드에 대한 리스트 캄프리헨션의 일반화다.
집합 캄프리헨션.
Python 언어 버전 3.x와 2.7은 집합 캄프리헨션을 위한 문법을 도입했다. 리스트 캄프리헨션의 형태와 유사하게, 집합 캄프리헨션은 리스트 대신 Python 집합을 생성한다.&lt;syntaxhighlight lang="python"&gt;
»&gt; print(s)
»&gt; type(s)
&lt;class 'set'&gt;
Racket 집합 캄프리헨션은 리스트 대신 Racket 집합을 생성한다.
 v))
딕셔너리 캄프리헨션.
Python 언어 버전 3.x와 2.7에서는 리스트 캄프리헨션의 형태와 유사하지만, 리스트 대신에 Python dicts를 생성하는, 딕셔너리 캄프리헨션을 위한 새로운 문법을 도입했다.
»&gt; s
Racket 해시 테이블 캄프리헨션은 Racket 해시 테이블 (Racket 딕셔너리 타입 구현 중 하나)을 생성한다.
(for/hash ([(val key) (in-indexed "ABCD")]
 #:unless (member val (string-&gt;list "CB")))
 (values key val))
병렬 리스트 캄프리헨션.
Glasgow Haskell 컴파일러는 병렬 리스트 캄프리헨션 (또는 zip-캄프리헨션이라고도 알려져 있는) 한 가지 예외를 갖고 있는데, 리스트 캄프리헨션 내에 다양하고 독립적인 수식어 분기가 가능하다. 반면, 콤마로 구분되는 수식어는 종속적("내재된")이며, 파이프로 구분된 수식어 분기는 병렬로 수행된다(이는 어떠한 형태의 멀티스레드 방식도 의미하지 않는다: 단지 분기가 매핑된다는 것을 의미할 뿐이다).
-- regular list comprehension
a = [(x,y) | x &lt;- [1..5], y &lt;- [3..5]]
-- [(1,3),(1,4),(1,5),(2,3),(2,4) ...
-- zipped list comprehension
b = [(x,y) | (x,y) &lt;- zip [1..5] [3..5]]
-- [(1,3),(2,4),(3,5)]
-- parallel list comprehension
c = [(x,y) | x &lt;- [1..5] | y &lt;- [3..5]]
-- [(1,3),(2,4),(3,5)]
Racket의 캄프리헨션 표준 라이브러리는 캄프리헨션에 대한 병렬과 내재된 버전을 포함하는데, 이름에서 "for"와 "for*"로 구분된다. 예를 들어, 벡터 캄프리헨션인 "for/vector"와 "for*/vector"는 각각 시퀀스에 대한 병렬 및 내재된 이터레이션을 생성한다. 다음은 Haskell 리스트 캄프리헨션 예제에 대한 Racket 코드다.
&gt; (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))
&gt; (for/list ([x (in-range 1 6)] [y (in-range 3 6)]) (list x y))
'((1 3) (2 4) (3 5))
Python에서는 다음과 같이 할 수 있다:
»&gt; 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), ...
»&gt; b = [x for x in zip(range(1, 6), range(3, 6))]
[(1, 3), (2, 4), (3, 5)]
XQuery와 XPath.
NPL의 본래 용도와 마찬가지로, 이들은 원래 데이터베이스 액세스 언어다.
이것이 캄프리헨션 컨셉을 좀 더 중요하게 만드는데, 전체 목록을 검색하고 그것에 대해 연산을 수행하는 것이 계산 상으로는 불가능하기 때문이다(초기 '전체 목록'은 전체 XML 데이터베이스일 수도 있다).
XPath의 표현은 다음과 같다:
 /library/book//paragraph[@style='first-in-chapter']
이는 개념적으로 연속된 "단계"들로 계산되는데, 여기서 각 단계는 리스트를 만들어내며 다음 단계는 이전 단계의 출력에 대한 각각의 요소에 필터 함수를 적용한다.
XQuery에서, 전체 XPath를 사용할 수 있지만, FLWOR 구문 또한 사용 가능한데, 이는 좀 더 강력한 캄프리헨션 구조다.
 for $b in //book
 where $b[@pages &lt; 400]
 order by $b//title
 return
 &lt;shortBook&gt;
 &lt;title&gt;{$b//title}&lt;/title&gt;
 &lt;firstPara&gt;{($book//paragraph)[1]}&lt;/firstPara&gt;
 &lt;/shortBook&gt;
여기서 XPath인 //book가 수행될 경우 (리스트라고도 하는) 하나의 시퀀스가 생성된다; where문은 함수적인 "필터"이고, order by문은 결과를 정렬하며,   XML 스니펫은 실제로 다른 함수형 언어에서 볼 수 있는 'map'을 사용해 시퀀스 내 각각의 요소에 대해 XML을 빌드하거나 변형하는 익명 함수다.
그래서, 위에서 본 FLWOR 구문은 다른 함수형 언에서 다음과 같이 구현될 수 있다:
 map(
 newXML(shortBook, newXML(title, $1.title), newXML(firstPara, $1...))
 filter(
 lt($1.pages, 400),
 xpath(//book)
 )
C#의 LINQ.
C# 3.0은 관련 기능 중 LINQ라고 불리는 그룹을 가지고 있는데, 객체 열거를 처리하기 위한 쿼리 동작 집합을 정의한다.
var s = Enumerable.Range(0, 100).Where(x =&gt; x*x &gt; 3).Select(x =&gt; x*2);
또한 추억의 SQL에 대한 대안으로 캄프리헨션 문법을 제공하기도 한다:
var s = from x in Enumerable.Range(0, 100) where x*x &gt; 3 select x*2;
LINQ는 전형적인 리스트 캄프리헨션 구현에 대한 기능을 제공한다. 캄프리헨션의 최상위 객체가 캄프리헨션에 대한 체인 메서드를 실행하지 않고 , IQueryable 인터페이스를 구현하는 경우, 명령의 전체 시퀀스는 AST(Abstract Syntax Tree) 객체로 변환되는데, 이는 IQueryable 객체로 전달되어 해석되고 실행된다.
덕분에 다른 것들보다도 IQueryable을 위해 다음 두 가지를 가능케한다:
C++.
C++는 리스트 캄프리헨션을 직접적으로 지원하는 어떠한 언어적 기능도 갖고 있지 않지만 연산자 오버로딩 (예를 들어, |, », »=의 재정의)은 "내장" 쿼리 DSL을 위한 표현 문법을 제공하는데 잘 사용되어 왔다. 그게 아니면, 리스트 캄프리헨션은 컨테이너 내 요소들을 선택하기 위한 erase-remove idiom과 그 요소들을 변형하기 위한 STL 알고리즘 for_each를 사용해 구성될 수 있다.
using namespace std;
template&lt;class C, class P, class T&gt;
C comprehend(C&amp;&amp; source, const P&amp; predicate, const T&amp; transformation)
 // initialize destination
 C d = forward&lt;C&gt;(source);
 // filter elements
 d.erase(remove_if(begin(d), end(d), predicate), end(d));
 // apply transformation
 for_each(begin(d), end(d), transformation);
 return d;
int main()
 list&lt;int&gt; range(10);
 // range is a list of 10 elements, all zero
 iota(begin(range), end(range), 1);
 // range now contains 1,2...,10
 list&lt;int&gt; result = comprehend(
 range,
 [](int x){return x*x &lt;= 3;},
 [](int &amp;x){x *= 2;});
 // result now contains 4,6...,20
C++에 집합-빌더 표기법과 유사한 리스트 캄프리헨션/구문을 제공하기 위한 노력들이 있다.
counting_range(1,10) | filtered( _1*_1 &gt; 3 ) | transformed(ret&lt;int&gt;( _1*2 ))
list&lt;int&gt; N;
list&lt;double&gt; S;
for (int i = 0; i &lt; 10; i++)
 N.push_back(i);
S « list_comprehension(3.1415 * x, x, N, x*x &gt; 3)
list&lt;int&gt; l, t;
int x, y;
for (int i = 0; i &lt; 10; i++)
 l.push_back(i);
(x, t) = l | x2;
(t, y) = t;
t = l &lt; 9;
t = t &lt; 7 | even | x2;
&lt;catalog&gt;
 &lt;book&gt;
 &lt;title&gt;Hamlet&lt;/title&gt;
 &lt;price&gt;9.99&lt;/price&gt;
 &lt;author&gt;
 &lt;name&gt;William Shakespeare&lt;/name&gt;
 &lt;country&gt;England&lt;/country&gt;
 &lt;/author&gt;
 &lt;/book&gt;
 &lt;book&gt;...&lt;/book&gt;
&lt;/catalog&gt;
LEESA는 X-Path의 / 구분자를 위한 »를 제공한다. 흥미롭게도, 트리 내 중간 노드를 "건너뛰는" X-Path의 // 구분자는 LEESA 내에서 전략적인 프로그래밍으로 알려져 있는 것들을 사용해 구현된다. 아래 예제에서,  catalog_, book_, author_, 그리고 name_은 각각 catalog, book, author, 그리고 name 클래스다.
// Equivalent X-Path: "catalog/book/author/name"
std::vector&lt;name&gt; author_names = 
evaluate(root, catalog_ » book_ » author_ » name_);
// Equivalent X-Path: "catalog//name"
std::vector&lt;name&gt; author_names = 
evaluate(root, catalog_ » DescendantsOf(catalog_, name_));
// Equivalent X-Path: "catalog//author[country=="England"]"
std::vector&lt;name&gt; author_names = 
evaluate(root, catalog_ » DescendantsOf(catalog_, author_)
 » Select(author_, [](const author &amp; a) { return a.country()=="England"; })
 » name_);