(* This file contains sample basic sml code to get you started.  load
   and run the file with use "sample.sml"   *)



(* n!  in  C:

  int f(int n) 
    { if (n<2) return 1 else return n*f(n-1); }
*)

(* n! in sml  *)

fun fact n = if (n<2) then 1 else n*(fact (n-1));

fact 4;


(* function definition by pattern matching, reversing a list *)
(* nil = empty list, :: = cons, @ = append *)
fun revlist nil = nil
  | revlist (A::B) = (revlist B)@[A];

revlist [1,2,3,4];
revlist ["a","b","c","d"];   (* demonstrates polymorphism *)

(* iterative version of list reversal, using a LOCAL FUNCTION: *)
fun rev2 L =
  let fun helper nil M = M
	| helper (h::t) M = helper t (h::M);
  in
     helper L nil
  end;

rev2 [1,2,3];

(* test for list membership *)
fun member x nil = false
  | member x (h::t) = (x = h) orelse (member x t);

(* deleting all occurences of an element from a list *)
fun delete A nil = nil 
  | delete A (B::R) = if (A=B) then (delete A R) else (B::(delete A R));

(* remove duplicates from a list *)
fun remDups nil = nil     	
  | remDups (A::R) = (A::(remDups (delete A R)));


(* algebraic datatype for polymorphic binary trees *)
datatype 'a btree = emptytree | node of ('a btree)*'a*('a btree);

(* add all the elements in a integer binary tree *)

fun sumtree emptytree = 0
  | sumtree (node(lbranch,x,rbranch)) = 
	x + (sumtree lbranch) + (sumtree rbranch);

sumtree (node(emptytree,3,node(node(emptytree,2,emptytree),4,emptytree)));


(* Higher Order Programming Examples: *)

fun map f nil = nil
  | map f (h::t) = (f h)::(map f t);

fun fold f id nil = id
  | fold f id (h::t) = f h (fold f id t);

fun filter f nil = nil
  | filter f (h::t) = if (f h) then (h::(filter f t)) else (filter f t);

fun fdelete x L = filter (fn y => not(x = y)) L;

fun sublist a b = fold (fn x => fn y => x andalso y) true 
			(map (fn x => member x b) a);