links

< home >
< unix stuff >
< code >
< writing >
< archive >
< music >
< photos >
< recipes >
< site map >
< about badcomputer >

sieve of eratosthenes

Standard ML

(* Sieve of Eratosthenes in Standard ML
 * Written by Rob Hoelz
 *
 * To run:
 *  $ sml sieve.sml
 *  - main <limit>
 *
 *)

datatype 'a lazyList =
    nullList | cons of 'a * (unit -> 'a lazyList)

fun seq first last =
  if first = last then
    cons(first, (fn () => nullList))
  else
    cons(first, (fn () => seq (first + 1) last))

fun lazyMap func nullList = []
  | lazyMap func (cons(h,t)) =
        (func h) :: (lazyMap func (t()))

fun filter _ nullList = nullList
  | filter pred (cons(h,t)) =
        if (pred h) then
          cons(h, (fn () => filter pred (t())))
        else
          filter pred (t())

fun primesAux _ nullList = nullList
  | primesAux limit (cons(h, t)) =
        if (h * h) <= limit then
          cons(h, (fn () => primesAux limit (filter (fn y => (y mod h) <> 0) (t()))))
        else
          cons(h, t)

fun primes limit = primesAux limit (seq 2 limit)

fun main limit = ((lazyMap (print o (fn x => (Int.toString x) ^ " ")) (primes limit)); print "\n")

back to Eratosthenes page

stats

It is Sunday October 12, 2008 1:38 pm
This page served 892 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.61
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 13:38:04 up 74 days, 04:44, 1 user, load average: 0.00, 0.00, 0.00