CSE 526
Spring 2005 Stony Brook |
Principles of Programming Languages
Annie Liu Homework 6 |
Handout H6
Mar. 1, 2005 Due Mar. 8 |

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);

For explanations of the two warnings, see "What is the value restriction?" near the end of http://www.faqs.org/faqs/meta-lang-faq/