Personal tools

List comprehension

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(small explanation because some articles link on it)
 
(Fleshed out stub for list comprehensions)
Line 1: Line 1:
List comprehensions are [[syntactic sugar]] like the following expression:
+
List comprehensions are [[syntactic sugar]] like the expression
 
<haskell>
 
<haskell>
  +
import Data.Char (toUpper)
  +
 
[toUpper c | c <- s]
 
[toUpper c | c <- s]
 
</haskell>
 
</haskell>
  +
where <hask>s :: String</hask> is a string such as <hask>"Hello"</hask>. Strings in Haskell are lists of characters; the generator <hask>c <- s</hask> feeds each character of <hask>s</hask> in turn to the left-hand expression <hask>toUpper c</hask>, building a new list. The result of this list comprehension is <hask>"HELLO"</hask>.
  +
  +
One may have multiple generators, separated by commas, such as
  +
<haskell>
  +
[(i,j) | i <- [1,2], j <- [1..4]]
  +
</haskell>
  +
yielding the result
  +
<haskell>
  +
[(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4)]
  +
</haskell>
  +
Note how each successive generator refines the results of the previous generator. Thus, if the second list is infinite, one will never reach the second element of the first list. For example,
  +
<haskell>
  +
take 10 [ (i,j) | i <- [1,2], j <- [1..]]
  +
</haskell>
  +
yields
  +
<haskell>
  +
[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10)]
  +
</haskell>
  +
In such a situation, a nested sequence of list comprehensions may be appropriate. For example,
  +
<haskell>
  +
take 5 [[ (i,j) | i <- [1,2]] | j <- [1..]]
  +
</haskell>
  +
yields
  +
<haskell>
  +
[[(1,1),(2,1)], [(1,2),(2,2)], [(1,3),(2,3)], [(1,4),(2,4)], [(1,5),(2,5)]]
  +
</haskell>
  +
  +
One can also provide boolean guards. For example,
  +
<haskell>
  +
take 10 [ (i,j) | i <- [1..], j <- [1..i-1], gcd i j == 1 ]
  +
</haskell>
  +
yields
  +
<haskell>
  +
[(2,1),(3,1),(3,2),(4,1),(4,3),(5,1),(5,2),(5,3),(5,4),(6,1)]
  +
</haskell>
  +
  +
Finally, one can also make local let declarations. For example,
  +
<haskell>
  +
take 10 [ (i,j) | i <- [1..], let k = i*i, j <- [1..k]]
  +
</haskell>
  +
yields
  +
<haskell>
  +
[(1,1),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(3,5)]
  +
</haskell>
  +
  +
Here is an example of a nested sequence of list comprehensions, taken from code implementing the [http://en.wikipedia.org/wiki/Sieve_of_Atkin Sieve of Atkin]:
  +
<haskell>
  +
[[[ poly x y
  +
| i <- [0..], let x = m + 60*i, test x y ]
  +
| j <- [0..], let y = n + 60*j ]
  +
| m <- [1..60], n <- [1..60], mod (poly m n) 60 == k ]
  +
</haskell>
  +
The result is a list of infinite lists of infinite lists.
  +
  +
The specification of list comprehensions is given in [http://haskell.org/onlinereport/exps.html#sect3.11 The Haskell 98 Report: 3.11 List Comprehensions].
   
  +
List comprehensions were generalized to monad comprehensions, which became Haskel's <hask>do</hask> notation. The GHC compiler supports parallel list comprehensions as an extension; see [http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#parallel-list-comprehensions GHC User's Guide: 7.3.4. Parallel List Comprehensions].
   
 
[[Category:Glossary]]
 
[[Category:Glossary]]

Revision as of 15:30, 13 July 2007

List comprehensions are syntactic sugar like the expression

import Data.Char (toUpper)
 
[toUpper c | c <- s]
where
s :: String
is a string such as
"Hello"
. Strings in Haskell are lists of characters; the generator
c <- s
feeds each character of
s
in turn to the left-hand expression
toUpper c
, building a new list. The result of this list comprehension is
"HELLO"
.

One may have multiple generators, separated by commas, such as

[(i,j) | i <- [1,2], j <- [1..4]]

yielding the result

[(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4)]

Note how each successive generator refines the results of the previous generator. Thus, if the second list is infinite, one will never reach the second element of the first list. For example,

take 10 [ (i,j) | i <- [1,2], j <- [1..]]

yields

[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10)]

In such a situation, a nested sequence of list comprehensions may be appropriate. For example,

take 5 [[ (i,j) | i <- [1,2]] | j <- [1..]]

yields

[[(1,1),(2,1)], [(1,2),(2,2)], [(1,3),(2,3)], [(1,4),(2,4)], [(1,5),(2,5)]]

One can also provide boolean guards. For example,

take 10 [ (i,j) | i <- [1..], j <- [1..i-1], gcd i j == 1 ]

yields

[(2,1),(3,1),(3,2),(4,1),(4,3),(5,1),(5,2),(5,3),(5,4),(6,1)]

Finally, one can also make local let declarations. For example,

take 10 [ (i,j) | i <- [1..], let k = i*i, j <- [1..k]]

yields

[(1,1),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(3,5)]

Here is an example of a nested sequence of list comprehensions, taken from code implementing the Sieve of Atkin:

[[[ poly x y
    | i <- [0..], let x = m + 60*i, test x y ]
    | j <- [0..], let y = n + 60*j ]
    | m <- [1..60], n <- [1..60], mod (poly m n) 60 == k ]

The result is a list of infinite lists of infinite lists.

The specification of list comprehensions is given in The Haskell 98 Report: 3.11 List Comprehensions.

List comprehensions were generalized to monad comprehensions, which became Haskel's
do
notation. The GHC compiler supports parallel list comprehensions as an extension; see GHC User's Guide: 7.3.4. Parallel List Comprehensions.