Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
119 lines (98 sloc) 2.75 KB
------------------------------------------------------------------------
-- Basic operations on lists of integers
------------------------------------------------------------------------
let range = rec range : int -> int -> int list is
fun m : int => fun n : int =>
if n < m then [int] else m :: (range (m+1) n)
let append = rec append : int list -> int list -> int list is
fun lst1 : int list =>
fun lst2 : int list =>
match lst1 with
[int] => lst2
| x::xs => x :: (append xs lst2)
;;
let fold_left =
rec fold_left : (int -> int -> int) -> int -> int list -> int is
fun f : (int -> int -> int) =>
fun x0 : int =>
fun lst : int list =>
match lst with
[int] => x0
| x::xs => fold_left f (f x0 x) xs
;;
let flatten =
rec flatten : int list list -> int list is
fun lsts : int list list =>
match lsts with
[int list] => [int]
| l :: ls => append l (flatten ls)
;;
let zip2 =
rec zip2 : int list -> int list -> int list is
fun l1 : int list =>
fun l2 : int list =>
match l1 with
[int] => l2
| x::xs =>
x :: (match l2 with
[int] => xs
| y::ys => y::(zip2 xs ys))
;;
let zip =
rec zip : int list list -> int list is
fun lsts : int list list =>
match lsts with
[int list] => [int]
| l::ls => zip2 l (zip ls)
let map = rec map : (int -> int) -> int list -> int list is
fun f : (int -> int) =>
fun l : int list =>
match l with
[int] => [int]
| x::xs => (f x) :: (map f xs)
;;
let filter =
rec filter : (int -> bool) -> int list -> int list is
fun p : (int -> bool) =>
fun l : int list =>
match l with
[int] => [int]
| x::xs => if p x then x::(filter p xs) else filter p xs
;;
------------------------------------------------------------------------
-- Prime numbers
------------------------------------------------------------------------
-- negation
let not = fun b : bool => if b then false else true
;;
-- integer division
let div = fun m : int => rec d : int -> int is
fun n : int => if n < m then 0 else 1 + (d (n-m))
;;
-- remainder
let mod = fun m : int => fun n : int =>
n - m * (div m n)
;;
let notmultiple = fun m : int => fun n : int =>
not (n % m = 0)
;;
let nth = rec nth : int list -> int -> int is
fun l : int list => fun n : int =>
match l with
[int] => 0
| x::xs => if n = 0 then x else nth xs (n-1)
;;
let nat = rec nat : int list is 1 :: (map (fun n : int => n + 1) nat)
;;
let nat2 = rec nat2 : int list is 2 :: (map (fun n : int => n+1) nat2)
;;
let sieve = rec sieve : int list -> int list is
fun l : int list =>
match l with
[int] => [int]
| n::ns => n :: (sieve (filter (notmultiple n) ns))
;;
-- the infinite list of primes
let primes = sieve nat2
;;
primes