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

Question

我有一个无限的列表，我想选择一对（a， b），其中a和b都来自列表，并且这对都满足一些属性。使用列表理解似乎不起作用，因为列表是无限的。

我试图找到一对素数，它们加起来等于一个给定的数字（参见下面的代码）。

我定义了素数，这是一个无限的素数列表，但当我天真地尝试选择下面的一对素数时，这个过程永远不会终止。

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

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

有没有一种简单的方法可以使用列表理解来解决这个问题？如果做不到这一点，有没有简单的解决方案？

Answer 1

很遗憾你没有接受@leftaroundabout的解决方案。还有很多。例如，另一个解决方案有一个启发式“所有数字必须小于n”（对于没有这个启发式的问题，你会怎么做？），还有一些其他的步骤使得证明它实际上是哥德巴赫问题的解决方案变得更加困难，例如，你能证明计数素数的方法将把所有有用的素数对放在一起吗？（确实如此，但你能证明吗？这是该解决方案的弱点）

所以在这里，我将展示如何在不使用“monad”这个词的情况下构建@leftaroundabout呈现的解决方案。

最初构建的列表理解的问题是，它会“深度优先”搜索解决方案——从第一个列表中选择一个元素，然后尝试与该元素的所有组合。但是，如果有无限多个组合，则永远无法使用第一个列表中的第二个元素枚举任何对。这就是我们需要讨论“广度优先”寻找解决方案的地方。

假设gen是解决方案的生成器：

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

比如说，gens是解决方案的生成器：

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

我们现在需要做的就是一次从每个生成器中取一个解来枚举解。请注意，如果生成器的数量是无限的，我们不能一个接一个地取它们——这样我们就永远不会从第一个生成器中取第二个解，所以我们需要以某种方式“步进”它们：

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

就这样。

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

现在，讲讲效率。它都在gens和gen中。将条件添加到gens到takeWhile((

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

Answer 3

最好的方法是使用广度优先的单子列表。由于列表理解可以被视为单元组语法糖（很像do），因此可以让它看起来与现在完全一样：

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

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