(* Programming language concepts, seminar 5, 2002-03-02 *)
(* SML: higher-order functions: map, foldr, anonymous functions *)

fun map f []      = []
  | map f (x::xr) = f x :: map f xr;

fun getxs (xes : ('a * 'b) list) : 'a list = map #1 xes


(* SML: anonymous functions: fn instead of fun *)

fun doubl x = 2 * x;

map doubl [4, 5, 89];

map (fn x => 2 * x) [4, 5, 89];


(* SML: apply function twice *)

fun tw g x = g (g x);

val quad = tw doubl;

quad 7;


(* SML: apply function n times *)

fun rep n g x = if n=0 then x else rep (n-1) g (g x);

val tw = rep 2;

val quad = tw doubl;

quad 7;


(* The function that multiplies by 2, ten times *)

val twototen = rep 10 doubl;

twototen 7;


(* A function that selects list elements satisfying predicate p *)

fun filter p []      = []
  | filter p (x::xr) = if p x then x :: filter p xr else filter p xr;

val even = filter (fn i => i mod 2 = 0) [4, 6, 5, 2, 54, 89];


(* SML: the list iterator foldr.
   foldr f e xs recursively replaces     
        []        by e 
   and  (x :: xr) by f(x, xr) 
*)

fun foldr f e []      = e
  | foldr f e (x::xr) = f(x, foldr f e xr);

fun len xs   = foldr (fn (_, res) => 1+res) 0 xs;

fun sum xs   = foldr (fn (x, res) => x+res) 0 xs;

fun prod xs  = foldr (fn (x, res) => x*res) 1 xs;

fun map g xs = foldr (fn (x, res) => g x :: res) [] xs;

fun concat xss = foldr (fn (xs, res) => xs @ res) [] xss;


(* SML: Polymorphic trees *)

datatype 'a tree =
    Lf 
  | Br of 'a * 'a tree * 'a tree;

(* SML: the tree iterator tfold *)

fun tfold f e Lf            = e
  | tfold f e (Br(v,t1,t2)) = f(v, tfold f e t1, tfold f e t2);

fun sumtree t = tfold (fn (v, r1, r2) => v + r1 + r2) 0 t;