How do I get pairs of elements from infinite lists in Haskell?

Question

General Problem

I have an infinite list and I want to select a pair (a,b) where a and b both come from the list and the pair satisfies some property. Using list comprehensions does not seem to work because the list is infinite.

Specific Instance

I am trying to find a pair of primes that add up to a given number (see this code golf problem).

I have defined primes, which is an infinite list of primes, but when I naively attempt to select a pair of primes as below, the process never terminates.

goldbach n = head [(a,b) | a<-primes, b<-primes, a+b==n]

I realize this is because the list of primes being generated is [(2,2), (2,3), (2,5)...]. Basically, a is becoming the first element from primes and then, once b is exhausted, it will move onto the second element. Because primes is infinite, it will never be exhausted!

Is there an easy way to use list comprehensions to solve this problem? Failing that, is there a simple solution?

Answer 1

goldbach n = head [(a,b) | let ps = takeWhile (<n) primes, a<-ps, b<-ps, a+b==n]

This would be a heck of a lot faster though.

goldbach2 n = aux ps (reverse ps) where
    ps = takeWhile (<n) primes
    aux [] _ = []
    aux _ [] = []
    aux (a:as) (b:bs)  
      | a > b = []
      | otherwise = case compare (a+b) n of
        EQ -> (a,b):aux as bs
        LT -> aux as (b:bs)
        GT -> aux (a:as) bs

Answer 2

The nicest way is to use the breadth-first list monad. Since list comprehensions can be seen as just monad syntactic sugar (much like do), that allows you do make it look exactly like what you've now:

{-# LANGUAGE MonadComprehensions #-}
import Control.Monad.Omega

goldbach n = head $ runOmega [(a,b) | a<-ps, b<-ps, a+b==n]
  where ps = each primes

Answer 3

It's a pity you unaccepted @leftaroundabout's solution. It has a lot more to it. For example, the other solution has a heuristic "all numbers must be less than n" (what do you do for problems where you don't have this heuristic?), and a few other steps that make it harder to prove that it actually is a solution to goldbach's problem - e.g. can you demonstrate that way ot enumerating primes is going to put together all useful pairs of primes? (It does, but can you demonstrate it? This is the weakness of that solution)

So here I will show how you can build the solution @leftaroundabout presented, without saying the word "monad".

The problem with the list comprehension you built at first is that it searches the solution "depth-first" - take one element from the first list, then try all combinations with this element. However, if there is a infinite number of combinations, you will never get to enumerate any pairs with the second element from the first list. This is where we need to talk about "breadth-first" search for solutions.

Let's say gen is a generator of solutions:

gen x = map (\y -> (x,y)) -- construct pairs for a given element x

Let's say gens is a generator of generators of solutions:

gens xs ys = map (\x -> gen x ys) xs

All we need to do now, is enumerate solutions by taking one solution from each generator at a time. Mind you, if the number of generators is infinite, we can't just take them one by one - that way we will never get to take the second solution from the first generator, so we need to "step" them somehow:

om xs = f [] [] xs where -- this is your omega enumerating solutions
                         -- from generator of generators
  f [] [] [] = [] -- this is where the pot stops cooking
  f [] gs [] = f gs [] []
  f [] gs (g:gens) = f (g:gs) [] gens -- ok, took one solution from all generators -
                          -- add one generator to the list of generators we enumerate
                          -- next time - this is how we "step" the generators
  f ([]:gs) gs' gens = f gs gs' gens  -- generator eliminator: last solution was taken
                          -- from one generator
  f ((x:xs):gs) gs' gens = x : f gs (xs:gs') gens -- take one solution from the first
                          -- generator, and move the rest of the generator to the list
                          -- for the next iteration

That's it.

> find (\(x,y) -> x+y==190) $ om $ gens primes primes
Just (179,11)

Now, to efficiency. It is all in gens and gen. Add a condition to gens to takeWhile ((<=n) . (x+)), and it will work even if Goldbach's conjecture is wrong (but you don't have to add it at all). Add a condition to gen to takeWhile (<=x), and you will enumerate only the pairs where the first prime is greater than the other.

Answer 4

or a lambda, giving infinite list of pairs from an infinite list of whatever

(\x->let p=(\(a:b:oo)->(a,b):p oo) in p x)

on ghci let p=(\x->let p=(\(a:b:oo)->(a,b):p oo) in p x) take 10 (p [1..])