리스트 캄프리헨션

리스트 캄프리헨션은 기존의 리스트에 기반한 리스트를 만들기 위해 일부 프로그래밍 언어에서 사용 가능한 문법적 구조다. 덕분에 map과 filter 함수의 용도와는 다르게 수학적인 집합 작성 표기법 (집합 캄프리헨션)의 형태를 따른다.

다음 예제에서 집합 작성 표기법의 다음과 같은 예제를 보자.

${\displaystyle }$

이것은 "${\displaystyle }$는 ${\displaystyle }$ ${\displaystyle }$ 자연수 (${\displaystyle }$) 집합의 요소이다"라고 읽을 수 있다.

가장 작은 자연수, x = 1일 때, x²>3 라는 조건을 만족시키지 못하므로 (1²>3는 거짓) 2·1은 S에 포함되지 않는다. 다음 자연수, 2는 다른 모든 자연수가 그러하듯 조건을 만족한다 (2²>3). 따라서 S는 2·2, 2·3, 2·4...로 구성되며,  S= 4, 6, 8, 10,...이므로 2보다 큰 모든 짝수를 나타낸다.

예제에 대한 주석을 보면:

${\displaystyle }$

• ${\displaystyle }$
• ${\displaystyle }$
• ${\displaystyle }$ 은 입력 집합 멤버에 대한 필터로 동작하는 술어 표현식이다.
• ${\displaystyle }$ 는 술어 표현식을 만족하는 입력 집합의 멤버로부터 새로운 집합의 멤버를 만들어내는 출력 표현식이다.
• ${\displaystyle }$ 중괄호는 결과가 집합임을 가리킨다.
• ${\displaystyle }$ 수직 바와 콤마는 구분 기호다.

리스트 캄프리헨션은 입력 리스트 또는 반복자(iterator)의 순서로 리스트를 생성하는 것을 나타내는 구문 상의 구성 요소와 같다:

• 입력 리스트 멤버를 나타내는 변수.
• 입력 리스트(또는 반복자).
• 술어 표현식(옵션).
• 그리고 술어를 만족시키는 반복 가능한 입력 멤버로부터 출력 리스트의 멤버를 만들어내는 출력 표현식.

출력 리스트 멤버의 생성 순서는 입력의 항목 순서에 기반한다.

이와 유사하게 하스켈의 리스트 이해 구문에서는, 이러한 집합 빌더 구성을 다음과 같이 작성한다:

여기서,리스트 [0..]는 ${\displaystyle }$, x^2>3는 술어를, 2*x는 출력 표현식을 나타낸다.

리스트 캄프리헨션은 (집합 멤버와는 달리) 정의된 순서로 결과를 낸다; 그리고 리스트 캄프리헨션은 리스트 전체를 생성하기 보다는, 예를 들어, 무한 리스트 에 대한 예전 하스켈 정의를 허용하기 위해 리스트 멤버를 순서대로 생성할 수도 있다.

SETL 프로그래밍 언어 (1969)는 리스트 캄프리헨션과 유사한 집합 형성 구조를 가지고 있다. 이 코드는 2부터 N까지의 모든 소수(prime number)를 출력한다:

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

컴퓨터 알게브라 시스템 AXIOM (1973)은 스트림을 처리하는 유사한 구조를 가지고 있지만, 그 구조를 위한 "캄프리헨션"이라는 용어는 1977년 Rod Burstall과 John Darlington의 프로그래밍 언어인 NPL의 명세서에서 처음 사용되었다.

리스트 캄프리헨션을 구성하는 스몰토크 블록 컨텍스트 메시지는 적어도 스몰토크-80 이후부터 해당 언어에 탑재되기 시작했다.

Burstall과 Darlington의 NPL 연구는 1980대에 많은 프로그래밍 언어에 영향을 주었지만, 모두가 리스트 캄프리헨션을 포함한 것은 아니었다. 1985년에 발표된, 영향력 있는 순수 함수형 언어인 Miranda는 예외였다. 이후에 개발된 표준 순수 함수형 언어 하스켈은 Miranda의 수많은 장점은 물론, 리스트 캄프리헨션도 포함한다.

캄프리헨션은 데이터베이스를 위한 쿼리 표기법으로 제안되었으며^[1] Kleisli   데이터베이스 쿼리 언어로 구현되었다.^[2]

Haskell에서, 모나드 캄프리헨션은 함수형 프로그래밍의 다른 모나드에 대한 리스트 캄프리헨션의 일반화다.

Python 언어 버전 3.x와 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 언어 버전 3.x와 2.7에서는 리스트 캄프리헨션의 형태와 유사하지만, 리스트 대신에 Python dicts를 생성하는, 딕셔너리 캄프리헨션을 위한 새로운 문법을 도입했다.

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

Racket 해시 테이블 캄프리헨션은 Racket 해시 테이블 (Racket 딕셔너리 타입 구현 중 하나)을 생성한다.

(for/hash ([(val key) (in-indexed "ABCD")]
           #:unless (member val (string->list "CB")))
  (values key val))

Glasgow Haskell 컴파일러는 병렬 리스트 캄프리헨션 (또는 zip-캄프리헨션이라고도 알려져 있는) 한 가지 예외를 갖고 있는데, 리스트 캄프리헨션 내에 다양하고 독립적인 수식어 분기가 가능하다. 반면, 콤마로 구분되는 수식어는 종속적("내재된")이며, 파이프로 구분된 수식어 분기는 병렬로 수행된다(이는 어떠한 형태의 멀티스레드 방식도 의미하지 않는다: 단지 분기가 매핑된다는 것을 의미할 뿐이다).

-- regular list comprehension
a = [(x,y) | x <- [1..5], y <- [3..5]]
-- [(1,3),(1,4),(1,5),(2,3),(2,4) ...

-- zipped list comprehension
b = [(x,y) | (x,y) <- zip [1..5] [3..5]]
-- [(1,3),(2,4),(3,5)]

-- parallel list comprehension
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 (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에서는 다음과 같이 할 수 있다:

# regular list comprehension
>>> 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), ...

# parallel/zipped list comprehension
>>> b = [x for x in zip(range(1, 6), range(3, 6))]
[(1, 3), (2, 4), (3, 5)]

NPL의 본래 용도와 마찬가지로, 이들은 원래 데이터베이스 액세스 언어다.

이것이 캄프리헨션 컨셉을 좀 더 중요하게 만드는데, 전체 목록을 검색하고 그것에 대해 연산을 수행하는 것이 계산 상으로는 불가능하기 때문이다(초기 '전체 목록'은 전체 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>

여기서 XPath인 //book가 수행될 경우 (리스트라고도 하는) 하나의 시퀀스가 생성된다; where문은 함수적인 "필터"이고, order by문은 결과를 정렬하며,  <shortBook>...</shortBook> XML 스니펫은 실제로 다른 함수형 언어에서 볼 수 있는 'map'을 사용해 시퀀스 내 각각의 요소에 대해 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(Abstract Syntax Tree) 객체로 변환되는데, 이는 IQueryable 객체로 전달되어 해석되고 실행된다.

덕분에 다른 것들보다도 IQueryable을 위해 다음 두 가지를 가능케한다:

• 비호환적되거나 비효율적인 캄프리헨션의 재작성
• 예외를 위해 AST를 또 다른 쿼리 언어(예를 들어, SQL)로 변환

C++는 리스트 캄프리헨션을 직접적으로 지원하는 어떠한 언어적 기능도 갖고 있지 않지만 연산자 오버로딩 (예를 들어, |, >>, >>=의 재정의)은 "내장" 쿼리 DSL을 위한 표현 문법을 제공하는데 잘 사용되어 왔다. 그게 아니면, 리스트 캄프리헨션은 컨테이너 내 요소들을 선택하기 위한 erase-remove idiom과 그 요소들을 변형하기 위한 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)
{
  // initialize destination
  C d = forward<C>(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<int> range(10);
      // range is a list of 10 elements, all zero
  iota(begin(range), end(range), 1);
      // range now contains 1,2,...,10

  list<int> result = comprehend(
      range,
      [](int x){return x*x <= 3;},
      [](int &x){x *= 2;});
      // result now contains 4,6,...,20
}

C++에 집합-빌더 표기법과 유사한 리스트 캄프리헨션/구문을 제공하기 위한 노력들이 있다.

• Boost.Range 라이브러리에는 어떤 범위에든 적용할 수 있고, 필터링 및 변환 등을 할 수 있는 어댑터 표기법이 있다. 이 라이브러리와 함께, 앞서 본 Haskell 예제를 (익명 필터와 변형 기능을 위해 Boost.Lambda를 사용해) 다음과 같이 작성할 수 있다(전체 예제 보관됨 2011-07-20 - 웨이백 머신):

  counting_range(1,10) | filtered( _1*_1 > 3 ) | transformed(ret<int>( _1*2 ))
  

• 다음^[5] 구현은 매크로를 사용하며 << 연산자 재정의한다. 'if' 내부의 모든 표현식이 유효한지를 평가하며, 어떤 변수 이름이든지 선택될 수 있다. 하지만, 이는 스레드에 안전하지 않다. 사용 예제:

  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)
  

• 다음^[6] 구현은 클래스 및 연산자 오버로딩을 사용한 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;
  

• 내장 쿼리와 순회를 위한 언어 (LEESA^[7])는 C++에 내장된 DSL로 연산자 오버로딩을 사용해 X-Path와 같은 쿼리를 구현한다. 이 쿼리는 XSD에서  xml-to-c++ 바인딩을 사용해 얻은 바인딩된 충분한 형식의 xml 트리 상에서 실행된다. 문자열 인코딩은 전혀 없다. xml 태그 이름 조차도 클래스이므로, 오타가 날 방법은 없다. LEESA 표현식이 데이터 모델 내에 존재치 않는 잘못된 경로를 형성할 경우, C++ 컴파일러는 코드를 거부한다. a 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는 X-Path의 / 구분자를 위한 >>를 제공한다. 흥미롭게도, 트리 내 중간 노드를 "건너뛰는" X-Path의 // 구분자는 LEESA 내에서 전략적인 프로그래밍으로 알려져 있는 것들을 사용해 구현된다. 아래 예제에서,  catalog_, book_, author_, 그리고 name_은 각각 catalog, book, author, 그리고 name 클래스다.

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

// Equivalent X-Path: "catalog//name"
std::vector<name> author_names = 
evaluate(root, catalog_ >> DescendantsOf(catalog_, name_));

// Equivalent X-Path: "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_);

• SQL에서 FROM과 WHERE문과 함께 사용되는 SELECT문

• List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe.

• 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 Batteries Included
• Language extensions introduced in OCaml Batteries Included 보관됨 2016-03-03 - 웨이백 머신

• 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.

• Implementation of a Lisp comprehension macro by Guy Lapalme

• Clojure API documentation - for macro

• Axiom stream examples

• SQL-like set operations with list comprehension one-liners in the Python Cookbook 보관됨 2008-07-02 - 웨이백 머신
• Discussion on list comprehensions in Scheme and related constructs
• List Comprehensions across languages