Due April 29, 1997 before class

Read Chapters 2, 4, and 8 in the EOPL book.

For each of the following problems, write a recursive definition, and then convert it to continuation-passing style. The variable I below is defined as the identity procedure (lambda (x) x).

1. Write a function fib that takes a number n and returns the nth Fibonacci number:

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

2. Write a function remfirst that takes a number n and a list of numbers lon and removes the first occurrence of n from lon:

   (remfirst 3 '(1 2 3 4 5 3)) ==> (1 2 4 5 3)
   (remfirst 3 '()) ==> ()
   
   (remfirstcps 3 '(1 2 3 4 5 3) I) ==> (1 2 4 5 3)
   (remfirstcps 3 '() I) ==> ()
   

3. Write a function remall that takes a number n and a list of numbers lon and removes all occurrences of n from lon:

   (remall 3 '(1 2 3 4 5 3)) ==> (1 2 4 5)
   (remall 3 '()) ==> ()
   
   (remallcps 3 '(1 2 3 4 5 3) I) ==> (1 2 4 5)
   (remallcps 3 '() I) ==> ()
   

4. Write a function insert that takes 3 arguments: a number new, a number old, and a list of numbers lon, and returns a new list that looks like lon except that new is inserted to the right of the first occurrence of old.

   (insert 1 3 '(1 2 3 4 5)) ==> (1 2 3 1 4 5)
   (insert 1 3 '()) ==> ()
   
   (insertcps 1 3 '(1 2 3 4 5) I) ==> (1 2 3 1 4 5)
   (insertcps 1 3 '() I) ==> ()
   

5. Write a function member? that takes a Scheme object n and a list lon and checks whether n occurs in lon:

    
   (member? 3 '(1 2 3 4 3 3)) ==> #t
   (member? #\x '(#\a #\e #\u #\x #\y)) ==> #t
   (member? 3 '()) ==> #f
   
   (membercps? 3 '(1 2 3 4 3 3) I) ==> #t
   (membercps? #\x '(#\a #\e #\u #\x #\y) I) ==> #t
   (membercps? 3 '() I) ==> #f
   

6. Write a function set? that takes a list of numbers lon and checks whether the list is a set, i.e. has no repeated element. Use member? or membercps? in the definition:

   (set? '(1 2 3 4)) ==> #t
   (set? '()) ==> #t
   (set? '(1 1)) ==> #f
   
   (setcps? '(1 2 3 4) I) ==> #t
   (setcps? '() I) ==> #t
   (setcps? '(1 1) I) ==> #f
   

7. Write a function filter that takes two arguments: a function p that represents a predicate, and a list of numbers lon, and returns a new list that consists of all the elements in lon that satisfy the predicate p:

   (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)
   
   (filtercps (lambda (x k) (k (even? x))) '(1 2 3 4 5 6) I) ==> (2 4 6)
   (filtercps (lambda (x k) (k (> x 8))) '(1 9 2 10 3 11 4 12) I) ==> (9 10 11 12)
   (filtercps (lambda (x k) (k (and (> x 8) (< x 10)))) '(1 9 2 10 3 11 4 12) I) ==> (9)
   

   In other words, when converting to CPS, assume that the predicate has been also converted to CPS.
8. Write a function map that takes a function f and a list of numbers lon, and returns a new list that is similar to lon except that f 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)
   
   (mapcps (lambda (x k) (k (add1 x))) '(1 2 3) I) ==> (2 3 4)
   (mapcps (lambda (x k) (k (* x 3))) '(1 2 3) I) ==> (3 6 9)
   

9. Write a function powerset that takes a list of numbers lon that represents a set and returns the powerset of lon. Use map and mapcps in the definition:

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

10. Write a function takeWhile that takes a predicate p and a list l and returns the prefix of the list up to (but not including) the first element that does not satisfy the predicate:

    (takeWhile even? '(2 4 6 1 8 10 12)) ==> (2 4 6)
    (takeWhile even? '()) ==> ()
    
    (takeWhilecps (lambda (x k) (k (even? x))) '(2 4 6 1 8 10 12) I) ==> (2 4 6)
    (takeWhilecps (lambda (x k) (k (even? x))) '() I) ==> ()
    

11. Write a function dropWhile that takes a predicate p and a list l and returns the suffix of the list starting from (and including) the first element that does not satisfy the predicate:

    (dropWhile even? '(2 4 6 1 8 10 12)) ==> (1 8 10 12)
    (dropWhile even? '()) ==> ()
    
    (dropWhilecps (lambda (x k) (k (even? x))) '(2 4 6 1 8 10 12) I) ==> (1 8 10 12)
    (dropWhilecps (lambda (x k) (k (even? x))) '() I) ==> ()
    

12. Write a function piglatin that takes a string s and converts it to pig latin. The rules for pig latin are the following:
    • If the string starts with a vowel, then add "yay" at the end.
    • Otherwise, take the prefix of consonants, transfer them back to the end, and append "ay".
    Use member?, takeWhile, and dropWhile (or their CPS variants) to define your function:

    (piglatin "able") ==> "ableyay"
    (piglatin "stripe") ==> "ipestray"
    
    (piglatincps "able" I) ==> "ableyay"
    (piglatincps "stripe" I) ==> "ipestray"