How to get pairs of elements from infinite lists in Haskell?

Question

a common problem

I have an infinite list, and I want to select a pair (a,b) , where a and b both from the list, and the pair satisfies some property. Using lists doesn't seem to work because the list is endless.

Specific instance

I am trying to find a pair of primes that make up a certain number (see this code issue for codes ).

I have defined primes , which is an endless list of primes, but when I naively try to select a pair of primes as shown below, the process never ends.

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

I understand that this is because the list of primes [(2,2), (2,3), (2,5)...] . Basically, a becomes the first element of primes , and then when b exhausted, it will move to the second element. Since primes infinite, it will never be exhausted!

Is there an easy way to use lists to solve this problem? Otherwise, is there a simple solution?

Answer 1

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

That would be much 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 most enjoyable way is to use the monad width of the first list . Since comprehension of lists can be thought of as just monad syntactic sugar (just like do ), which allows you to make it look like what you have:

 {-# 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 is a pity that you did not make a decision @leftaroundabout. It has a lot more. For example, another solution has a heuristic "all numbers must be less than n" (what do you do for problems when you do not have this heuristic?) And a few more steps that make it difficult to prove that this is actually a solution to the goldbach problem - For example, can you demonstrate that when enumerating primes, they are going to collect all useful pairs of primes? (This is true, but can you demonstrate it? This is the weakness of this decision)

So, here I will show how you can create a @leftaroundabout solution without saying the word “monad”.

The problem with understanding the list that you created first is that it is looking for a "depth-first" solution - take one item from the first list, and then try all the combinations with that item. However, if there are an infinite number of combinations, you can never list any pairs with the second element from the first list. Here we need to talk about breadth first.

Let's say gen is a solution generator:

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

Say gens is a generator of generating solutions:

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

All we need to do now is list the solutions, taking one solution from each generator at a time. Keep in mind that if the number of generators is infinite, we cannot just take them one by one - this way we can never get a second solution from the first generator, so we need to somehow “direct” them:

 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 

What is it.

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

Now, to efficiency. All this is in gens and gen . Add the gens condition to takeWhile ((<=n) . (x+)) and it will work even if the Goldbach hypothesis is wrong (but you don't need to add it at all). Add the condition to the gen in takeWhile (<=x) , and you will only list pairs where the first number is greater than the other.

Answer 4

or lambda, providing an endless list of pairs from an endless list of any

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

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