Haskell - > F＃：特纳的筛子 [英] Haskell --> F#: Turner's Sieve

问题描述

当我偶然发现一种改良版的Eratosthenes Sieve称为Euler's Sieve时，我正在阅读不同的筛选算法。根据维基百科，有一个在Haskell中实现了一个稍微不同的想法版本（称为Turner's Sieve）。

现在我正试图理解代码片段究竟做了什么，我已经得到了它，但现在我想将代码翻译成F＃并且真的不知道从哪里开始。我主要关心的是，似乎没有一个功能来减去两个序列。

以下是代码：

  import Data.OrdList（minus）
 $ b $ primes = euler [2 ..] 
 euler（p：xs）= p： euler（xs`minus` map（* p）（p：xs））
  

在F＃中实现？它甚至有可能吗？

解决方案

如果你想计算诸如Haskell这样的无限列表的合并/差异，LazyList类型（在F＃动力装置里面找到的）想起来。

它使得代码非常繁琐，如下面的翻译所示：

  #rFSharp.PowerPack.dll
 
 //一个懒惰的数字流，从x 
开始让rec numsFrom x = LazyList.consDelayed x（fun（） - > numsFrom （x + 1））
 
 //从L1中减去L2，其中L1和L2都是排序的（！）懒列表
 let rec lazyDiff L1 L2 = 
匹配L1， L2与
 |当x1 时，LazyList.Cons（x1，xs1），LazyList.Cons（x2，xs2） 
 LazyList.consDelayed x1（fun（） - > lazyDiff xs1 L2）
 |当x1 = x2-> LazyList.Cons（x1，xs1），LazyList.Cons（x2，xs2） 
 lazyDiff xs1 L2 
 |当x1> x2  - >时，LazyList.Cons（x1，xs1），LazyList.Cons（x2，xs2） 
 lazyDiff L1 xs2 
 | _  - >失败不应该出现无限列表！ 
 
让rec euler =函数
 | LazyList.Cons（p，xs）为LL  - > 
 let remaining = lazyDiff xs（LazyList.map（（*）p）LL）
 LazyList.consDelayed p（fun（） - > euler剩余）
 | _  - >失败应该是无限的无限名单！ 
 
让primes = euler（numsFrom 2）
  

with

 >素数|> 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 即使我们知道计算中的所有列表都是（无限）无限的，条款也可以防止编译器抱怨不完整的匹配。

I was reading on different sieving algorithms when I stumbled upon a kind of improved version of the Sieve of Eratosthenes called Euler's Sieve. According to Wikipedia there is an implementation of an slightly different version of the idea (called Turner's Sieve) in Haskell.

Now I am trying to understand what exactly the code snippet given does and I think I've got it but now I wanted to translate the code into F# and have really no idea where to start. My main concern is that there doesn't seem to be a function to "substract" two sequences.

Here's the code:

import Data.OrdList (minus)

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

How would this be implemented in F#? Is it even possible?

解决方案

If you want to calculate things like merges/differences of infinite lists like Haskell does, the LazyList type (found inside the F# power pack) springs to mind.

It makes for very verbose code, like the translation below:

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

Note that I added two failwith clauses to keep the compiler from complaining about an incomplete match, even if we know that all lists in the calculation are (lazily) infinite.

这篇关于Haskell - > F＃：特纳的筛子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！