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

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 2

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