How to use Haskells laziness when finding right triangles

Question

I'm following the (excellent) Haskell tutorial at http://learnyouahaskell.com/starting-out and am trying out the right triangle example:

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

running this I get, as expected:

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

Now, I'd like to try using infinite lists instead:

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

But when I try it, like:

> take 2 triangles

...the programs just runs and runs with no output. What am I doing wrong? I thought Haskells laziness would cause it to find the two first triangles and then halt?

Answer 1

Well, the laziness isn't the problem here. It's the order in which you're iterating the variables in the list.

Basically what happens is:

1. c is bound to 1
2. b is bound to 1
3. a is bound to 1
4. Equation is checked
5. a is bound to 2
6. Equation is checked
7. a is bound to 3
8. Equation is checked

and it goes on forever.

So the generator keeps on iterating and binding values for a, because it doesn't know that you need to stop and also increment b or c for a change.

So you need to generate tuples in more balanced ways.

You can use, for instance, this method:

triplesN :: Int -> [(Int, Int, Int)]
triplesN n = [(i, j, n - i - j) | i <- [1..n - 2], 
                                  j <- [1..n - i - 1], i>=j, 
                                  let k = n - i - j,   j>=k]

isTriangle (a, b, c) = a^2 == b^2 + c^2

triangles = filter isTriangle $ concatMap triplesN [1..]

tripleN generates all the ordered triples with sum n. By mapping this function over all the natural numbers we actually get the stream of all ordered pairs. And finally, we filter only those triples that are triangles.

By doing:

take 10 triangles

we get:

[(5,4,3),(10,8,6),(13,12,5),(15,12,9),(17,15,8),(20,16,12),(25,24,7),(25,20,15),(26,24,10),(29,21,20)]