I like the mapWithState function.

I am forgetting that at the end of the day everything ends up imperative under the hood (it has to end up as machine code at some stage after all!)

I suppose, the trick is to have enough tools in the toolbag to write purely functional application code even if the tools themselves may be written less elegantly.

Presumably I could implement mapWithState as a type extension to Seq could I? Just to make it obvious that it is a generic tool.

Thanks to the other other posts using LazyLists. I can't say I fully understand the code snippets so need to do some reading up and experimenting. They look quite powerful. I'll end up learning something new which was the point of the original exercise.

Cheers everyone.

I see your point about finite lists, but can't I get around that with LazyLists?

For example, we start with the original isPrime x:bigint -> bool, then we just write

let rec getNextPrime (x:bigint) =
if (isPrime x) then
x
else
getNextPrime (x + 1I)

and build a LazyList of primes with

let ll = LazyList.unfold (fun x -> Some (x, getNextPrime (x + 1I))) 2I

and then change the "get the tuple" function to

let findLimit k l =
let rec inner p s l2 =
if s > k then
(p, s)
else
match l2 with
| LazyList.Cons(h, t) -> inner (h) (s + 1.0 / (float)(h)) (t)
| LazyList.Nil -> failwith "WTF?"
inner 0I 0.0 l

?

Hi.

I had an identical problem a few weeks ago. Here is a lazy list implementation of the prime number sequence:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

let rec smallest_prime_factor n = 
    let limit = System.Math.Sqrt(float(n)) |> int
    let rec smallest_prime_factor primes = 
        match primes with
        | LazyList.Cons(p,_) when (p>limit) -> n
        | LazyList.Cons(p,_) when (n%p=0) -> p
        | LazyList.Cons(_,tail) -> smallest_prime_factor tail
        | _ -> failwith "Invalid prime sequence!"
    smallest_prime_factor primes
and is_prime n = ((smallest_prime_factor n) = n)
and next_prime_after n = 
    assert(n%2=1)
    let candidate = n+2
    if (is_prime candidate) then candidate
    else next_prime_after candidate
and all_primes_after n = 
    let next = next_prime_after n
    LazyList.consf next (fun () -> all_primes_after next)
and primes = LazyList.consf 2 (fun () -> LazyList.consf 3 ( fun() -> all_primes_after 3 ) )

The great thing about this strategy is that not only is there absolutely no mutation anywhere, but also you will never go through the same calculations twice for the same number. So while the first iteration might be slow, successive iterations will be very fast. Plus general prime number calculation is faster, because when you're testing a number for primality you have to generate smaller primes to attempt to find a factor. Using the lazy implementation, you cant even get to a prime p until you've determined the primality of all numbers less than p, but at that point all those values are remembered, so they're never tested again.

Now if you want to generate a sequence of primes tupled with the running sum just do this you can use the awesome LazyList.folds() function. Add the following to the end of the code above, as the very last line:

1

and prime_inverse_sums = LazyList.folds (fun (_,sum) p -> (p, sum + (1.0 / (p |> float)))) (0, 0.0) primes

That's it! Here's some output from FSI:

> LazyList.take 5 prime_inverse_sums |> Seq.to_list;;
val it : (int * float) list
= [(2, 0.5); (3, 0.8333333333); (5, 1.033333333); (7, 1.176190476); (11, 1.267099567)]
>

In my experience, the main reason to use a seq in the first place is to hide a mutable. If you want to _get rid_ of a mutable, try a LazyList before trying anything else.