(* Here's several examples of common higher-order functions. Each one
   is followed by some simple functions illustrating its use.  *)


(* COMPOSE == function composition (o)  *)

fun COMPOSE (F,G) = fn X => (F (G X));

val test_COMPOSE = COMPOSE (implode,explode);


(* REV_ARG -- takes a binary function, F, as an argument and returns
              a function G such that (G (X,Y)) = (F (Y,X))  *)

fun REV_ARG F = fn (X,Y) => (F (Y,X));

val divided_into =
let fun divide (X,Y) = X div Y
in  REV_ARG divide
end;


(* MAP. A very commonly used function.
   MAP (F,L) returns the results of applying F to each element of L.  *)

fun MAP (_,[]) = []
 |  MAP (F,head::tail) = (F head)::(MAP (F,tail))
;

fun test_MAP L =         (* increment each element in L *)
let fun increment x = 1+x
in  MAP (increment,L)
end;

(* F_MAP.
  Analagous to MAP - takes a list of functions and applies each to the same
  argument  *)
 
fun F_MAP ([],_) = []
 |  F_MAP (Fhead::Ftail,Arg) = (Fhead Arg)::(F_MAP (Ftail,Arg))
;

(* PRODUCT.  Like MAP, except in this case there is a list of functions
             and a list of arguments. Returns a list of the result of applying
             each function to each argument.  *)

fun PRODUCT ([],_) = []
 |  PRODUCT (Fhead::Ftail,ArgList) = (MAP (Fhead,ArgList))@(PRODUCT (Ftail,ArgList))
;

fun test_PRODUCT L =   (* increment, double, and square all the integers in L *)
let fun increment x  = 1+x
    fun double    x  = 2*x
    fun square x:int = x*x
in  PRODUCT ([increment,double,square],L)
end;

(* FOLD (F,X,L) -- another very commonly used function.
   Somewhat hard to describe in words, but well-illustrated in
   the examples that follow.  *)

fun FOLD (_,X,[])         = X    (* X accumulates the final result  *)
 |  FOLD (F,X,head::tail) = FOLD (F,(F (X,head)),tail)
;

fun add_up L =             (* add up the elements in list L *)
let fun add (A:int,B) = A + B
in   FOLD (add,0,L)
end;

fun largest L =             (* returns the largest element in list L *)
let fun max (A:int,B) = if A < B then B else A
in   FOLD (max,0,L)         (* returns 0 if L has no positive elements  *)
end;

fun how_true L =            (* counts number of true values in list L *)
let fun increment_if_true (N,true)  = N+1
     |  increment_if_true (N,false) = N
in   FOLD (increment_if_true,0,L)
end;

(* Question: Given a predicate P and list L, what is the effect of
             (how_true (MAP (P,L)) ?    *)



(* ZIP (F,L1,L2) -- another classic.  F is a binary function.
   ZIP pairs up corresponding elements in lists L1 and L2 and
   applies F to each pair.  *)

fun ZIP (_,[],_) = []
 |  ZIP (_,_,[]) = []
 |  ZIP (F,head1::tail1,head2::tail2) = (F (head1,head2))::(ZIP (F,tail1,tail2))
;

fun test_ZIP (L1,L2) =      (* add the corresponding elements in L1 and L2 *)
let fun add (A:int,B) = A + B
in  ZIP (add,L1,L2)
end;