Haskell --> F# : Turner's Sieve

Question

当我偶然发现一种称为欧拉筛的改进版的埃拉托色尼筛时，我正在阅读不同的筛分算法。根据Wikipedia在 Haskell 中有一个稍微不同版本的想法(称为 Turner's Sieve)的实现。

现在我试图了解给出的代码片段到底是做什么的，我想我已经明白了，但现在我想将代码翻译成 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# 电源包中找到)就会浮现在脑海中。

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

#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)

和

> 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即使我们知道计算中的所有列表都是(懒惰的)无限的，也可以避免编译器提示不完全匹配的子句。