Abstract functions

Instructions for students & labbies: Students use DrScheme, following the design recipe, on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention. There are more exercises here than most students will be able to do during lab, so skip over the ones with qualifiers, if necessary.

filter Review

As a reminder, we've discussed filter. Starting from several examples using specific predicates, we noticed a great deal of similarity. By abstracting away that similarity into a function parameter, we obtained the following definition:

      ; filter : (X -> boolean) [X] -> [X]
      ; Purpose: Returns a list like the one given, except with those
      ; elements not passing the given predicate test removed.
      (define (filter keep? l)
         (cond
            [(empty? l) empty]
            [(cons? l)  (cond
                            [(keep? (first l))
                             (cons (first l) (filter keep? (rest l)))]
                            [else
                             (filter keep? (rest l))])]))

As an alternative, we could note that the above definition repeats the code (filter keep? …). I.e., keep? is an invariant argument. We could choose to avoid that, as follows:

     ; filter : (X -> boolean) [X] -> [X]
     ; Returns a list like the one given, except with those
     ; elements not passing the given predicate test removed.
     (define (filter keep? l)
        (local
           [(define (filter-helper l)
               (cond
                  [(empty? l) empty]
                  [(cons? l)  (cond
                                  [(keep? (first l))
                                   (cons (first l) (filter-helper (rest l)))]
                                  [else
                                   (filter-helper (rest l))])]))]
           (filter-helper l)))

filter exercises

Using DrScheme's "Check Syntax" feature to identify where each variable is bound in the second definition. Recall that when you put your cursor above a binding instance, it will draw arrows to the uses, and when you put your cursor above a use, it will draw an arrow to its binding instance. Using either definition of filter, define a function that takes a list of numbers and returns a list of all the positive numbers in that list.

map Review

We are familiar with writing functions such as the following:

      ; double-nums : [number] -> [number]
      ; Given a list of numbers, return a list of
      ; numbers that are twice the value of the corresponding items in
      ; the original list.
      (define (double-nums a-lon)
         (cond
            [(empty? a-lon) empty]
            [(cons? a-lon)  (cons (* 2 (first a-lon))
                                  (double-nums (rest a-lon)))]))

      ; lessthan3-nums : [number] -> [boolean]
      ; Given a list of numbers, return a list of
      ; booleans that indicate whether the corresponding items in
      ; the original list are less than 3.
      (define (lessthan3-nums a-lon)
         (cond
            [(empty? a-lon) empty]
            [(cons? a-lon)  (cons (< (first a-lon) 3)
                                  (lessthan3-nums (rest a-lon)))]))

Since these functions are so similar, we'd like to package together the similar parts and separate out the different parts. We'll "package" the similar parts as a new function that can take either of the "different" parts as an argument that tells us what to do:

      ; map : (X -> Y) [X] -> [Y]
      (define (map f l)
         (cond
            [(empty? l) empty]
            [(cons? l)  (cons (f (first l)) (map f (rest l)))]))

      ; double-num : number -> number
      (define (double-num n) (* 2 n))
      ; double-nums : [number] -> [number]
      (define (double-nums a-lon) (map double-num a-lon))

      ; lessthan-3-nums : [number] -> [boolean]
      (define (lessthan3-nums a-lon) (map (lambda (n) (< n 3))
                                          a-lon))

map abstracts the general idea of "computing a new element from each old element and building a list of the new elements" away from what specifically you are computing from each element.

Another way to understand map is by the following equation. It describes what map does without the usually extraneous details of how it does it.

      (map f (list x1 … xn)) = (list (f x1) … (f xn))

map exercises

Write double-nums using map and local, without a global function double-num. Write double-nums using map and lambda, without any named function like double-num.

The Big Picture

Abstract functions are both powerful and convenient. By using abstract functions to group all the common similar elements of many functions, we can concentrate on what's different. This allows us to write shorter code that is also clearer and more understandable.

The examples in this lab are certainly not the only abstract functions, but they are among those that are particularly useful because they correspond to common list computations. Because Scheme has lists built in and since these functions are so useful, Scheme has them pre-defined.

Usually, using abstract functions takes the place of following our standard templates. So, what happens to our design recipes? In the short term, while you are still getting used to abstract functions, we strongly recommend that you first follow the design recipe, and then go back and edit your code to use abstract functions where applicable. In the long term, you will learn to identify common patterns before you actually write code and be able to go directly to writing the shorter versions using abstract functions. You will probably find filter and map among the easier ones to use at first. On the other hand, foldr and foldl are more general and take more practice to get comfortable with. You will get practice on homeworks and the next two exams.

foldr

