From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id HAA17215; Wed, 24 Dec 2003 07:42:13 +0100 (MET)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA17278 for <caml-list@pauillac.inria.fr>; Wed, 24 Dec 2003 07:42:12 +0100 (MET)
Received: from wetware.com (wetware.wetware.com [199.108.16.1])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hBO6gBb29907
	for <caml-list@inria.fr>; Wed, 24 Dec 2003 07:42:11 +0100 (MET)
Received: from [208.177.152.18] (helo=[10.0.1.5])
	by wetware.com with esmtp (Exim 4.20)
	id 1AZ2ib-0001Vx-4p; Tue, 23 Dec 2003 22:42:05 -0800
In-Reply-To: <1072206032.62516.27.camel@tylere>
References: <1072206032.62516.27.camel@tylere>
Mime-Version: 1.0 (Apple Message framework v609)
Content-Type: multipart/mixed; boundary=Apple-Mail-4--548356526
Message-Id: <48E3FF15-35DC-11D8-859D-000393B8133A@wetware.com>
Cc: caml-list@inria.fr
From: james woodyatt <jhw@wetware.com>
Subject: Re: [Caml-list] A (much less) frustrated beginner
Date: Tue, 23 Dec 2003 22:42:03 -0800
To: Tyler Eaves <tyler@ml1.net>
X-Mailer: Apple Mail (2.609)
X-Loop: caml-list@inria.fr
X-Spam: no; 0.00; woodyatt:01 jhw:01 wetware:01 caml-list:01 00,:99 950:99 primes:01 weirdness:01 figuring:01 woodyatt:01 jhw:01 wetware:01 village:99 ocaml:01 credit:98 
X-Attachments: type="application/octet-stream" name="primes.ml" name="primes.ml" 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk


--Apple-Mail-4--548356526
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed

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.


--Apple-Mail-4--548356526
Content-Transfer-Encoding: 7bit
Content-Type: application/octet-stream;
	x-unix-mode=0644;
	name="primes.ml"
Content-Disposition: attachment;
	filename=primes.ml

(** 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
;;

--Apple-Mail-4--548356526
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
	charset=US-ASCII;
	format=flowed




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

--Apple-Mail-4--548356526--

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners