List comprehension

A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical set-builder notation (set comprehension) as distinct from the use of map and filter functions.

Overview

Consider the following example in set-builder notation.

This can be read, " is the set of all numbers "2 times " where is an item in the set of natural numbers (), for which squared is greater than ."

The smallest natural number, x = 1, fails to satisfy the condition x2>3 (the condition 12>3 is false) so 2 ·1 is not included in S. The next natural number, 2, does satisfy the condition (22>3) as does every other natural number. Thus S consists of 2 ·2, 2 ·3, 2 ·4... so S = 4, 6, 8, 10,... i.e., all even numbers greater than 2.

In this annotated version of the example:

A list comprehension has the same syntactic components to represent generation of a list in order from an input list or iterator:

The order of generation of members of the output list is based on the order of items in the input.

In Haskell's list comprehension syntax, this set-builder construct would be written similarly, as:

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

Here, the list [0..] represents , x^2>3 represents the predicate, and 2*x represents the output expression.

List comprehensions give results in a defined order (unlike the members of sets); and list comprehensions may generate the members of a list in order, rather than produce the entirety of the list thus allowing, for example, the previous Haskell definition of the members of an infinite list.

History

The SETL programming language (1969) has a set formation construct which is similar to list comprehensions. This code prints all prime numbers from 2 to N:

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

The computer algebra system AXIOM (1973) has a similar construct that processes streams, but the first use of the term "comprehension" for such constructs was in Rod Burstall and John Darlington's description of their functional programming language NPL from 1977.

Smalltalk block context messages which constitute list comprehensions have been in that language since at least Smalltalk-80.

Burstall and Darlington's work with NPL influenced many functional programming languages during the 1980s, but not all included list comprehensions. An exception was the influential pure lazy functional programming language Miranda, which was released in 1985. The subsequently developed standard pure lazy functional language Haskell includes many of Miranda's features, including list comprehensions.

Comprehensions were proposed as a query notation for databases[1] and were implemented in the Kleisli database query language.[2]

Examples in different programming languages

Similar constructs

Monad comprehension

In Haskell, a monad comprehension is a generalization of the list comprehension to other monads in functional programming.

Set comprehension

Version 3.x and 2.7 of the Python language introduces syntax for set comprehensions. Similar in form to list comprehensions, set comprehensions generate Python sets instead of lists.

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

Racket set comprehensions generate Racket sets instead of lists.

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

Dictionary comprehension

Version 3.x and 2.7 of the Python language introduced a new syntax for dictionary comprehensions, similar in form to list comprehensions but which generate Python dicts instead of lists.

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

Racket hash table comprehensions generate Racket hash tables (one implementation of the Racket dictionary type).

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

Parallel list comprehension

The Glasgow Haskell Compiler has an extension called parallel list comprehension (also known as zip-comprehension) that permits multiple independent branches of qualifiers within the list comprehension syntax. Whereas qualifiers separated by commas are dependent ("nested"), qualifier branches separated by pipes are evaluated in parallel (this does not refer to any form of multithreadedness: it merely means that the branches are zipped).

-- 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's comprehensions standard library contains parallel and nested versions of its comprehensions, distinguished by "for" vs "for*" in the name. For example, the vector comprehensions "for/vector" and "for*/vector" create vectors by parallel versus nested iteration over sequences. The following is Racket code for the Haskell list comprehension examples.

> (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))

In Python we could do as follows:

# 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)]

XQuery and XPath

Like the original NPL use, these are fundamentally database access languages.

This makes the comprehension concept more important, because it is computationally infeasible to retrieve the entire list and operate on it (the initial 'entire list' may be an entire XML database).

In XPath, the expression:

 /library/book//paragraph[@style='first-in-chapter']

is conceptually evaluated as a series of "steps" where each step produces a list and the next step applies a filter function to each element in the previous step's output.[3]

In XQuery, full XPath is available, but FLWOR statements are also used, which is a more powerful comprehension construct.[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>

Here the XPath //book is evaluated to create a sequence (aka list); the where clause is a functional "filter", the order by sorts the result, and the <shortBook>...</shortBook> XML snippet is actually an anonymous function that builds/transforms XML for each element in the sequence using the 'map' approach found in other functional languages.

So, in another functional language the above FLWOR statement may be implemented like this:

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

LINQ in C#

C# 3.0 has a group of related features called LINQ, which defines a set of query operators for manipulating object enumerations.

var s = Enumerable.Range(0, 100).Where(x => x*x > 3).Select(x => x*2);

It also offers an alternative comprehension syntax, reminiscent of SQL:

var s = from x in Enumerable.Range(0, 100) where x*x > 3 select x*2;

LINQ provides a capability over typical List Comprehension implementations. When the root object of the comprehension implements the IQueryable interface, rather than just executing the chained methods of the comprehension, the entire sequence of commands are converted into an Abstract Syntax Tree (AST) object, which is passed to the IQueryable object to interpret and execute.

This allows, amongst other things, for the IQueryable to

C++

C++ does not have any language features directly supporting list comprehensions but operator overloading (e.g., overloading |, >>, >>=) has been used successfully to provide expressive syntax for "embedded" query DSLs. Alternatively, list comprehensions can be constructed using the erase-remove idiom to select elements in a container and the STL algorithm for_each to transform them.

#include <algorithm>
#include <list>

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
}

There is some effort in providing C++ with list-comprehension constructs/syntax similar to the set builder notation.

LEESA provides >> for X-Path's / separator. Interestingly, X-Path's // separator that "skips" intermediate nodes in the tree is implemented in LEESA using what's known as Strategic Programming. In the example below, catalog_, book_, author_, and name_ are instances of catalog, book, author, and name classes, respectively.

// 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_);

See also

Notes and references

  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.
  4. ↑ "XQuery FLWOR Expressions". W3Schools.
  5. ↑ "Single-variable List Comprehension in C++ using Preprocessor Macros".
  6. ↑ "C++ list comprehensions".
  7. ↑ "Language for Embedded Query and Traversal (LEESA)".

Haskell

OCaml

Python

Common Lisp

Clojure

Axiom

External links

This article is issued from Wikipedia - version of the 9/22/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.