We have written many functions to combine elements of a list, e.g., to sum the numbers in a list and to find the maximum element in a list. In each, we have some value base as the result for the empty list and a function f to combine the first element and the result on all the rest of the elements. Combining all the elements means satisfying the following equation:

      (foldr f base (list x1 x2 … xn)) = (f x1 (f x2 … (f xn base)))

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

This function was discussed in class, but with the name fun-for-l and its arguments in a different order. There we saw this is also equivalent to turning our list template into an abstract function.

foldr exercises

Based upon this equation, what should the following evaluate to? Think about them first, then try them in DrScheme (where foldr is pre-defined). (foldr + 0 (list -1 5 -3 4 2)) (foldr - 0 (list -1 5 -3 4 2)) (foldr cons empty (list -1 5 -3 4 2)) (foldr append empty (list (list 1 2) (list 4) empty (list 8 1 2))) What is the contract for foldr? You should be able to determine this from the equation and examples above. First ask yourself the question assuming the input list is a list of numbers, then generalize. Using foldr, define a function to compute the product of a list of numbers. Using foldr, define map. Define the function my-foldr to satisfy the above equation. As you might expect, it follows the template for a function consuming a list. Test your function against Scheme's built-in foldr to make sure they give the same results for the same inputs. If you have time… Using foldr, define a function to compute whether all elements in a list of numbers are greater than 6. Then generalize this to using foldr to define filter.

More examples

Here's a few more pre-defined abstract functions:

      (andmap f (list x1 … xn)) = (and (f x1) … (f xn))
      (ormap f (list x1 … xn))  = (or (f x1) … (f xn))
      (build-list n f)          = (list (f 0) … (f (sub1 n)))

The following is a quick summary of the abstract functions mentioned in this lab:

• filter -- selects some elements from a list
• map -- applies a function to each list element
• andmap/ormap -- applies a function to each list element and combines the resulting booleans
• build-list -- constructs a list of the given length according to the given function

• foldr/foldl -- combines all elements of a list

Exercises

The following can be defined using some combination of the pre-defined abstract functions. Define a function that, given a list of numbers, returns the sum of all the positive numbers in the list. Define a function that, given a list of anything, determines whether all of the numbers in the list are even. If you have time… (This is from the last lab, but use abstract functions this time, and then compare the function to the one you wrote last week.) Develop a function that, given n and i normally returns the list of length i of numbers up to n: (list n-(i-1) … n-1 n) More concretely, e.g., (nums-upto-help 5 0) ⇒ empty (nums-upto-help 5 2) ⇒ (list 4 5) (nums-upto-help 5 5) ⇒ (list 1 2 3 4 5) (nums-upto-help 6 5) ⇒ (list 2 3 4 5 6) (nums-upto-help 7 5) ⇒ (list 3 4 5 6 7) For simplicity, you may assume that i≤n. This should just follow the template for natural numbers on i. If you have time… Define andmap, which computes whether all elements in a list of booleans are true: (andmap f (list x1 … xn)) = (and (f x1) … (f xn)) First, define it recursively following the list template, then define it using foldr and map, then using only foldr.

foldl

The mathematically inclined might have noticed that foldr

groups the binary operations right-associatively. Thus the "r" in the name. What if we want to group left-associatively? Well, we also have the following:

      (foldl f base (list x1 x2 … xn)) = (f xn … (f x2 (f x1 base))…)

foldl exercises

Based upon this equation, what should the following evaluate to? Think about them, then try them in DrScheme (where foldl is pre-defined). (foldl + 0 (list -1 5 -3 4 2)) (foldl - 0 (list -1 5 -3 4 2)) (foldl cons empty (list -1 5 -3 4 2)) (foldl append empty (list (list 1 2) (list 4) empty (list 8 1 2))) Compare the results to those for foldr. Do (foldr + 0 numlist) and (foldl + 0 numlist) always give the same results? Hint: Think back a couple labs. Define the function my-foldl to satisfy the above equation, testing it against Scheme's built-in foldl. Hint: Use reverse. If you've read ahead a few chapters: Define my-foldl without using reverse. Hint: Use an accumulator.

Other types

Abstract functions are also quite useful. Scheme has lists and their abstract functions built-in, so they get more attention, but the ideas transfer to trees perfectly well.

For example, one definition of binary tree is the following:

      (define-struct node (n left right))

      ; A binary tree of numbers (btn) is
      ; - empty
      ; - (make-node n l r)
      ;   where n is a number and l,r are btns

Tree exercises

If you have time… Define a map-like function on btns. Semi-challenge: Define a foldr-like function on btns. Hint: Whereas foldr on lists took a binary function argument, this one needs a ternary function argument.

Access Permissions

• Set ALLOWTOPICCHANGE = TeachersComp210Group