Assignment 4 (CPS)

Due Date: May 1, 2000 before class

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