Haskell List Comprehension - Right Angled Triangles

user_8016568 0
Viewed 122

I'm currently learning Haskell from the Learn You a Haskell for Great Good! book. One of the examples involves creating 3-item tuples representing triangles:

let triangles = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10] ]

We then apply some conditions to the original list comprehension to only create right-angled triangles:

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

Producing result:

ghci> rightTriangles
[(3,4,5),(6,8,10)]

I would have produced this result via:

let rightTriangles = [(a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2, a < b && b < c]

Can anyone explain exactly how the tutorial's right angle code works? Both methods apply the filter to make sure that a < b && b < c but I just can't quite picture exactly what is happening with c <- [1..10], b <- [1..c], a <- [1..b].

I would be supremely grateful if someone could explain what's happening, perhaps with an some kind of illustration if possible. I'm quite new to functional programming and would really like to understand how this works.

Thanks!

list-comprehension functional-programming haskell
1 Answers

Short answer: since b <- [ 1 .. c ] it means that b is always less than or equal to c.

The c <- [1..10], b <- [1..c] and a <- [1..b] are generators. In Python this would look like a for loop, so something like;

data = []
for c in range(1, 11):
    for b in range(1, c+1):
        for a in range(1, b+1):
            if a*a + b*b == c*c:
                data.append((a, b, c))

You can see this as a looping mechanism where the variable c, b, and a are assigned values.

Because it is implemented as b <- [1 .. c], this means that b is less than or equal to c, since that is the maximum bound of the range.

Since that trick is also applied to a <- [ 1 .. b], it means that for all 3-tuples that we consider, a ≤ b ≤ c. Since a ≥ 1, it also means that b ≤ c if it satisfies the constraint a2+b2=c2, it means that a < c and b< c, since if b for example is one, it means that a2 + 1 = b2, the same applies for a. So we know that a < c and b < c.

a can also not be equal to b. If that is the case, it means that 2×a2 = c2, and this thus means that c = √2×a. Since a, b and c are all integral values, that it is not possible that a = b, because then c can not be an integral number, since an integral multiplied with an irrational number is an irrational number.

user_675790
Related