Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

Many functions we've written fit this pattern, although this fact might not be obvious at first.

Exercises

  1. Wiki Markup
    Based upon the preceding equation (\[1\]), what should the following evaluate to? Think about them first, then try them in DrScheme (where {{foldr}} is pre-defined).
    1. (foldr + 5 (list -1 5 -3 4 2))
    2. (foldl + 5 (list -1 5 -3 4 2))
    3. (foldr - 5 (list -1 5 -3 4 2))
    4. (foldl - 5 (list -1 5 -3 4 2))
    5. (foldr cons empty (list -1 5 -3 4 2))
    6. (foldl cons empty (list -1 5 -3 4 2))
    7. (foldr append empty (list (list 1 2) (list 4) empty (list 8 1 2)))
    8. (foldr append empty (list (list 1 2) (list 4) empty (list 8 1 2)))
  2. What is the contract for foldr? For foldl? You should be able to determine this from the equations and the examples above.
    (We also covered the typing of foldr in lecture.) Hint: First, determine the type of foldr and foldl assuming the input list is a list of numbers, and then generalize.
  3. Using foldr, define a function to compute the product of a list of numbers. Do the same for foldl.
  4. Using foldr, define map. (Also done in lecture.) Do the same for foldl.
  5. Define the function Foldr to satisfy equation (1) above. As you might expect, it follows the template for a function consuming a list. (It was also done in lecture.) Test your function against Scheme's built-in foldr to make sure they give the same results for the same inputs.
  6. Define the function Foldl to satisfy equation (2) above. As you might expect, it follows the template for a function consuming a list. Test your function against Scheme's built-in foldl to make sure they give the same results for the same inputs.
  7. Define a function to compute whether all elements in a list of numbers are greater than 6. Write two version versions, one using foldr and one using foldl, choosing suitable names (distinct from filter for each.
    Then generalize both definitions to define filter. Are your two filter functions identical? Hint: look at computations that generate errors.
  8. Define a function that, given a list of numbers, returns the sum of all the positive numbers in the list. Write two versions, one using foldr and one using foldl.
  9. Without using explicit recursion, develop a function upfrom that, given i and n returns the list of length i of numbers up to n.

...