List Comprehension – Haskell

Haskell, a purely functional programming language, is well known for its elegant and expressive syntax. One of the features that contributes to its expressiveness is list comprehension. List comprehensions in Haskell provide a concise and powerful way to create and manipulate lists by specifying rules for constructing elements.

In this article, we’ll explore what list comprehensions are, how they work, and some practical examples that demonstrate their flexibility and usefulness in functional programming.

What is List Comprehension?

List comprehension is a concise way to generate lists based on existing lists or data. It’s inspired by set notation in mathematics, and allows you to create a new list by applying operations to each element of an existing list, optionally filtering out some elements.

The basic structure of list comprehension looks like this:

[ expression | pattern <- list, condition ]

Here’s what each part means:

• expression: This defines how each element in the result list is generated.
• pattern <- list: This is the generator that extracts elements from the list.
• condition: (Optional) This is a filter (or predicate) that determines whether or not an element should be included in the final list.

Simple Example of List Comprehension

Let’s start with a basic example: generating a list of squares of numbers from 1 to 5.

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

Explanation:

• x <- [1..5]: x takes each value from the list [1, 2, 3, 4, 5].
• x^2: The expression generates the square of x.
• The result is: [1, 4, 9, 16, 25].
  • 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 16, 5^2 = 25
• In this example, there is no condition

Filtering with List Comprehension

You can add a condition to a list comprehension to filter out unwanted elements. For example, let’s generate the squares of even numbers from 1 to 10:

evenSquares = [x^2 | x <- [1..10], even x]
-- Result: [4, 16, 36, 64, 100]

Explanation:

• x <- [1..10]: x takes values from 1 to 10.
• even x: The condition ensures that only even numbers are considered.
• x^2: For each even number, x^2 is calculated.
• The result is: [4, 16, 36, 64, 100].

In this case, only even values from the list [1..10] are squared.

Multiple Generators in List Comprehension

List comprehensions can also have multiple generators. This allows you to produce all combinations of elements from two or more lists.

For example, let’s create pairs of numbers from two lists:

pairs = [(x, y) | x <- [1, 2, 3], y <- [4, 5]]
-- Result: [(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)]

Explanation:

• x <- [1, 2, 3]: x takes values from the first list.
• y <- [4, 5]: y takes values from the second list.
• (x, y): Each combination of x and y is paired as a tuple.
• The result is: [(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)].

Nested List Comprehension

Haskell allows for nested list comprehensions, meaning you can include list comprehensions inside other list comprehensions.

Here’s an example of generating a list of lists, where each inner list contains the multiples of a number:

multiples = [[x * y | y <- [1..3]] | x <- [1..3]]
-- Result: [[1, 2, 3], [2, 4, 6], [3, 6, 9]]

Explanation:

• The outer list comprehension runs for each x from [1..3].
• For each x, the inner list comprehension generates a list of x * y for y values from [1..3].
• The result is: [[1, 2, 3], [2, 4, 6], [3, 6, 9]].

List Comprehension with Strings

Since strings in Haskell are just lists of characters ([Char]), you can use list comprehensions to manipulate strings just like any other list.

For example, you can extract all the vowels from a given string:

vowels = [c | c <- "Hello, World!", c `elem` "aeiouAEIOU"]
-- Result: "eoo"

Explanation:

• c <- "Hello, World!": c takes each character from the string.
• c \elem` “aeiouAEIOU”`: The condition filters out characters that are not vowels.
• The result is: "eoo".

Practical Example: Generating Pythagorean Triples

A common example of using list comprehension in Haskell is generating Pythagorean triples. These are sets of integers (a, b, c) such that a² + b² = c².

Here’s how you can generate Pythagorean triples where all numbers are less than or equal to 20:

pythagoreanTriples = [(a, b, c) | a <- [1..20], b <- [a..20], c <- [b..20], a^2 + b^2 == c^2]

Explanation:

• a <- [1..20]: a takes values from 1 to 20.
• b <- [a..20]: b takes values starting from a to avoid duplicate combinations.
• c <- [b..20]: c takes values starting from b for the same reason.
• a^2 + b^2 == c^2: The condition ensures that the triplet (a, b, c) satisfies the Pythagorean theorem.
• The result is: [(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20)].

Infinite Lists and List Comprehension

Since Haskell uses lazy evaluation, you can use list comprehensions to work with infinite lists. For example, you can generate an infinite list of even numbers and take only the first 10:

evens = [x | x <- [1..], even x]
firstTenEvens = take 10 evens

Explanation:

• x <- [1..]: This generates an infinite list starting from 1.
• even x: Only even numbers are kept.
• take 10 evens: Extracts the first 10 even numbers.
• The result is: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20].

Benefits of List Comprehension

• Conciseness: List comprehensions allow you to write code that is both concise and readable. Complex list manipulations can be expressed in a single line.
• Modularity: By separating generators, expressions, and conditions, list comprehensions are highly modular, making it easy to read and modify specific parts of a list comprehension.
• Efficiency: List comprehensions leverage Haskell’s lazy evaluation, which means that they only compute values as needed, making them efficient, especially when working with large or infinite lists.

Conclusion

List comprehension is one of the most powerful and elegant features of Haskell. It allows for a clear and concise way to generate and transform lists, making it a crucial tool for Haskell programmers. Whether you’re generating simple lists, filtering elements, or working with nested and infinite lists, list comprehensions provide a flexible and readable solution for manipulating data in Haskell.

By mastering list comprehension, you’ll be able to write more concise, efficient, and readable Haskell code, tapping into the power of functional programming.