Infinite list not being terminated after appropriate value is found.

Question

I have written the following function that returns an infinite list of 3-tuple members, (a, b, c) according to the definition of a Pythagorean triples: a^2 + b^2 = c^2. I need to be able to check if a given tuple (a, b, c) is a valid Pythagorean triple. The way I do this is by generating an infinite list of tuples by means of the function and I pass this list to elem along with the 3-tuple I want to check.

However, this does not terminate when it matches my 3-tuple to a member of the infinite list.

Code:

pythagoreanTriples::[(Integer, Integer, Integer)]
pythagoreanTriples = [(a, b, c) | a <- [2..], b <- [a+1..], 
                                  c <- [b+1..], a*a + b*b == c*c ]
main = do
print $ elem (30, 72, 78) (pythagoreanTriples)

I know the logic is correct, because I have tried modifying the above function to produce an finite list and the logic works very nicely:

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

main = do
print $ elem (30, 72, 78) (pythagoreanTriples 100)

However, it must be done with an infinite list. Please suggest to me how I can make it work. Thanks.

Answer 1

Start with your finite code,

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

and simply make it work for any n from 1 and up:

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

(but this produces a lot of duplicates). I'd prefer to first fix the biggest, c value, and then find the a and b such that a < b < c, and the condition holds:

                     = [(a, b, c) | n <- [1..],
                                    c <- [2..n], a <- [2..c-1], 
                                    b <- [a+1..c-1], a*a + b*b == c*c ]

but what do we need that n for, now? We don't:

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

So that

GHCi> take 20 pythagoreanTriples

[(3,4,5),(6,8,10),(5,12,13),(9,12,15),(8,15,17),(12,16,20),(7,24,25),(15,20,25),
(10,24,26),(20,21,29),(18,24,30),(16,30,34),(21,28,35),(12,35,37),(15,36,39),(24
,32,40),(9,40,41),(27,36,45),(14,48,50),(30,40,50)]

(the case a==b is impossible, because sqrt(2) is an irrational number).

Answer 2

The problem lies in how the list is generated. Lets hop in ghci and look how the infinite list looks:

ghci> [(a, b, c) | a <- [2..], b <- [a+1..], c <- [b+1..]]

We get something which looks like this:

[(2,3,4),(2,3,5),(2,3,6),(2,3,7),(2,3,8),(2,3,9),(2,3,10),(2,3,11),(2,3,12),..]

Because you have not specified when to stop iterating through c and to go to b, the above sequence will continue until eternity.

With the constraint added we can see that no items fulfil the constraint because the square root of 13 is not an integer.

If we tweak the conditions a little we have a working infinite list:

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

Now because we have specified when to stop iterating through c the list will advance one iteration in a before continuing in c. Because just adding this constraint to c will not work, we also have to add one to a, otherwise we face the same problem as before.

So we settle on choosing the length of the longer cathete and a maximum bound to the smaller cathete. Based on those constraints, we can now also add one to c.

---

We can do this even faster if we decide to compute c directly and check if it is a square. This would look something like this:

pythagoreanTriples = [(a, b, c) | b <- [3..], a <- [2..b-1], let c = a^2 + b^2, isSquare c]
  where
    isSquare x = round x == (round $ sqrt x) ^ 2

Note that this could be inaccurate due to floating point arithmetic.

---

You can imagine this list comprehension as a nested for-loop:

for (number a = 2; true; a++)
{
    for (number b = a+1; true; b++)
    {
        for (number c = b+1; true; c++)
        {
            if (a^2 + b^2 == c^2)
            {
                add (a, b, c) to a list;
            }
        }
    }
}        

Answer 3

The problem comes with the order of iteration. [(a, b) | a <- [1..100], b <- [1..100]] will first iterate through all b, then all a.

Prelude> [(a, b) | a <- [1..10], b <- [1..10]]
[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(2,10),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(3,10),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(4,10),(5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),(5,9),(5,10),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(6,10),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),(7,9),(7,10),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(8,10),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9),(9,10),(10,1),(10,2),(10,3),(10,4),(10,5),(10,6),(10,7),(10,8),(10,9),(10,10)]

As you can see, b is fully iterated before a increments. However, as you are doing b <- [1..], b never finishes iterating, and a stays as 1 forever.