哈斯克尔 -->F#:特纳筛 [英] Haskell --> F#: Turner's Sieve

问题描述

当我偶然发现一种称为 Euler 筛的 Eratosthenes 筛的改进版本时，我正在阅读不同的筛分算法.根据 维基百科，有一个在 Haskell 中实现了略有不同的想法版本(称为特纳筛).

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.

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

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.

代码如下:

import Data.OrdList (minus)

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

这将如何在 F# 中实现?甚至有可能吗?

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

推荐答案

如果您想像 Haskell 那样计算无限列表的合并/差异之类的东西，LazyList 类型(在 F# 电源包中找到)就会浮现在脑海中.

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)

与

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

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.

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