0094: Email Tutorials – FP 7 List Comprehensions

FP7 Graham Hutton Video

Table of Contents

1. What a “comprehension” means (sets vs lists)
2. The basic syntax of a list comprehension
3. Generators: “x is drawn from …”
4. Multiple generators and ordering (nested-loop intuition)
5. Dependent generators (later generators depend on earlier ones)
6. Guards (filters): keep some values, throw away others
7. Example: concat (flatten a list of lists)
8. Example: primes (factors, prime, primes) and why laziness helps
9. zip: pairing two lists element-by-element
10. Useful patterns with zip: pairs, sorted, positions
11. String comprehensions (strings are lists of characters) + count
12. Exercises: Pythagorean triples, perfect numbers, scalar product
13. Glossary

1. What a “comprehension” means (sets vs lists)

In mathematics, you may have seen set comprehensions like:

• “the set of all (x^2) such that (x) is in ({1..5})”

The same idea exists in Haskell, but for lists.

The big difference is:

• Sets don’t care about order and duplicates (membership matters, not position or repetition).
• Lists do care about order and duplicates (position and repetition matter).

So in a list, [1,4,9,16,25] is different from [25,16,9,4,1], and [1,1,4] is different from [1,4].

2. The basic syntax of a list comprehension

A list comprehension has this shape:

[ outputExpression | qualifiers ]

Think of it as:

“Build a new list by producing outputExpression for every choice allowed by qualifiers.”

Qualifiers are usually:

• generators (produce values), and
• guards (filter values).

3. Generators: “x is drawn from …”

A generator looks like this:

x <- [1..5]

Read it as:

“x is drawn from the list 1 to 5.”

Example (square every number from 1 to 5):

squares :: [Int]
squares = [x^2 | x <- [1..5]]
-- result: [1,4,9,16,25]

Here’s what’s happening, step-by-step:

1. Take each x from [1..5] one at a time.
2. Compute x^2.
3. Collect results into a new list.

4. Multiple generators and ordering (nested-loop intuition)

You can use multiple generators, separated by commas:

[(x,y) | x <- [1..3], y <- [4..5]]

This produces all combinations of x from [1..3] with y from [4..5]:

