list comprehension


list comprehension

(functional programming)An expression in a functional language denoting the results of some operation on (selected)elements of one or more lists. An example in Haskell:

[ (x,y) | x
This returns all pairs of numbers (x,y) where x and y areelements of the list 1, 2, ..., 10, y <= x and their sum isless than 10.

A list comprehension is simply "syntactic sugar" for acombination of applications of the functions, concat, map andfilter. For instance the above example could be written:

filter p (concat (map (\\ x -> map (\\ y -> (x,y))[1..x]) [1..6]))wherep (x,y) = x+y < 10

According to a note by Rishiyur Nikhil ,(August 1992), the term itself seems to have been coined byPhil Wadler circa 1983-5, although the programming constructitself goes back much further (most likely Jack Schwartz andthe SETL language).

The term "list comprehension" appears in the references below.

The earliest reference to the notation is in Rod Burstall andJohn Darlington's description of their language, NPL.

David Turner subsequently adopted this notation in hislanguages SASL, KRC and Miranda, where he has called them "ZF expressions", set abstractions and list abstractions (in his1985 FPCA paper [Miranda: A Non-Strict Functional Languagewith Polymorphic Types]).

["The OL Manual" Philip Wadler, Quentin Miller and MartinRaskovsky, probably 1983-1985].

["How to Replace Failure by a List of Successes" FPCASeptember 1985, Nancy, France, pp. 113-146].