Name _________________________

CS 60

Rex Worksheet (Worksheet 1)

This worksheet is keyed to the first part of Chapter 2 of the notes and the whole of Chapter 3 (maybe even a bit of Chapter 4). It focuses on list structures, recursion, and functional programming in rex. It is due by class on Thu., Feb. 7, and is worth 25 points.

1. What are the differences between a list and a set?

________________________________________________________.

2. Under what conditions are two lists equal?

________________________________________________________.

3. What is the fundamental list dichotomy?

________________________________________________________.

4. Under what condition(s) are the first and rest of a list not meaningful?

________________________________________________________.

5. What is meant by a variable binding?

________________________________________________________.

6. In the equation [F, S | R] = [7, 11, 13, 17], what are the resulting bindings of F, S, and R?

________________________________________________________.

7. If we bind [A, [B] | C] = [ [3,[4]], [[5]] ], what are the resulting bindings of A, B, and C?

________________________________________________________.

8. What is an example of a list whose length is two but whose leafcount is six?

________________________________________________________.

9. What is meant by a binary relation?

________________________________________________________.

10. If the list L = [3, 5, 7, 11, 13] is considered a partial function, what are L(3), L(0), and L(5)?

________________________________________________________.

11. Suppose f is the rex function such that f(x) = x%4; What is map(f,range(1998,2002))?

________________________________________________________.

12. Suppose superlog is the rex function from Assignment 1 problem 7. What is the value of map(superlog, [3,2,10,8], [243,64,100,64]) ?

________________________________________________________.

13. What is different about the two map functions in problems 11 and 12 above?

________________________________________________________.

14. Using the rex function assoc, what is the value of

assoc("feb", [["jan", 31], ["feb", 28], ["mar", 31]]) ?

________________________________________________________.

15. What is the value of ((x) => x*x+1)(9)?

________________________________________________________.

16. For f(x) = 2*x + 1, what is the value of ((F)=>F(F(5)))(f)?

________________________________________________________.

17. What is a predicate?

________________________________________________________.

18-19. Suppose P is the predicate such that P(x) = (x%5 == 0) and L is bound to the list [3, 5, 7, 11, 15, 19]. What are the values of the following:

some(P, L)_______________________________________________

all(P, L)_______________________________________________

keep(P, L)_______________________________________________

drop(P, L)_______________________________________________

find(P, L)_______________________________________________

find_indices(P, L) ________________________________________

20-25. (Typical midterm-type rex question) Write a function sumSort that accepts a list of lists of numbers as input and outputs the same list, but with the sublists in increasing order by sum. You can assume no two lists will have the same sum and all will be nonempty.

Example:

rex >  sumSort([ [10,4], [1,2,1], [-5,3], [0] ]);
[ [-5,3], [0], [1,2,1], [10,4] ]