ML sample codes
fun printList(nil) = ()
| printList(x::xs) = (
print(Int.toString(x));
print("\n");
printList(xs)
);
fun rev_printList(nil) = ()
| rev_printList(x::xs) = (
rev_printList(xs);
print(Int.toString(x));
print("\n")
);
fun pow(x,n) = if x= 0 then 1
else x*pow(x,n-1) ;
fun filter(P,nil) = nil
| filter(P,x::xs) =
if P(x) then x::filter(P,xs)
else filter(P,xs) ;
fun odd(n) = if n mod 2 = 0 then true else false;
filter(fn(x) => odd(x) ,[1,2,3,4,5,6]) ;
exception EmptyList;
fun reduce(F,nil) = raise EmptyList
| reduce(F,[a]) = a
| reduce(F,x::xs) = F(x,reduce(F,xs));
fun max2(x,y) = if x > y then x else y ;
fun add2(x,y) = x + y ;
fun min2(x,y) = if x < y then x else y ;
fun mul2(x,y) = x * y ;
fun or2(x,y) = if x = true then true else y ;
fun maxL(L) = reduce(max2,L) ;
fun minL(L) = reduce(min2,L) ;
fun mulL(L) = reduce(mul2,L) ;
fun orL(L) = reduce(or2,L) ;
fun between2(x: real,l,u) = if x >= l andalso x <= u then true else false ;
fun double x = x + x ;
fun d_double (x) = double ( double (x)) ;
fun f91(x) = if x > 100 then x - 10
else f91(f91(x+11)) ;
fun tail(nil) = raise Empty
| tail(a::l) = l ;
fun head nil = raise Empty
| head (a::l) = a ;
fun rem_last nil = nil
| rem_last (a::nil) = nil
| rem_last(a::b::l) = a::rem_last(b::l) ;
(* remove last element from the list *)
fun zip nil l = nil
| zip l nil = nil
| zip (a::la) (b::lb) = (a,b)::(zip la lb) ;
(* zip a pair of list into a list of pairs *)
fun pow(x,0) = 1
| pow(x,n) = pow(x,n-1)* x ;
fun pow1(x, n, res) =
if n = 0 then res
else pow1(x,n-1,x*res) ;
fun member (x , nil) = false
| member (x,h::t) = (x = h) orelse member (x,t) ;
fun factor_1(n,k) =
if k = 1 then k
else if n mod k = 0 then k
else factor_1(n,k-1) ;
fun prime(n) =
if n = 2 then true
else if factor_1(n,n-1) > 1 then false
else true ;
fun length(L) = if L = nil then 0
else 1 + length(tl(L)) ;
fun len(L,n) = if L = nil then n
else len(tl(L), n+1) ;
fun length1(L) = len(L,0) ;
(* Tail recursion *)
fun fact(n) = if n = 0 then 1
else n*fact(n-1) ;
fun fact1(n,result) = if n = 0 then result
else fact1(n-1,n*result) ;
fun fact2(n) = fact1(n,1) ;
fun fib(n) = if n = 0 orelse n = 1 then n
else fib(n-1) + fib(n-2) ;
fun fib_aux(n,fn1,fn2) = if n = 0 orelse n = 1 then n
else if n = 2 then fn1 + fn2
else fib_aux(n-1,fn1+fn2 , fn1) ;
fun fib_tr(n) = fib_aux(n,1,0) ;
fun fib_tr1 n = let
fun fib_aux(n,fn1,fn2) = if n = 0 orelse n = 1 then n
else if n = 2 then fn1 + fn2
else fib_aux(n-1,fn1+fn2 , fn1)
in
fib_aux(n,1,0)
end ;
fun fastfib n = let
fun fibLoop a b 0 = a
| fibLoop a b n : int = fibLoop b (a+b) (n-1)
in
fibLoop 0 1 n
end;
fun sumList(L) = if L = nil then 0
else hd(L) + sumList(tl(L)) ;
fun sum_aux(L,res) = if L = nil then res
else sum_aux(tl(L), res + hd(L)) ;
fun sumList_tr(L) = sum_aux(L,0) ;
fun mulList(L) = if L = nil then 1
else hd(L)*mulList(tl(L)) ;
fun mulList_aux(L,res) = if L = nil then res
else mulList_aux(tl(L), hd(L)* res) ;
fun mulList_tr(L) = mulList_aux(L,1) ;
fun List(n) = if n = 0 then []
else List(n-1)@[n] ;
fun foldr f e [] = e
| foldr f e (h::t) = f (h, foldr f e t );
fun foldl f e [] = e
| foldl f e (h::t) = foldl f (f ( h, e)) t ;
fun length' s = foldr (fn (x,y) => 1 + y ) 0 s ;
fun sum' s = foldr ( fn (x,y) => x + y ) 0 s ;
fun mul' s = foldr (fn (x,y) => x * y ) 1 s
fun listrev s = foldl (op ::) [] s;
fun listid s = foldr (op ::) [] s ;
fun flatten (L) = if L = nil then nil
else hd(L)@flatten(tl(L)) ;
(* binary tree with integral leaf node *)
datatype inttree =
Lf
| Br of int* inttree * inttree;
val t1 = Br(34,Br(23,Lf,Lf),Br(54,Lf, Br(78,Lf,Lf)));
fun sumtree Lf = 0
| sumtree(Br(v, t1, t2)) = v + sumtree t1 + sumtree t2;
val t1sum = sumtree t1 ;
(* binary tree *)
datatype 'label btree =
Empty |
Node of 'label * 'label btree * 'label btree ;
(* create a binary tree *)
Node("as",Node("a",Empty,Empty),Node("in",Empty,Empty)) ;
Node(2,Node(1,Empty,Empty),Empty) ;
fun lower(nil) = nil
| lower(c::cs) =
if c>= #"A" andalso c<= #"Z" then chr(ord(c)+32)::lower(cs)
else c::lower(cs);
fun lt(x:string,y) =
implode(lower(explode(x))) < implode(lower(explode(y)));
exception EmptyTree;
(*=================================================================*)
(* lookup(x,T) tells whether element x is in tree T *)
fun lookup(x,Empty) = false
| lookup(x,Node(y,left,right)) =
if x=y then true
else if lt(x,y) then lookup(x,left)
else (* lt(y,x) *) lookup(x,right);
(* insert(x,T) returns tree T with x inserted *)
fun insert(x,Empty) = Node(x,Empty,Empty)
| insert(x, T as Node(y,left,right)) =
if x=y then T (* do nothing; x was already there *)
else if lt(x,y) then Node(y,insert(x,left),right)
else (* lt(y,x) *) Node(y,left,insert(x,right));
(* deletemin(T) returns a pair consisting of the least element y
in tree T and the tree that results from deleting y from T.
It is an error if T is empty *)
fun deletemin(Empty) = raise EmptyTree
| deletemin(Node(y,Empty,right)) = (y,right)
(* This is the critical case. If the left subtree is empty,
then the element at the current node is the min. *)
| deletemin(Node(w,left,right)) =
let val (y,L) = deletemin(left)
in (y, Node(w,L,right))
end;
(* delete(x,T) returns tree T with element x deleted *)
fun delete(x,Empty) = Empty
| delete(x,Node(y,left,right)) =
if lt(x,y) then Node(y,delete(x,left),right)
else if lt(y,x) then Node(y,left,delete(x,right))
else (* x=y *)
if left = Empty then right
else if right = Empty then left
else let val (z,R) = deletemin(right)
in Node(z,left,R)
end;
fun sum(Empty) = 0
| sum(Node(a,left,right)) =
a + sum(left) + sum(right);
fun preOrder(Empty) = nil
| preOrder(Node(a,left,right)) =
[a] @ preOrder(left) @ preOrder(right) ;
fun inOrder(Empty) = nil
| inOrder(Node(a,left,right)) =
inOrder(left)@[a]@inOrder(right) ;
val x =insert("ML",Empty) ;
val x = insert("MosML",x) ;
val x = insert("SML",x) ;
val x = insert("Functional Programming",x) ;
val x = insert("Procedural Programming", x) ;
inOrder(x) ;
preOrder(x) ;
(* polynomial *)
type term = real * int
datatype termsum = Zero | Sum of (term * termsum)
val test_poly = Sum((1.0,2) , Sum( ( 2.0,1), Sum((3.0,0), Zero)));
load "Real";
load "Int" ;
fun print_poly(ts:termsum) : unit =
let fun print_term((coef,pow) : term ) : unit =
(print(Real.toString(coef));
if pow <> 0 then print("*x^" ^ Int.toString(pow)) else ())
in case ts of
Zero => print("0\n")
| Sum(t,Zero) => (print_term(t) ; print("\n") )
| Sum(t, xs) => (print_term(t); print(" + "); print_poly(xs))
end ;
fun add_poly(ts1: termsum , ts2 : termsum ) : termsum =
case (ts1, ts2) of
(Zero, _ ) => ts2
| (_, Zero) => ts1
| (Sum((c1,p1), xs1), Sum((c2,p2), xs2)) =>
case Int.compare(p1,p2) of
GREATER => Sum((c1,p1), add_poly(xs1,ts2))
| LESS => Sum((c2,p2), add_poly(ts1,xs2))
| EQUAL => Sum((c1+c2, p1), add_poly(xs1,xs2)) ;
fun mult_poly(ts1: termsum, ts2: termsum) : termsum =
let fun mult_term((c1,p1): term, ts:termsum) =
case ts of
Zero => Zero
| Sum((c2,p2),xs) => Sum((c1*c2, p1+p2), mult_term((c1,p1), xs))
in case ts1 of
Zero => Zero
| Sum(t,xs1) => add_poly(mult_term(t,ts2), mult_poly(xs1,ts2))
end ;
print_poly(mult_poly(test_poly, test_poly)) ;