Re: [Caml-list] A (much less) frustrated beginner

[james woodyatt <jhw@wetware.com>]

[-- Attachment #1: Type: text/plain, Size: 807 bytes --]

On 23 Dec 2003, at 11:00, Tyler Eaves wrote:
>
> I think I'm beginning to get it. Attached find my second try at a prime
> number generator.
>
> This one is distinguished from my first by two important differences:
>
> 1: It is written (I think) in a completly functional style
> 2: It actually *works*. It's pretty fast too. Running as an optimized
> binary on my system (Athlon @ 950mhz under FreeBSD 5.1) it can 
> calculate
> the first 15104 primes (Highest is 165161) with one minute of CPU time.

For extra credit, have a look at the following bit of weirdness 
(though, I really think this thread belongs on the ocaml-beginners 
list).  I think you will be surprised at how fast it runs, and I 
suspect it would be a good piece of example code for figuring out how 
to use lazy evaluation in Ocaml.


[-- Attachment #2: primes.ml --]
[-- Type: application/octet-stream, Size: 1290 bytes --]

(** primes.ml -- sieve of eratosthenes *)

(* a lazy list *)
type 'a seq_cell = Z | P of 'a * 'a seq and 'a seq = 'a seq_cell Lazy.t

(* val sieve: int -> int seq -> int seq *)
let sieve n =
  let rec loop s =
    match Lazy.force s with
    | P (hd, tl) when hd mod n = 0 -> loop tl
    | P (hd, tl) -> P (hd, lazy (loop tl))
    | _ -> Z
  in
  fun s ->
    lazy (loop s)

(* val primes: int seq -> int seq *)
let primes max =
  let max = sqrt (float_of_int max) in
  let rec loop s =
    match Lazy.force s with
    | P (hd, tl) ->
      let tl = if float_of_int hd > max then tl else sieve hd tl in
      P (hd, lazy (loop tl))
    | Z ->
      Z
  in
  fun s ->
    lazy (loop s)

(* val counter: int seq *)
let counter =
  let rec loop n = P (n, lazy (loop (succ n))) in
  lazy (loop 2)

(* val limit: int -> 'a seq -> 'a seq *)
let rec limit max s =
  lazy begin
    match Lazy.force s with
    | P (hd, tl) when hd <= max -> P (hd, limit max tl)
    | _ -> Z
  end

(* val main: unit *)
let main =
  let rec loop s =
    match Lazy.force s with
    | P (hd, tl) -> Printf.printf " %d" hd; flush stdout; loop tl
    | Z -> ()
  in
  let n = int_of_string Sys.argv.(1) in
  Printf.printf "Primes to %d: 1" n;
  loop (primes n (limit n counter));
  print_newline ();
  flush stdout
;;

[-- Attachment #3: Type: text/plain, Size: 105 bytes --]




-- 
j h woodyatt <jhw@wetware.com>
that's my village calling... no doubt, they want their idiot back.