1. The first step in this assignment is to learn the standard
    higher-order functions on lists, which you will use a lot.
    Suppose you need a list, or a Boolean, or a function---what can
    you call?

    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

    Put each function into exactly one of the following four categories:

    **(B)** Always returns a Boolean  
    **(F)** Always returns a function  
    **(L)** Always returns a list  
    **(A)** Can return anything (including a Boolean, a function, or a list)

    After each function, write (B), (F), (L), or (A):

         map  

         filter  

         exists?  

         all?  

         curry  

         uncurry  

         foldl  

         foldr



 2. Here are the same functions again:

          map  filter  exists?  all?  curry  uncurry  foldl  foldr

    For each function, say which of the following five categories best
    describes it.  Pick the most specific category (e.g., (S) is more
    specific than (L) or (M), and all of these are more specific than (?)).

    **(S)** Takes a list & a function; returns a list of *exactly* the same size  
    **(L)** Takes a list & a function; returns a list of *at least* the same size  
    **(M)** Takes a list & a function; returns a list of *at most* the same size  
    **(?)** Might return a list  
    **(V)** Never returns a list

    After each function, write (S), (L), (M), (?), or (V):

         map  

         filter  

         exists?  

         all?  

         curry  

         uncurry  

         foldl  

         foldr



 3. Here are the same functions again:

          map  filter  exists?  all?  curry  uncurry  foldl  foldr

    Put each function into exactly one of the following categories. Always pick
    the most specific category (e.g. (F2) is more specific than (F)).

    **(F)** Takes a single argument: a function  
    **(F2)** Takes a single argument: a function *that itself takes two arguments*  
    **(+)** Takes more than one argument

    After each function, write (F), (F2), or (+):

         map  

         filter  

         exists?  

         all?  

         curry  

         uncurry  

         foldl  

         foldr


    _You are now ready to tackle most parts of exercise 29._

   


 4. Review the difference between `foldr` and `foldl` in section 2.8.1.
    You may also find it helpful to look at their implementations in
    section 2.8.3, which starts on page 131; the implementations are
    at the end.

    (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, which is summarized on 99.
        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 29 and 30._

 5. Read the third [*Lesson in Program Design*](../design/lessons.pdf): 
    Higher-Order Functions.  The lesson mentions a higher-order
    function `flip`, which can convert `<` into `>`, among other
    tricks.  Write as many algebraic laws as are needed to specify `flip`:

    

 6. Review function composition and currying, as described in
    section 2.7.2, which starts on page 127.  Then judge the
     _proposed_ properties below, which propose equality of
     functions, according to these rules:

       - Assume that names `curry`, `o`, `<`, `*`, `cons`, `even?`,
         and `odd?` have the definitions you would expect, but that
         `m` may have any value.

       - Each property proposes to equate two functions.  If the functions
         are equal---which is to say, when both sides are applied to
         an argument, they always produce the same result---then mark
         the property **Good**.  But if there is any argument on which the
         left-hand side produces *different* results from the right,
         mark the property **Bad**.
     
     Mark each property **Good** or **Bad**:

        ((curry <) m)     == (lambda (n) (< m n))

        ((curry <) m)     == (lambda (n) (< n m))

        ((curry cons) 10) == (lambda (xs) (cons 10 xs))

        (o odd?  (lambda (n) (* 3 n))) == odd?

        (o even? (lambda (n) (* 4 n))) == even?

    _You are now ready to tackle the first three parts of exercise 38,
    as well as problem **M** below._

 7. Read about association lists in section 2.3.8, which starts on page 107.
    Given the definition

        (val mascots 
           '((Tufts Jumbo) (MIT Beaver) (Northeastern Husky) (BU Terrier)))
        
    Say what is the value of each of these expressions:

        (find 'Tufts   mascots)
        (find 'MIT     mascots)
        (find 'Harvard mascots)
        (find 'MIT (bind 'MIT 'Engineer mascots))

    _You are ready to use association lists in the **V** family of
    problems below._