A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical set-builder notation (set comprehension) as distinct from the use of map and filter functions.

Case study

List all right triangles that have integers for all sides and all sides equal to or smaller than 10 has a perimeter of 24?

Haskell solution

Before we continue, please, read the Set Builder Notation article.

As you know, in functional programming we either describing a problem than writing a solution. Let’s describe our problem using Set Builder Notation taking into consideration that side b isn’t larger than the hypothenuse and that side a isn’t larger than side b:

\[S = \{(a, b, c)\ |\\\ a \in \mathbb{N} \ and\ b \in \mathbb{N}\ and\ c \in \mathbb{N},\ a \in [1..10]\ and\ b \in [1..a]\ and\ c \in [1..b], \ \\{a}^{2}+{b}^{2}={c}^{2}, a+b+c=24\}\]
Expression Meaning
\((a, b, c)\) Output expression or output function. A tuple which contains triangle sides
\(\ a \in \mathbb{N}\ and\ b \in \mathbb{N}\ and\ c \in \mathbb{N},\\\ a \in [1..10]\ and\ b \in [1..a]\ and\ c \in [1..b]\) Input set. Builds [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] set from \(\mathbb{N}\) - natural numbers set.
\(\ {a}^{2}+{b}^{2}={c}^{2}, a+b+c=24\) Predicate. Satisfies when coma-separated parts return true. (and logic)

Lets do nothing, but translate it to Haskell, using List Comprehension syntax and we will have a ready solution.

ghci> let rightTriangles = [ (a,b,c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2, a+b+c == 24]
ghci> rightTriangles 
[(6,8,10)]

BTW, I remember that “equation system solution” exists, but we are doing programming here ;)

Warmup

Let’s imagine, that we need to create the list of even squares of Integers each of which is less then 100.

Set builder notation solution:

\[S = \{x^2 |\ \exists n : x \in \mathbb{N}, x < 100, x = 2n\}\]

Haskell solution:

let xs = let xs = [x*x | x <- [1..100], even x]

Swift solution

(1...100).map { $0*$0 }.filter { $0 % 2 == 0 }
Expression Meaning
$0*$0 Output function. map applies it to each element of the set.
(1...100) Input set
$0 % 2 == 0` Predicate

Now we know all the basics. It’s time to crack the Triangles problem.

Solution

Solution should return the Array of all possible triangles, satysfing the problem conditions. Each triangle is represented with triple (in Haskel - triple is three element tuple)

Let’s build the set of existing triangles with sides lengths 1..10

let triangles = (1...10).map { a in
  (1...10).map { b in
    (1...10).map { c in
      // Output function returns (Int, Int, Int) tuple
      return (a, b, c)
    }
  }
}

print(triangles)
// Prints
> [[[(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 1, 5), (1, 1, 6), (1, 1, 7), (1, 1, 8), (1, 1, 9), (1, 1, 10)], [(1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 2, 7), (1, 2, 8), (1, 2, 9), (1, 2, 10)], [(1, 3, 1), (1, 3, 2), (1, 3, 3), (1, 3, 4), (1, 3, 5),...

The result contains some extra brackets (which is correct), so we better rewrite it using flatMap:

let triangles = (1...10).flatMap { a in
    (1...10).flatMap { b in
        (1...10).compactMap { c in
            return (a, b, c)
        }
    }
}

print(triangles)
// Prints
> [(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 1, 5), (1, 1, 6), (1, 1, 7), (1, 1, 8), (1, 1, 9), (1, 1, 10), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 2, 7), (1, 2, 8), (1, 2, 9), (1, 2, 10), (1, 3, 1), (1, 3, 2), (1, 3, 3), (1, 3, 4), (1, 3, 5), (1, 3, 6),...

Output now is much better. We have the Array of (Int, Int, Int), or, another word, we built needed set of needed triangles. The only thing we should do is to add the Predicate.

let triangles = (1...10).flatMap { a in
    (1...10).flatMap { b in
        (1...10).compactMap { c in
            return (a, b, c)
        }
    }
    }.filter { tr in
        let isRight = tr.0 * tr.0 + tr.1 * tr.1 == tr.2 * tr.2
        let pSatisfies = tr.0 + tr.1 + tr.2 == 24
        return isRight && pSatisfies
}
print(triangles)

// Output
> [(6, 8, 10), (8, 6, 10)]

Conclusion

I made the simple problem complex, wrote some weird code which could be ten times simpler. But functional programming is not just a monad usage. Functional programming is the way, where math and coding go together. It is elegant and beautiful. This article was not a programming use case. It is an attempt to describe different approach to problem solution.

Further reading