← Back to branch summary

~ubuntu-branches/ubuntu/karmic/ocaml-doc/karmic

« back to all changes in this revision

Viewing changes to examples/basics/sieve.ml

  • Committer: Bazaar Package Importer
  • Author(s): Vanicat Rémi
  • Date: 2002-02-05 10:51:43 UTC
  • Revision ID: james.westby@ubuntu.com-20020205105143-a061tunf8tev07ne
Tags: 3.04-4
* New debian maintainer
* Split doc-base file
* Move to non-free
* Change the copyright file to the copyright of the documentation
* remove FAQs (their license prohibit their redistribution)
* corrected the examples

Show diffs side-by-side

added added

removed removed

Lines of Context:
examples/basics/sieve.ml
 
1
(* Eratosthene's sieve *)
 
2
(*
 
3
  Manipulation of lists.
 
4
 
 
5
  - [] is the empty list
 
6
  - :: is the infix operator that builds list cells.
 
7
    Hence 1 :: (2 :: []) is the list that contains 1 and 2 in this order.
 
8
 
 
9
*)
 
10
(* interval min max = [min; min+1; ...; max-1; max] *)
 
11
 
 
12
let rec interval min max =
 
13
  if min > max then [] else min :: interval (succ min) max
 
14
;;
 
15
 
 
16
(*
 
17
 
 
18
  Case analysis on list l is written
 
19
  match l with
 
20
  | [] -> ``nil case''
 
21
  | x :: tail -> ``non nil case,
 
22
                   with x (the head of l) and tail (the tail of l) available''
 
23
 
 
24
  Function can perform direct case analysis on their argument,
 
25
  if introduced by the function keyword. Hence,
 
26
 
 
27
    let f (x) =
 
28
      match x with
 
29
      | [] -> ...
 
30
      | ...
 
31
 
 
32
  can be abreviated as
 
33
 
 
34
    let f = function
 
35
      | [] -> ...
 
36
      | ...
 
37
 
 
38
*)
 
39
 
 
40
(* filter p L returns the list of the elements in list L
 
41
   that satisfy predicate p *)
 
42
 
 
43
let rec filter p = function
 
44
  | []  -> []
 
45
  | a :: r -> if p a then a :: filter p r else filter p r
 
46
;;
 
47
 
 
48
(* Application: removing all numbers multiple of n from a list of integers *)
 
49
 
 
50
let remove_multiples_of n =
 
51
  filter (fun m -> m mod n <> 0)
 
52
;;
 
53
 
 
54
(* The sieve itself *)
 
55
 
 
56
let sieve max =
 
57
  let rec filter_again = function
 
58
  | [] -> []
 
59
  | n :: r as l ->
 
60
      if n * n > max then l else n :: filter_again (remove_multiples_of n r)
 
61
  in
 
62
    filter_again (interval 2 max)
 
63
;;
 
64
 
 
65
let usage() =
 
66
  print_string "Usage: sieve <n>\n";
 
67
  exit 2
 
68
;;
 
69
 
 
70
(* The entry point *)
 
71
 
 
72
let main () =
 
73
  if Array.length Sys.argv <> 2 then usage () else
 
74
  begin
 
75
    try
 
76
      let n = int_of_string Sys.argv.(1) in
 
77
      List.iter (fun n -> print_int n; print_string " ") (sieve n);
 
78
      print_newline ()
 
79
    with Failure "int_of_string" ->
 
80
      print_string "Bad integer constant";
 
81
      print_newline ()
 
82
  end
 
83
;;
 
84
 
 
85
if !Sys.interactive then () else main ();;