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

functional-programming, haskell, lazy-evaluation

Solution

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

Problem

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?

Original source