2

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Rumen Hristov
  • 867
  • 2
  • 13
  • 29
  • possible duplicate of [How to have multiple infinite ranges in list comprehensions?](http://stackoverflow.com/questions/15510916/how-to-have-multiple-infinite-ranges-in-list-comprehensions) – nemo Nov 16 '14 at 12:47
  • see also [Haskell- Two lists into a list of tuples](http://stackoverflow.com/questions/15792912/haskell-two-lists-into-a-list-of-tuples), [cartesian product of infinite lists haskell](http://stackoverflow.com/questions/20516402/cartesian-product-of-infinite-lists-haskell), and [also this answer](http://stackoverflow.com/questions/759554/how-to-express-2n3m1n-m%E2%88%88n-in-list-comprehension-form-n-is-the-set-of-nat/762806#762806). – Will Ness Nov 16 '14 at 13:31

3 Answers3

3

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).

Will Ness
  • 70,110
  • 9
  • 98
  • 181
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;
            }
        }
    }
}
ThreeFx
  • 7,250
  • 1
  • 27
  • 51
  • I know how the list looks in Java/C++. I very well know that it is a 3 nested loops structure. I know that it is an infinite loop, but that's the point! If I put an end condition on c, b or a, it will miss many possible combinations. The point is that it needs to be able to terminate as soon as it finds if my tuple is indeed a pythagorean triple. – Rumen Hristov Nov 16 '14 at 11:21
  • @RumenHristov I added a tweaked version, I'll leave the rest for anybody else who stumbles upon the same problem with less knowledge ;) – ThreeFx Nov 16 '14 at 11:26
  • This does Not even work! Yes, it makes the list terminate, but the logic is completely wrong. – Rumen Hristov Nov 16 '14 at 11:36
  • @RumenHristov Well your example works for me, do you have any example which does not work? – ThreeFx Nov 16 '14 at 11:39
  • Run this code. You completely removed my test-condition at the end of the comprehension so now it runs, but it outputs completely wrong numbers. It just iterates over the bounds in each generator and adds them in a tupple. it goes (2, 3..., 4...), then goes to (3, 4..., 5...), (4, 5..., 6...) etc. If my example works then it is by coincidence. Totally not because of proper logic, though. I don't mean to be negative here, just saying. – Rumen Hristov Nov 16 '14 at 11:44
  • @RumenHristov No, try running the list without the constraint for pythagorean triples added. It gives you: ``[(2,3,3),(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),(2,3,13),(2,4,3),(2,4,4),(2,4,5),(2,4,6),(2,4,7),(2,4,8),(2,4,9),(2,4,10),(2,4,11)..]``, which not only contains every possible combination but is also more efficient than the previous implementation. – ThreeFx Nov 16 '14 at 11:49
  • But why would you take my contraint out!? That's the very point of the problem! It is only supposed to generate the pythagorean triples!!! And then every time it generates a new tuple, it must check to see if it is the same as the one I've entered(essentially, checking to see if my value is contained in the list of pythagorean triples). – Rumen Hristov Nov 16 '14 at 11:52
  • @RumenHristov Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/65029/discussion-between-threefx-and-rumen-hristov). – ThreeFx Nov 16 '14 at 11:52
1

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.

BluePeppers
  • 1,603
  • 14
  • 12