Try Firefox!

SI413 Scheme Lab 5: Recursion with lists vs. map & apply

This lab is to review the use of recursion to compute with lists, and to contrast it with the way map and apply do the same things.
Note: The functions cross, filter-in, filter-out and comes-before? you define in problems 3,4 and 5 are really useful!

  1. Write functions (max-sin-r L) and (max-sin-f L) that both take a list L = (x1 x2 ... xn) and return the largest number amongst sin(x1), sin(x2), ..., sin(xn). The function (max-sin-r L) must be defined recursively, without the aid of map and apply. The function (max-sin-f L) may not use recursion or call any recursive function you write, it must use map and apply instead. Examples:
    > (max-sin-r '(3 4 7 8 10 12))
    > (max-sin-f '(3 4 7 8 10 12))
    > (max-sin-f '(5.5))
    > (max-sin-r '(5.5))

  2. Think about a different function (sin-max L) that takes a non-empty list of numbers L and returns the element of that list whose sin is the largest. For example:
    > (sin-max '(2.5 2.0 1.5 1.0))
    ... because the sin(1.5) = 0.9974949866040544, which is larger than the sines of all the other values. You already know how to write this kind of function recursively. However, think about whether map and apply are much help for this problem ... more specifically, why are they not much help? What else do you need for them to be useful? (To turn in: write a comment in your scheme file, under "Problem 2", that answers this question.)

  3. Write a function called (cross A B) that takes two lists, A and B, and returns the list of all pairs of elements whose first component comes from A and second componant comes from B. For example:
    > (cross '(1 2 3) '(a b))
    ((1 a) (1 b) (2 a) (2 b) (3 a) (3 b))
    > (cross '(hi) '(bye there))
    ((hi bye) (hi there))

    Here are some words of wisdom: Wouldn't it be useful to have a function (pair-with x L) that takes an object x and a list L = (l1 l2 ... lk) and returns the list ((x l1) (x l2) (x l3) ... (x lk))? Both in defining this function and in using it, you have a choice of map/apply and recursion. Think about; what are the tradeoffs?

  4. Write functions (filter-in keep? L) and (filter-out reject? L) that take a predicate and a list and return a list that either keeps only elements that the predicate keep? evaluates to true on or keeps everything except what reject? evaluates to true on. Here are some examples:
    > (filter-in even? '(10 9 8 7 6 5 4 3 2 1))
    (10 8 6 4 2)
    > (filter-out even? '(10 9 8 7 6 5 4 3 2 1))
    (9 7 5 3 1)
    > (filter-out null? '( (a b) () (1 2 3) ("the" "end") () (x y z)))
    ((a b) (1 2 3) ("the" "end") (x y z))
    Note: You'll need to do this by recursion ... at least one of them. However, a clever person could use these to solve the sin-max problem.

  5. The member function in scheme is pretty useful. The call (member x L) searches for x in the list L by taking the cdr of L repeatedly until it either runs out, in which case #f is returned, or until it gets to a point where x is the car of whatever's left of L, in which case this remaining sublist is what's returned. For example:
    > (member 'd '(a b c d e f))
    (d e f)
    > (member 'x '(a b c d e f))
    Using member, write a function comes-before? that takes a list L, and two objects a and b, and returns #t if a comes before b in the list, and #f otherwise. For example:
    > (comes-before? 'mon 'wed '(sun mon tue wed thu fri sat))
    > (comes-before? 'fri 'wed '(sun mon tue wed thu fri sat))

Christopher W Brown
Last modified: Wed Aug 27 09:02:30 EDT 2008