(*world*)

fun accumulate f a [] = a
   |accumulate f a (b::x) = accumulate f (f a b) x;
(* For example:
   fun sum (i:int) (j:int) = i+j;
   accumulate sum 0 [1,2,3,4,5];
   fun prod (i:int) (j:int) = i*j;
   accumulate prod 1 [1,2,3,4,5]; *)

fun append x y = x @ y;

infix mo; (* member of *)
infix subset;
infix superset;
infix intersection;
infix difference;

fun e mo [] = false
   |e mo (a::x) = e=a orelse (e mo x);

fun remove e [] = []
   |remove e (a::x) = if e=a then remove e x else a::remove e x;

fun x subset  y = let fun subsetp [] y = true
                        |subsetp (a::x) y = a mo y andalso 
                                            subsetp x y
                     in (length x) <= (length y) andalso 
                         subsetp x y end;

fun x superset  y = y subset x;
(* Why is not the definition of superset as follows?
        fun superset x y = not(x subset  y);
   As the chemist said "Suck it and see" *)

fun [] intersection y = []
   |(e::x) intersection y = if e mo y 
                            then e::(x intersection y)
                            else x intersection y;
fun [] difference y = []  
   |(e::x) difference y = if e mo y
                          then x difference y
                          else e::(x difference y);
   

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

fun exists p [] = false
   |exists p (a::x) = p a orelse exists p x;

fun all p [] = true
   |all p (a::x) = p a andalso all p x;

fun zip f [] [] = []
   |zip f [] (b::y) = []
   |zip f (a::x) [] = []
   |zip f (a::x) (b::y) = f a b::zip f x y;

fun nth n [] = []
   |nth 1 (a::x) = [a]
   |nth n (a::x) = nth (n-1) x;

fun reverse [] = []
   |reverse (a::x) = (reverse x) @ [a]; 

fun mapf [] x = []
   |mapf (f::fs) x = (f x)::(mapf fs x);
(* Given a list of functions [f1,f2,...,fn] and an argument x
   deliver a list of results [(f1 x),(f2 x),...,(fn x)]
   This may be used as follows: val fns = map remove [1,2,3];
                                mapf fns [1,2,3]
   This will deliver [[2,3],[1,3],[1,2]]   *)


(* Use these functions to familiarise youself with what they do
   These are basic list handling functions, and may be considered as 
   a functional programmer's primitive world.
  
  20 Questions! Write the following functions:
  
  (1) remove_if p e x
      Remove from the list x all elements that fail to satisfy 
      the binary predicate p e ex (where ex is a member of x)
  (2) equal_if p x y
      Deliver true if p ex ey holds for pairwise
      comparisons between members of x and y. Note that x and
      y are of the same type but may be of different lengths.
  (3) flatten x
      x is a list of lists. Produce the list that is the result
      of appending together all lists in x
  (4) min x
      Deliver the smallest member of the list of integers x
      What will you do if x=[]?
  (5) max x
      Deliver the largest member of the list of integers x
      What will you do if x=[]?
  (6) remove_duplicates x
      Given a list x, remove all duplicate items
      (Note: this may be of use in future exercises)
  (7) primes n
      Deliver the list of the first n prime numbers
  (8) primep n
      Predicate that test for primeness
  (9) first_half x
      Deliver the first half of the list x
 (10) last_half x
      Deliver the last half of the list x
 (11) insert p e x
      Insert the element e into the list x such that 
      the binary predicate holds over that list
 (12) insert_lt e x
      Insert e into the list x, where x is in ascending order
      (Hint: curry)
 (13) pair_with e x
      Take an element e and a list x, produce a list of
      pairs (e,ex) where ex is a member of x.
      Use the function map to do this.
 (14) merge p x y
      Merge the to sorted lists x and y such that the binary
      predicate p holds over the resultant list.
 (15) bin_member e x
      Deliver true if e is a member of the list x.
      Implement as a "binary chop" using functions
      first_half and last_half
 (16) num_to_char n
      The argument n is an integer. Deliver its string equivalent.
      That is: num_to_char 129 delivers "129"
 (17) nums_to_char x
      Given a list of integers produce a list of string equivalents.
      Use map.
 (18) bin_members x
      Given a list of pairs of the form (e,(ey::y)) deliver
      true if for every pair e is a member of (ey::y).
      Create the data set using pair_with over a pair of lists
      x and y (where y is a list of lists) using map. Implement
      bin_members using functions bin_member and map (if possible).
 (19) sort p x
      Given the binary predicate p and the list x
      sort the list x with respect to p. Use sort to sort
      (a) a list of integers in ascending order, (b) a list of
      integers into ascending order, (c) a list names into
      alphabetic order, (d) a list of lists such that the resultant
      list is a sorted list of sorted lists.
 (20) all_true x
      Given a list of pairs of the form (p,(e::y)) deliver 
      true if for each pair the predicate p holds over its list.


*)