Dovetail iteration over infinite lists in Haskell

Question

I want to iterate 2 (or 3) infinite lists and find the "smallest" pair that satisfies a condition, like so:

until pred [(a,b,c) | a<-as, b<-bs, c<-cs]
  where pred (a,b,c) = a*a + b*b == c*c
        as = [1..]
        bs = [1..]
        cs = [1..]

The above wouldn't get very far, as a == b == 1 throughout the run of the program. Is there a nice way to dovetail the problem, e.g. build the infinite sequence [(1,1,1),(1,2,1),(2,1,1),(2,1,2),(2,2,1),(2,2,2),(2,2,3),(2,3,2),..] ?

Bonus: is it possible to generalize to n-tuples?

Answer 1

There's a monad for that, Omega.

Prelude> let as = each [1..]
Prelude> let x = liftA3 (,,) as as as
Prelude> let x' = mfilter (\(a,b,c) -> a*a + b*b == c*c) x
Prelude> take 10 $ runOmega x'
[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15),(12,9,15),(8,15,17),(15,8,17)]

Using it's applicative features, you can generalize to arbitrary tuples:

quadrupels = (,,,) <$> as <*> as <*> as <*> as   -- or call it liftA4

But: this alone does not eliminate duplication, of course. It only gives you proper diagonalization. Maybe you could use monad comprehensions together with an approach like Thomas's, or just another mfilter pass (restricting to b /= c, in this case).

Answer 2

List comprehensions are great (and concise) ways to solve such problems. First, you know you want all combinations of (a,b,c) that might satisfy a^2 + b^2 = c^2 - a helpful observation is that (considering only positive numbers) it will always be the case that a <= c && b <= c.

To generate our list of candidates we can thus say c ranges from 1 to infinity while a and b range from one to c.

[(a,b,c) | c <- [1..], a <- [1..c], b <- [1..c]]

To get to the solution we just need to add your desired equation as a guard:

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

This is inefficient, but the output is correct:

[(3,4,5),(4,3,5),(6,8,10),(8,6,10),(5,12,13),(12,5,13),(9,12,15)...

There are more principled methods than blind testing that can solve this problem.