# Is List comprehension equivalent to composition of filter and map?

Wikipedia says

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.

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

• A variable representing members of an input list.
• An input list (or iterator).
• An optional predicate expression.
• And an output expression producing members of the output list from members of the input iterable that satisfy the predicate.

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

I think a list comprehension can be equivalently converted to combining a filter and a map in the following way:

• "An optional predicate expression." corresponds to a filter

• "an output expression producing members of the output list from members of the input iterable that satisfy the predicate" corresponds to a map

So are list comprehension and combination of filter and map equivalent?

Thanks!

-
This sounds right. – Yuval Filmus Mar 18 '14 at 23:01

Yes. Given any list comprehension, you can always compute the same thing in an equivalent way using map and filter. However, there are some important differences between these two styles of programming.

A list comprehension is a declarative way of specifying what you want. In contrast, using map and filter is an operational specification: it specifies not just what you want, but also specifies exactly how it should be computed. Declarative specifications are arguably nicer, because they let the compiler choose the best way to compute the desired results, and because they let the programmer focus on what they want the computation to return without getting distracted by the details of how it will be computed.

-

## Basic difference

List comprehension and combination of filter and map may be equivalent only in languages with lazy evaluation.

The reason is that, without lazy evaluation, filter and map will want to evaluate the whole lists given as arguments, while comprehensions are built from the start as structure that evaluate on a call by need basis.

Hence, comprehensions can in principle include infinite lists, and some languages allow that (e.g. Python)

Also, evaluating all elements of a list may lead to non terminating programs, if the evaluation of one element (not really needed) does not terminate, while the corresponding comprehension may never be asked to produce that element, and will not prevent termination of the program.

The semantics of the program may also be changed if the computation of a list element produces side-effects. The ccomprehension will produce the side-effects later, if at all, during the execution of the program.

## My interpretation of the wikipedia text

From what I always understood, comprehension means the same as intension, which is itself opposed to extension (wikipedia).

An extensional definition of a set is an actual enumeration of its elements (which works moderately well for infinite ones).

An intensional definition is the usual technique that defines the elements by specifying some property they must have.

The computational counterpart is comprehension, that provides a way of computing the elements, rather than enumerating them explicitly.

Comprehension is in a sense the Curry-Howard counterpart of intension.

The counterpart for extensional sets is a data structure that enumerates the elements explicitly.

Now, one can always define a property by extensionally giving the set of elements that have that property, so that extensional definitions can always be seen as a special case of intensional ones. But that does not seem to be the point of view of wikipedia.

The wikipedia text is not too clear, and could be more explicit (no pun intended)

My feeling is that they do want to exclude lists that are extensional, maybe for typing reasons. It is not supposed to be a specific data-structure, but an object to be used as an iterator , or as a stream possibly (it is very remindful of the literature on coroutines and generators).

Direct use of map and filter with produce extensional lists, data structures actually containing all values.

But similar constructions with the same predicates and functions in comprehensions will produce a non extensional version of the same lists.

Computationally, comprehensions will be naturally evaluated in a call by need mode, which may allow different program organizations. A comprehension need not be finite, depending on how it is used.

Analysis of the various languages that use the concept might confirm, or not, this understanding.

-