-- result:
-- [(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]

Why does order change when you swap generators?

If you swap them:

[(x,y) | y <- [4..5], x <- [1..3]]

you get the same pairs but in a different order:

-- result:
-- [(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]

A reliable mental model is:

Multiple generators behave like nested loops. The last generator changes fastest (inner loop).

So in y <- [4..5], x <- [1..3], x is the “inner loop”, so it runs through 1..3 for each fixed y.

5. Dependent generators (later generators depend on earlier ones)

A dependent generator means a later generator uses a variable introduced earlier:

[(x,y) | x <- [1..3], y <- [x..3]]

Read it as:

• Pick x from 1 to 3
• Then pick y from x to 3 (so the range depends on x)

Result:

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

This is a clean way to express constraints like “(y \ge x)” without extra filtering.

6. Guards (filters): keep some values, throw away others

A guard is a boolean condition inside the qualifiers. If it’s false, the value is discarded.

Example: keep only even numbers from 1 to 10:

evens :: [Int]
evens = [x | x <- [1..10], even x]
-- [2,4,6,8,10]

Read it as:

“The list of all x such that x is drawn from [1..10] and x is even.”

So:

• generators produce candidates
• guards remove unwanted candidates

7. Example: concat (flatten a list of lists)

concat takes a list of lists and smashes them into one long list.

Example:

concat [[1,2,3],[4,5],[6]]
-- [1,2,3,4,5,6]

A list-comprehension definition:

concat' :: [[a]] -> [a]
concat' xss = [x | xs <- xss, x <- xs]

Explanation:

1. Outer generator: xs <- xss picks each inner list.
2. Inner generator: x <- xs picks each element from that inner list.
3. Output expression is just x, so you collect every element in order.

8. Example: primes (factors, prime, primes) and why laziness helps

8.1 Factors (divisors)

A helper function: all numbers that divide n with remainder 0.

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

• x <- [1..n] tries every candidate divisor
• n mod x == 0 keeps only divisors

Example:

factors 15
-- [1,3,5,15]

8.2 Prime test

A positive integer is prime if its only factors are [1, n].

prime :: Int -> Bool
prime n = factors n == [1,n]

This looks “slow”, but Haskell’s lazy evaluation can stop early when it already knows the answer in many cases (you’ll see more of this idea when studying laziness). The lecture specifically motivates this point and later contrasts it with a sieve-based approach. ([youtube.com][1])

8.3 All primes up to a limit

primes :: Int -> [Int]
primes n = [x | x <- [2..n], prime x]

9. zip: pairing two lists element-by-element

zip turns two lists into a list of pairs, matching corresponding positions:

zip ['a','b','c'] [1,2,3,4]
-- [('a',1),('b',2),('c',3)]

It stops when the shorter list ends.

This becomes a powerful helper for comprehensions because it lets you “attach extra information” (like indices) to each element.

10. Useful patterns with zip: pairs, sorted, positions

10.1 Adjacent pairs

pairs :: [a] -> [(a,a)]
pairs xs = zip xs (tail xs)

Example:

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

10.2 Check if a list is sorted

A list is sorted if every adjacent pair is in order.

sorted :: Ord a => [a] -> Bool
sorted xs = and [x <= y | (x,y) <- pairs xs]

Explanation:

1. pairs xs gives adjacent pairs.
2. The comprehension tests x <= y for each pair.
3. and returns True only if all are True.

10.3 Find positions (indices) of a value in a list

We typically count indices from 0.

positions :: Eq a => a -> [a] -> [Int]
positions x xs = [i | (x', i) <- zip xs [0..], x == x']

Explanation:

1. zip xs [0..] pairs each element with its index.
2. Guard x == x' keeps only matching elements.
3. Output i collects only the indices.

Example:

positions 0 [1,0,0,1,0,1,1,0]
-- [1,2,4,7]

11. String comprehensions (strings are lists of characters) + count

In Haskell, a String is just [Char]. That means list functions and comprehensions work on strings too.

Count how many times a character appears:

count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x == x']

Example:

count 's' "Mississippi"
-- 4

This style is “Haskell-ish”: build a filtered list, then take its length, instead of manually incrementing a counter.

12. Exercises (with clear starter solutions)

12.1 Pythagorean triples

A triple (x,y,z) is Pythagorean if:

x^2 + y^2 == z^2

A straightforward comprehension (range 1..n):

pyths :: Int -> [(Int,Int,Int)]
pyths n =
  [(x,y,z) |
    x <- [1..n],
    y <- [1..n],
    z <- [1..n],
    x^2 + y^2 == z^2]

Beginner tip: this is correct but can generate duplicates like (3,4,5) and (4,3,5). Later you can refine it with constraints like x <= y.

12.2 Perfect numbers

A number is perfect if it equals the sum of its factors excluding itself.

Helper:

perfect :: Int -> Bool
perfect n = sum (init (factors n)) == n

Then list all perfect numbers up to n:

perfects :: Int -> [Int]
perfects n = [x | x <- [1..n], perfect x]

12.3 Scalar product

The scalar product multiplies corresponding elements and sums:

scalarproduct :: [Int] -> [Int] -> Int
scalarproduct xs ys = sum [x*y | (x,y) <- zip xs ys]

This is a classic “zip + comprehension” pattern.

13. Glossary of terms

List comprehension: A compact syntax to build a new list from existing lists using generators and guards.

Set comprehension: The mathematical “set-builder” notation for constructing sets from rules.

Generator (x <- xs): A qualifier that produces values by drawing elements from a list.

Guard (condition): A qualifier that filters values; only keeps items where the condition is True.

Qualifier: Anything that appears after the | in a comprehension (generators, guards, etc.).

Cartesian product: All pairs (a,b) formed by choosing a from one collection and b from another.

Dependent generator: A generator whose list depends on earlier variables (e.g., y <- [x..3]).

Polymorphic: Works for many types (e.g., concat' :: [[a]] -> [a] works for any a).

Curried function: A function that takes arguments one at a time (e.g., positions :: Eq a => a -> [a] -> [Int]).

Type constraint (Eq a, Ord a): A requirement that a type supports certain operations (equality for Eq, ordering for Ord).

Lazy evaluation: Haskell’s evaluation strategy that avoids computing results until needed (important for performance and infinite lists). ([youtube.com][1])

Infinite list ([0..]): A list with no end; works in Haskell because of laziness.

Buy Book

Quizz & Progress Badge NFT