创建无限惰性列表的问题

Question

我用 F# 完成了第七个欧拉问题*，但对我的成绩并不完全满意执行。在函数 primes 中，我创建了一个序列，我估计它会包含第 10,001 个素数。当我尝试使用 Seq.initInfinite 延迟生成候选素数时，我的代码在抛出内存不足异常之前挂起。

有人可以建议我用延迟生成的序列替换文字序列吗？一旦找到所需的素数，该序列就会短路？

let isPrime n =
    let bound = int (sqrt (float n))
         seq {2 .. bound} |> Seq.forall (fun x -> n % x <> 0)

let primeAsync n =
    async { return (n, isPrime n)}  

let primes =
    {1..1000000}
         |> Seq.map primeAsync
         |> Async.Parallel
         |> Async.RunSynchronously
         |> Array.filter snd
         |> Array.map fst
         |> Array.mapi (fun i el -> (i, el))    
         |> Array.find (fun (fst, snd) -> fst = 10001)

primes

*"By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10,001st prime number?"

Answer 1

我认为 Async.RunSynchronously 的问题 is/was 不是懒惰的，并试图评估整个无限序列。尽管对此有更好的解决方案，但您的算法足够快，因此您甚至不需要并行化；这非常有效：

open System

let isPrime n =
    let bound = n |> float |> sqrt |> int
    seq {2 .. bound} |> Seq.forall (fun x -> n % x <> 0)

let prime =   
   Seq.initInfinite ((+) 2)
      |> Seq.filter isPrime
      |> Seq.skip 10000
      |> Seq.head

Answer 2

将序列输入 Async.Parallel 后立即得到 'reified'。如果要最小化内存消耗，运行串行计算或将其拆分为惰性块，每个块中的元素运行并行。

创建无限惰性列表的问题

Problems Creating an Infinite Lazy List

f#

c#-to-f#