Haskell --> F#：特纳筛

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

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

这是代码：

import Data.OrdList (minus)

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

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

如果您想像 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即使我们知道计算中的所有列表都是（懒惰地）无限的，也可以防止编译器抱怨不完整的匹配。