hubFS: THE place for F#

I've created the following iterative prime sieve in C#

		static IEnumerable Primes()

		{

			yield return 2;

			Dictionary sieve = new Dictionary();

			for(int i = 3;; i += 2)

			{

				int marker;

				if(!sieve.TryGetValue(i, out marker))

				{				

					yield return i;

					marker = i;

				}

				int step = marker + marker, x = marker + step;

				while(sieve.ContainsKey(x))

					x += step;

				sieve.Add(x, marker);

			}

		}

And now I wonder how do I "translate" it to F# I've found "Seq.unfold" and I guess that's half the answer but the other half I seem to not really get.

Any help greatly appriciated.

Seq.unfold is great if you have a well-defined sequence - e.g., the result of a method call.  For more complex scenarios with 'yield return' you should prefer Sequence Computation Expressions. (http://blogs.msdn.com/dsyme/archive/2007/09/22/some-details-on-f-computation-expressions-aka-monadic-or-workflow-syntax.aspx)

Translated code (a little messily):

#light

open System.Collections.Generic
let primes = 
    seq { 
        // First prime
        yield 2

        let sieve = new Dictionary()
        // Loop through all odd numbers < 1E3
        for i in 3 .. 2 .. 1000 do
            // Check if its in our sieve (if not, its prime)
            let (found, value) = sieve.TryGetValue(i)

            let marker = if not found then i else value
            // Add to sieve
            let _ =
                let step = marker + marker
                let finalX =
                    let initX = marker + step
                    let rec incX x = 
                        if sieve.ContainsKey(x) then
                            incX (x + step)
                        else 
                            x
                    incX initX
                sieve.Add(finalX, marker)
                
            if not found then 
                yield i
    }
printfn "%A" (Seq.take 100 primes)

---

http://blogs.msdn.com/chrsmith

Thanks a bunc! I wound up with this:

let Primes =

    seq {

        yield 2

        let sieve = new Dictionary()

        for i in 3 |> Seq.unfold (fun x -> Some(x, (x + 2))) do

            let (found, value) = sieve.TryGetValue(i)

            let marker = if found then value else i

            let _ =

                let step = marker + marker

                let rec Next x = if sieve.ContainsKey(x) then Next (x + step) else x

                let next = Next (marker + step)

                sieve.Add(next, marker)

                

            if not found then yield i

    }

The only thing I don't quite understand is why the yield needs to be the last thing in the seq and why "let _" is needed.

Hello.

Unfortunly, F# compiler does not allow to create recursive functions in sequence expressions, but we can create those into nested context (f.e. using "match ..." or "let _ = ...").

Also, we may not use "yield" into such nested contexts. So you code looks as it looks.

It's not necessary to use "yield" as last expression:

seq {

let c = ref 1

for i in 1..1000 do

yield i,if 1 = (i&&&1) then 0 else !c

do incr c

}