1. The first step in this assignment is to learn the standard higher-order functions on lists---you will use them a lot. Review Sections 2.7.2, 2.8.1, and 2.8.2. Now consider each of the following functions: map filter exists? all? curry uncurry foldl foldr Below, please put the name of each function below to the statement that _most accurately_ describes it. Any given statement may describe more than one function, exactly one function, or no functions. Any given function name must appear in exactly one position. * Each of the functions listed after the arrow *might* return a Boolean: → * Each of the functions listed after the arrow *always* returns a Boolean: → * None of the functions listed after the arrow *ever* returns a Boolean: → 2. Here are the same functions again: map filter exists? all? curry uncurry foldl foldr And again, please put the name of each higher-order function next to the statement that most accurately describes it: * Each of the functions listed after the arrow takes a list and a function. Each one *always* returns a list of *exactly* the same size as the original list: → * Each of the functions listed after the arrow takes a list and a function. Each one *always* returns a list of *at least* the same size as the original list: → * Each of the functions listed after the arrow takes a list and a function. Each one *always* returns a list of *at most* the same size as the original list: → * Each of the functions listed after the arrow *might* return a list: → * _None_ of the functions listed after the arrow *ever* returns a list: → 3. Here are the same functions again: map filter exists? all? curry uncurry foldl foldr And again, please put the name of each higher-order function next to the statement that most accurately describes it: * Each of the functions listed after the arrow takes one argument, which is a function that itself takes two arguments: → * Each of the functions listed after the arrow takes one argument, which is a function: → * Each of the functions listed after the arrow takes more than one argument: → _You are now ready to tackle most parts of exercise 14._ 4. Review section 2.7 from page 112 to page 115. (a) Define function `twice` using `val` and `lambda`, not `define`. (b) Using `lambda`, write an *expression* that evaluates to the absolute-value function. Don't use any definition forms. (*Hint*: you can negate a number $n$ by subtracting it from zero.) 5. Review the difference between `foldr` and `foldl` in section 2.8.1. You may also find it helpful to look at the implementation in code chunk 125b on page 125. (a) Do you expect `(foldl + 0 '(1 2 3))` and `(foldr + 0 '(1 2 3))` to be the same or different? (b) Do you expect `(foldl cons '() '(1 2 3))` and `(foldr cons '() '(1 2 3))` to be the same or different? (c) Look at the initial basis on page 149. Give one example of a function, other than `+` or `cons`, that can be passed as the first argument to `foldl` or `foldr`, such that `foldl` _always returns exactly the same result_ as `foldr`. (d) Give one example of a function, other than `+` or `cons`, that can be passed as the first argument to `foldl` or `foldr`, such that `foldl` _may return a different result_ from `foldr`. _You are now ready to tackle all parts of exercises 14 and 15._ 6. μScheme provides syntactic sugar for records, which are made from cons cells. Review the record syntax in section 2.16.6, which starts on page 183. You may also find it helpful to scan the tree data structure in section 2.6. Given the record definition (record course (room instructor enrollment)) answer these questions: (a) How many arguments does function `make-course` expect? (b) How many arguments does function `course?` expect? (c) Is the following equation a valid algebraic law? That is, does it hold for all values of `n`? (course? (make-course '(Barnum 008) 'Ramsey n)) == #t (d) Is the following equation a valid algebraic law? That is, does it hold for all values of `r`, `i`, and `n`? (course-room (make-course r i n)) == i _You are now ready to tackle the record operations in part (d) of problem 19._ 7. This question builds on the record syntax described in section 2.16.6. Review function composition and currying, which are described in section 2.7.2. Assume you have the following definitions: (record prof (building room courses)) (val rockstar (make-prof 'Halligan 241 '(170))) (val greybeard (make-prof 'Halligan 222 '(105 150TW))) (val electric (make-prof 'Halligan 205 '(105))) (val nearby? (o ((curry =) 'Halligan) prof-building)) Answer these questions: (a) How many arguments does `nearby?` expect, and what values are acceptable? (b) What values may `nearby?` return? (c) What does function `nearby?` do, and how does it work? (d) If I evaluate the expression `(nearby? rockstar)`, what do you expect to happen and why? (e) If I evaluate the expression `(nearby? greybeard electric)`, what do you expect to happen and why? (f) If I evaluate the expression `(nearby? '(Halligan 107B (7)))`, what do you expect to happen and why? _You are now ready to tackle the first three parts of exercise 19, as well as problem **M** below._ 8. Section 2.9.1 on page 129 describes the "third approach" to polymorphism. Here is a (weak) form of equality test: (val equal-on-zero? (lambda (f g) (equal? (f 0) (g 0)))) Suppose function `specialized-set-ops` is passed value `equal-on-zero?`. Answer these questions: (a) Give examples of two different values that might be stored in a set that uses `equal-on-zero?`. (b) Explain in general what sorts of values may be stored in such a set. (c) Give examples of two values that are not actually equal, but that would be considered equal by `equal-on-zero?`. (*Hint*: Look for ideas in previous homeworks.) (d) Does μScheme have a primitive or predefined function that could be used in place of `equal-on-zero?`? Would it give more accurate results? Justify your answer. _You are now ready to tackle the final part of exercise 19._