Due April 30, 1998 before class

Read a Scheme reference and Chapter 8 in the EOPL book.

Write Scheme definitions for the following functions and convert them to CPS. The continuation argument should be the last argument. For example, if you were asked to write factorial and its CPS counterpart, the answer would be:

(define fact
  (lambda (n) 
    (if (zero? n)
        1
        (* n (fact (- n 1))))))

(define factcps
  (lambda (n k)
    (if (zero? n)
        (k 1)
        (factcps (- n 1) (lambda (v)
          (k (* n v)))))))

• A function dupla that takes two argument, an element and a size, and creates a list of the requested size:

  (dupla 3 0) ==> '()
  (dupla 3 1) ==> '(3)
  (dupla 3 2) ==> '(3 3)
  (dupla 3 5) ==> '(3 3 3 3 3)
  

• A function index that returns the nth element of a list

  (index 3 '(a b c d e f)) ==> 'd
  

• A function remove that removes the nth element of a list:

  (remove 1 '(a b c d e f)) ==> '(a c d e f)
  

• A function insert that inserts an element at the nth position of a list:

   
  (insert 'a 2 '(1 2 3 4 5 6)) ==> '(1 2 a 3 4 5 6)
  

• The Fibonacci function.

  (fib 0) ==> 0
  (fib 1) ==> 1
  (fib 2) ==> 1
  (fib 8) ==> 21
  

• The function filter that takes two arguments: a function that represents a predicate, and a list of numbers. It returns a new list that consists of all the elements in the argument list that satisfy the predicate:

  (filter even? '(1 2 3 4 5 6)) ==> '(2 4 6)
  (filter (lambda (x) (> x 8)) '(1 9 2 10 3 11 4 12)) ==> '(9 10 11 12)
  (filter (lambda (x) (and (> x 8) (< x 10))) '(1 9 2 10 3 11 4 12)) ==> '(9)
  

  When converting to CPS, assume the predicate function has also been converted to CPS.

• Write the function map that takes a function and a list of numbers, and returns a new list that is similar to the argument list except that the input function has been applied to each element:

  (map add1 '(1 2 3)) ==> '(2 3 4)
  (map (lambda (x) (* x 3)) '(1 2 3)) ==> '(3 6 9)
  

  When converting to CPS, assume the function has also been converted to CPS.

• The function powerset that takes a list of numbers that represents a set and returns the powerset. Use map and mapcps in the solution.

  (powerset '()) ==> '(()) 
  (powerset '(1 2 3)) ==> '((), (3), (2), (2,3), (1), (1,3), (1,2), (1,2,3))
  

• The function merge that merges two sorted lists of numbers into a larger sorted list.

  (merge '() '(1 2 3)) ==> '(1 2 3)
  (merge '(1 2 3) '()) ==> '(1 2 3)
  (merge '(1 3 5 7 8 9 10) '(2 4 6)) ==> '(1 2 3 4 5 6 7 8 9 10)
  

• The function split that takes a list and splits it in two sublists. The first sublist should contain the elements at odd indices, and the second sublist should contain the elements at even indices.

  (split '()) ==> '(() ())
  (split '(1)) ==> '((1) ())
  (split '(1 2 3 4 5 6 7 8 9)) ==> '((1 3 5 7 9) (2 4 6 8))
  (split '(1 2 3 4 5 6 7 8 9 10)) ==> '((1 3 5 7 9) (2 4 6 8 10))
  

• The function mergesort that takes a list of numbers and returns a sorted version. Use split, splitcps, merge, and mergecps in your solution:

  (mergesort '()) ==> '()
  (mergesort '(8 1 3 9 6 5 7 2 4 10)) ==> '(1 2 3 4 5 6 7 8 9 10)
  

Extra Credit