Haskell - > F#:特纳的筛子

Question

当我偶然发现一种名为Euler's Sieve的Eratosthenes筛子的改进版本时,我正在阅读不同的筛选算法.根据维基百科,在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#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)

同

> 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子句,以防止编译器抱怨不完整的匹配,即使我们知道计算中的所有列表都是(懒惰)无限的.