List comprehension

List comprehension #

Pure functional programming does not admit loops.

In particular, this is the case of Haskell. So iteration in Haskell is primarily achieved via recursive functions.

Besides, Haskell provides an alternative syntax for a limited form of iteration, called list comprehensions.

List comprehensions are also available in Python (with a slightly different syntax) since the release of Python 2 (in 2000).

Syntax #

We have already seen set comprehensions.

Haskell provides a similar notion for lists.

Example. If xs is a list of numbers, then we can write

 [x^2 | x <- xs, x >= 5]

This expression evaluates to the list of all x^2 such that x is in xs and x >= 5.

Terminology. In the example above, the expression x <- xs is called a generator.

A list comprehension may have several generators.

Example. The following list comprehension has two generators:

[x + y | x <- xs, y <- ys]

This expression evaluates to the list of all x + y such that x is in xs and y is in ys.

Evaluation #

Warning. For a list (as opposed to set) comprehension:

  • the order of the output list reflects the order of the initial list(s),
  • the output list may contain duplicates.

Examples.

  • [x^2 | x <- [3,5,2]] evaluates to [9,25,4]
  • [x^2 | x <- [3,5,2], x < 5] evaluates to [9,4]
  • [x^2 | x <- [-3,3,3]] evaluates to [9,9,9]
  • [x + y | x <- [3,5,2], y <- [2,3]] evaluates to [5,6,7,8,4,5]

The function sum maps a list of numbers to their sum. For instance, sum [2,3,6] evaluates to 11.

What does the following function do?

myFunction :: [Int] -> Int
myFunction xs = sum [1 | x <- xs]

It maps a list to its length.

What does the following function do?

myFunction :: [[Int]] -> [Int]
myFunction xss = [x | xs <- xss, x <- xs]

It concatenates the inner lists from a list of lists.

For instance

myFunction [[1,3], [2,5], [1,3,4]] evaluates to [1,3,2,5,1,3,4]

Implement the function

discard :: Int -> [Int] -> [Int]

such that discard x xs is the list identical to xs, but where all occurrences of x have been discarded.

For instance, discard 3 [1,3,2,3] should evaluate to [1,2].

discard :: Int -> [Int] -> [Int]
discard x xs = [y | y <- xs, y /= x]

Pattern matching #

The left-hand side of a generator can be a pattern.

Example. The expression

[ x | (x, _) <- [("Bolzano", 39100), ("Merano", 39012)] ]

evaluates to

["Bolzano", "Merano"]

Write a function firstsIfSecPos that maps a list of pairs of integers to a list that consists of the first element of each pair, if the second element is $\ge 0$.

For instance,

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

should evaluate to

[3,-3,1]

firstsIfSecPos :: [(Integer, Integer)] -> [Integer]
firstsIfSecPos ps = [x | (x, y) <- ps, y >= 0]