Back to Questions
1.7k
views3
comments
for fun: generate primes using seq comprehansions
f#

It's work :)

But if we will have Seq.tl, this code will be simpler

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

let gen_primes n = 

  let test n = function

    | i when i*i > n -> Some true

    | i when n%i = 0 -> Some false

    | _ -> None

  let rec primes = {

  yield 2

  yield 3

  for i in 6..6..n do

    if Some true = Seq.first (test (i-1)) primes then yield i-1

    if Some true = Seq.first (test (i+1)) primes then yield i+1

  }

  primes

> List.of_seq (gen_primes 100);;

val it : int list

= [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;

73; 79; 83; 89; 97]

.

The traditional functional idiom for primes is something like

1
2
3
4
5
6

let primes = 
  let rec prim s = 
    { let h = Seq.hd s
       -> h 
       ->> prim {for i in s when i%h<>0 -> i} } in
  Seq.init_infinite ((+)2) |> prim

though the current syntax for sequence expressions is not as beautiful as it could be.

By on 11/24/2007 2:13 PM ()

It's recommended you use yield/yield! instead of "->" and "->>" in sequence expressions of any real size.

For example:

1
2
3
4
5
6
7
8
9
10
11
12
13

 

#light
let primes = 
  let rec prim n (sofar: list<int>) = 
      seq { if (sofar |> List.for_all (fun i -> n%i <> 0)) then 
                yield n
                yield! prim (n+1) (n :: sofar) 
            else 
                yield! prim (n+1) sofar }
  prim 2 []

Or using a mutable buffer to hold the generated primes:

1
2
3
4
5
6
7
8
9
10
11
12
13

 

#light
let primes2 = 
  let sofar = new ResizeArray<_>()
  let rec prim n  = 
      seq { if (sofar |> ResizeArray.for_all (fun i -> n%i <> 0)) then 
                do sofar.Add(n)
                yield n
            yield! prim (n+1) }
  prim 2

Kind regards

don

By on 11/24/2007 11:08 PM ()

Don, what *is* <i>yield!<i>, exactly? Is -> to <i>yield<i> as ->> is to <i>yield!<i>? Apropos, I saw <i>return!<i> for the first time today, on your blog. Could I ask what it means? Sorry if this is an elementary question; I'm struggling with f.p.

By on 12/10/2007 8:33 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper