哈斯克尔 --> F#：特纳筛

Question

当我偶然发现一种埃拉托色尼筛法的改进版本（称为欧拉筛法）时，我正在阅读不同的筛分算法。根据维基百科有一个在 Haskell 中实现了稍微不同的想法版本（称为特纳筛法）。

现在我试图了解给出的代码片段到底是做什么的，我想我已经明白了，但现在我想将代码转换为 F#，但真的不知道从哪里开始。我主要担心的是，似乎没有一个函数可以“减去”两个序列。

代码如下：

import Data.OrdList (minus)

primes = euler [2..]
euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs))

这将如何在 F# 中实现？有可能吗？

Answer 1

如果您想像 Haskell 那样计算无限列表的合并/差异之类的事情，那么 LazyList 类型（在 F# power pack 中可以找到）就会浮现在脑海中。

它会产生非常冗长的代码，如下面的翻译：

#r "FSharp.PowerPack.dll"

//A lazy stream of numbers, starting from x
let rec numsFrom x = LazyList.consDelayed x (fun () -> numsFrom (x+1))

//subtracts L2 from L1, where L1 and L2 are both sorted(!) lazy lists
let rec lazyDiff L1 L2 =
    match L1,L2 with
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1<x2 ->
            LazyList.consDelayed x1 (fun () -> lazyDiff xs1 L2)
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1=x2 ->
            lazyDiff xs1 L2
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1>x2 ->
            lazyDiff L1 xs2
        | _ -> failwith "Should not occur with infinite lists!"

let rec euler = function
    | LazyList.Cons(p,xs) as LL ->
        let remaining = lazyDiff xs (LazyList.map ((*) p) LL)
        LazyList.consDelayed p (fun () -> euler remaining)
    | _ -> failwith "Should be unpossible with infinite lists!"

let primes = euler (numsFrom 2)

with

> primes |> Seq.take 15 |> Seq.toList;;
val it : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

请注意，我添加了两个 failwith 子句，以防止编译器抱怨不完整的匹配，即使我们知道计算中的所有列表都是 (懒惰地）无限。

Answer 2

您可以使用seq来做到这一点。当你完成减时，欧拉本身与Haskell中的相同。

let rec minus xs ys =
  seq {
    match Seq.isEmpty xs, Seq.isEmpty ys with
    | true,_ | _,true -> yield! xs
    | _ ->
       let x,y = Seq.head xs, Seq.head ys
       let xs',ys' = Seq.skip 1 xs, Seq.skip 1 ys
       match compare x y with
       | 0 -> yield! minus xs' ys'
       | 1 -> yield! minus xs ys'
       | _ -> yield x; yield! minus xs' ys
  }

let rec euler s =
  seq {
    let p = Seq.head s
    yield p
    yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
  }

let primes = Seq.initInfinite ((+) 2) |> euler

Answer 3

对于序列，通过持久化序列你会变得更有竞争力：

let rec euler s =
    seq {
        let s = Seq.cache s
        let p = Seq.head s
        yield p
        yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
    }

Answer 4

首先，必须指出的是，欧拉素数筛并不是“埃拉托斯特尼筛法的改进版本”，因为它的性能在任何意义上都比埃拉托斯特尼筛法的任何版本都要差得多： 关于素数算法的 Haskell Wiki - Euler

接下来，应该说 @cfem 使用 LazyList 的代码是忠实的，尽管您提供的欧拉筛版本的详细翻译，尽管它缺乏根据上面的链接仅筛选奇数的轻微改进。

应该注意的是，实现欧拉筛实际上没有任何意义，因为它比通过试除优化 (TDO) 查找素数更复杂且更慢，因为它只对找到的素数进行除法直到根据以下内容测试素数候选数：Haskell Wiki on Prime Number Algorithms - TDO。

此试除优化 (TDO) 筛选可以使用 LazyList（参考 FSharp.PowerPack.dll）在 F# 中实现为：

let primesTDO() =
  let rec oddprimes =
    let rec oddprimesFrom n =
      if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0)
      then LazyList.consDelayed n (fun() -> oddprimesFrom (n + 2))
      else oddprimesFrom (n + 2)
    LazyList.consDelayed 3 (fun() -> oddprimesFrom 5)
  LazyList.consDelayed 2 (fun () -> oddprimes)

它可以使用与以下形式相同的序列来实现：

let primesTDOS() =
  let rec oddprimes =
    let rec oddprimesFrom n =
      if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0)
      then seq { yield n; yield! oddprimesFrom (n + 2) }
      else oddprimesFrom (n + 2)
    seq { yield 3; yield! (oddprimesFrom 5) } |> Seq.cache
  seq { yield 2; yield! oddprimes }

序列版本比 LazyList 版本稍快，因为它避免了调用时的一些开销，因为 LazyList 基于缓存序列。两者都使用一个内部对象，该对象表示迄今为止找到的素数的缓存副本，在 LazyList 的情况下自动缓存，在序列的情况下由 Seq.cache 自动缓存。两者都可以在大约两秒内找到前 100,000 个素数。

现在，欧拉筛可以进行奇数筛分优化，并使用 LazyList 表示如下，由于知道输入列表参数是无限的，并且比较匹配被简化，因此消除了一种匹配情况，如下好吧，我添加了一个运算符“^”以使代码更具可读性：

let primesE = //uses LazyList's from referenced FSharp.PowerPack.dll version 4.0.0.1
  let inline (^) a ll = LazyList.cons a (LazyList.delayed ll) //a consd function for readability
  let rec eulers xs =
    //subtracts ys from xs, where xs and ys are both sorted(!) infinite lazy lists
    let rec (-) xs ys =
      let x,xs',ys' = LazyList.head xs,LazyList.tail xs,LazyList.tail ys
      match compare x ( LazyList.head ys) with
        | 0 -> xs' - ys' // x == y
        | 1 -> xs - ys' // x > y
        | _ -> x^(fun()->(xs' - ys)) // must be x < y
    let p = LazyList.head xs
    p^(fun() -> (((LazyList.tail xs) - (LazyList.map ((*) p) xs)) |> eulers))
  let rec everyothernumFrom x = x^(fun() -> (everyothernumFrom (x + 2)))
  2^(fun() -> ((everyothernumFrom 3) |> eulers))

但是，必须注意的是，对于 primesTDO 和 primesTDOS，计算第 1899 个素数（16381）的时间分别约为 0.2 和 0.16 秒，而使用这个 primesE 大约需要 2.5 秒，即使对于这么小的范围，欧拉筛的性能也很糟糕，时间是其十倍以上。除了糟糕的性能之外，primeE 甚至无法计算 3000 以内的素数，因为它记录的延迟执行函数数量随着找到的素数的增加而迅速增加，因此内存利用率更差。

请注意，在重复编写代码时必须小心，因为 LazyList 是一个值，并且内置了先前找到的元素的记忆，因此第二次相同的扫描将花费接近零的时间；出于计时目的，最好将 PrimeE 设为 PrimeE() 中的函数，以便每次工作都从头开始。

总之，用包括 F# 在内的任何语言实现的欧拉筛只是一种有趣的智力练习，没有实际用途，因为它比几乎所有其他合理优化的筛要慢得多，而且占用内存要严重得多。