# 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"
```

Amr A Sabry
Tue Apr 1 08:12:00 PST 1997