How to use Haskells ribbon to find the right triangles

Question

I follow the (excellent) Haskell tutorial at http://learnyouahaskell.com/starting-out , and I tried an example of a proper triangle:

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

by running this, I get, as expected:

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

Now I would like to try using infinite lists:

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

But when I try to do this, for example:

 > take 2 triangles 

... programs simply start and run without output. What am I doing wrong? I thought Haskels laziness would make him find the first two triangles, and then stop?

Answer 1

Well, laziness is not a problem. This is the order in which you repeat the variables in the list.

Basically the following happens:

• c linked to 1
• b tied to 1
• a is associated with 1
• Equation verified
• a is associated with 2
• Equation verified
• a is associated with 3
• Equation verified

and it goes on forever.

Thus, the generator stores the iteration and binding values ​​for a , because it does not know what you need to stop, and also increase b or c to change.

So, you need to generate tuples in more balanced ways.

You can use, for example, 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 ordered triples with the sum n . By mapping this function over all natural numbers, we actually get a stream of all ordered pairs. And finally, we filter only those triples that are triangles.

Performing:

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

Answer 2

You might be interested in reading the Monad article on combinatorial sigfpe blog searches.

It defines a new monad, called a punishment list or PList, similar to the list monad, but which also has the concept of a penalty for more complex decisions. When you combine PLists, the order in which the results are created is the smallest penalty of the order → the largest penalty.

In your example, the penalty associated with an integer may be equal to the size of an integer, and the penalty associated with a tuple is the sum of the penalties of its elements. Thus, the tuple (3,4,5) has a penalty of 3 + 4 + 5 = 12, and the tuple (5,12,13) has a penalty of 5 + 12 + 13 = 30.

In the monad list, the order of the resulting tuples

 (1,1,1), (1,1,2), (1,1,3), (1,1,4), (1,1,5) ... 

and you will never see a tuple not shaped (1,1,x) . With monad PList, the resulting tuples can be

 (1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,1,3), (1,3,1), (3,1,1), (1,2,2) ... 

with all the "smaller" tuples created before the "big" ones.

For your specific problem, this solution is redundant, but it can be very useful in more complex problems.