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)*.

- 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

- 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) ==> ()

- 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) ==> ()

- 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) ==> ()

- 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

- 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

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

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

- 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) ==> ()

- 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) ==> ()

- 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".

*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"

Tue Apr 1 08:12:00 PST 1997