snippetMinor
Is List comprehension equivalent to composition of filter and map?
Viewed 0 times
comprehensionmapequivalentfilterandlistcomposition
Problem
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:
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!
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!
Solution
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.
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.
Context
StackExchange Computer Science Q#22779, answer score: 3
Revisions (0)
No revisions yet.