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?
(->) is often called the "function arrow" or "function type constructor", and while it does have some special syntax, there's not that much special about it. It's essentially an infix type operator. Give it two types, and it gives you the type of functions between those types.
The ++ operator is the list concatenation operator which takes two lists as operands and "combines" them into a single list.
From HaskellWiki. Currying is the process of transforming a function that takes multiple arguments in a tuple as its argument, into a function that takes just a single argument and returns another function which accepts further arguments, one by one, that the original function would receive in the rest of that tuple.
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.
You can do it with seq. And as you got minus done, euler itself is same as in Haskell.
let rec minus xs ys =
seq {
match Seq.isEmpty xs, Seq.isEmpty ys with
| true,_ | _,true -> yield! xs
| _ ->
let x,y = Seq.head xs, Seq.head ys
let xs',ys' = Seq.skip 1 xs, Seq.skip 1 ys
match compare x y with
| 0 -> yield! minus xs' ys'
| 1 -> yield! minus xs ys'
| _ -> yield x; yield! minus xs' ys
}
let rec euler s =
seq {
let p = Seq.head s
yield p
yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
}
let primes = Seq.initInfinite ((+) 2) |> euler
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With