# Assignment 4 (CPS)

## Due Date: May 1, 2000 before class

Convert the following functions to CPS.
```fun dup e 0 = []
| dup e n = e :: (dup e (n-1))

fun index 0 (x::xs) = x
| index n (x::xs) = index (n-1) xs

fun remove 0 (x::xs) = xs
| remove n (x::xs) = x :: (remove (n-1) xs)

fun insert y 0 xs = y::xs
| insert y n (x::xs) = x :: (insert y (n-1) xs)

fun fib 0 = 0
| fib 1 = 1
| fib n = fib(n-1) + fib(n-2)

(*
When translating filter to filtercps, assume that pred
has also been translated to predcps
*)
fun filter pred [] = []
| filter pred (x::xs) = if pred x
then x :: (filter pred xs)
else filter pred xs

(* This is an example function that you can pass to filter *)
fun pred1 n = if (n < 10)
then true
else if (n > fib (n-10))
then true
else false

fun map f [] = []
| map f (x::xs) = f x :: (map f xs)

fun powerset [] = [[]]
| powerset (x::xs) =
let val prl = powerset xs
val hpl = map (fn subset => x :: subset) prl
in prl @ hpl
end

fun merge [] ys = ys
| merge xs [] = xs
| merge (x::xs) (y::ys) =
if (x < y)
then x :: (merge xs (y::ys))
else y :: (merge (x::xs) ys)

fun split [] = ([],[])
| split [x] = ([x],[])
| split (x1::x2::xs) = let val (l1,l2) = split xs
in (x1::l1, x2::l2)
end

fun mergesort [] = []
| mergesort [x] = [x]
| mergesort xs = let val (l1,l2) = split xs
in merge (mergesort l1) (mergesort l2)
end

```

Page visited times since November 18, 1996.

sabry@cs.uoregon.edu