This assignment has five subproblems, each worth 20% of the grade. A bonus subproblem is worth an extra 20% of the grade. For each subproblem, turn in the code of your program, and its execution on at least the arguments given. The assignment is due before class on Tuesday Mar. 8. Please submit your file(s) as a single attachment (made using tar or zip if necessary) in an email to cse526@cs.sunysb.edu.

Problem 1. Recursive functions.

a. Selection sort. Selection sort takes a list of numbers and returns a sorted list of the numbers by selecting the minimum number in the input list, recursively sorting the remaining numbers, and constructing the output list with the minimum number as the head and the recursively sorted list as tail. Write an program for selection sort. Run it on at least three inputs that you consider interesting.

b. List cut. A cut of a list l is a pair l1 and l2 such that l = l1@l2. For example, the cuts of [1,2] are ([],[1,2]), ([1],[2]), and ([1,2],[]). Write a function cuts that takes a list as input and returns the list of all its cuts.

- cuts [];
stdIn:35.1-35.8 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
val it = [([],[])] : (?.X1 list * ?.X1 list) list

(* instead of
- cuts [];
val it = [([],[])] : ('a list * 'a list) list
*)

- cuts [1];
val it = [([],[1]),([1],[])] : (int list * int list) list

- cuts ["I'm", "melting"];
val it = [([],["I'm","melting"]),(["I'm"],["melting"]),(["I'm","melting"],[])] : (string list * string list) list

- cuts [1,2,3,4,5];
val it = [([],[1,2,3,4,5]),([1],[2,3,4,5]),([1,2],[3,4,5]),([1,2,3],[4,5]),([1,2,3,4],[5]),([1,2,3,4,5],[])] : (int list * int list) list

Problem 2. Higher-order functions as control abstraction

Give expressions not involving explicit recursion (or iteration, which is equivalent to tail recursion) for the following functions. You may use the functions accumulate and so on defined at the end; those definitions are recursive, but don't any extra recursion (or iteration, for that matter). Actually, your code could be no more than two lines for each of these.

a. Append. This is also built in as the operator @, but don't use @ in your definition.

fun append [] ys = ys
  | append (x::xs) ys = x::(append xs ys);

- append [1,2,3] [];
val it = [1,2,3] : int list

- append ["Spring", "Summer", "Fall"] ["Winter"];
val it = ["Spring","Summer","Fall","Winter"] : string list

b. Replicate. This is an example of overlapping patterns. Your solution may behave better on negative numbers.

fun replicate x 0 = []
  | replicate x n = x::(replicate x (n-1));

- replicate "Help" 5;
val it = ["Help","Help","Help","Help","Help"] : string list

- replicate () 10;
val it = [(),(),(),(),(),(),(),(),(),()] : (unit) list

- replicate (fn x => [[x]]) 2;
stdIn:77.1-77.28 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
val it = [fn,fn] : (?.X1 -> ?.X1 list list) list

(* instead of
- replicate (fn x => [[x]]) 2;
val it = [fn,fn] : ('a -> 'a list list) list
*)

c. Unique. This takes a list, and returns it with duplicates removed. Your output don't need to return exactly the same list as shown.

fun member x [] = false
  | member x (y::ys) = (x=y) orelse member x ys;

fun unique [] = []
  | unique (x::xs) = let val u = unique xs
		     in if (member x u) then u else x::u end;

- unique ["u", "n", "i", "q", "u", "e"];
val it = ["u","n","i","q","e"] : string list

- unique [1,2,3];
val it = [1,2,3] : int list

- unique [1,1,1,2,2,2,3,3,3,2,1,3,2,4,1,2,3,1,4,3,2,3,4,3];
val it = [1,2,3,4] : int list

d. Bonus subproblem: Prime.

fun prime n =
  let fun prime2 n m = if m>=n then true
		       else if n mod m = 0 then false
		       else prime2 n (m+1)
  in (n>1) andalso prime2 n 2 end;

- map prime (1 through 10);
val it = [false,true,true,false,true,false,true,false,false,false] : bool list

- prime 329;
val it = false : bool

fun accumulate init (h::t) f = accumulate (f init h) t f
  | accumulate init [] f    = init;

fun reduce f init (h::t) = f h (reduce f init t)
  | reduce f init []     = init;

fun map f [] = []
  | map f (a::l) = (f a) :: (map f l);

fun exists test [] = false
  | exists test (a::l) = if (test a) then true else exists test l;

fun forall test [] = true
  | forall test (a::l) = if (test a) then (forall test l) else false;

infix through;
fun m through n = if m>n then [] else m :: ((m+1) through n);