如何从Haskell中的无限列表中获取元素对？

Question

一般问题

我有一个无限的列表,我想选择一对(a,b),其中a和b两个来自列表,该对满足一些属性.使用列表推导似乎不起作用,因为列表是无限的.

具体实例

我试图找到一对加起来给定数字的素数(参见此代码高尔夫问题).

我已定义primes,这是一个无限的素数列表,但是当我天真地尝试选择如下所示的一对素数时,该过程永远不会终止.

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

我意识到这是因为生成的素数列表是[(2,2), (2,3), (2,5)...].基本上,a正在成为第一个元素primes,然后,一旦b用尽,它将移动到第二个元素.因为primes是无限的,它永远不会用尽!

有没有一种简单的方法可以使用列表推导来解决这个问题？如果做不到的话,有一个简单的解决方案吗？

Answer 1

最好的方法是使用广度优先列表monad.由于列表内涵可以被视为只是单子语法糖(很像do),它允许你使它看起来正是像你现在已经是什么:

{-# 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]

不过，这会快很多。

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