COMP 210 Lab 8: Abstract Functions

There are many more exercises here than you can do in lab. Do a representative subset.

Review

In class, we were introduced to some abstract functions: map, foldr, and foldr. Three three functions are "abstract" in the sense that they form the common cores of many typical functions on lists. In other words, they provide invariant core of computations, taking other functions as arguments which represent the variant parts of computations.

This lab has exercises on these three abstract functions and asks you to define some additional abstract functions. The current homework introduces another common abstract function on lists, filter.

Summary of map, foldr, foldl
map 
; map : (any1 -> any2) list-of-any1 -> list-of-any2
(define (map f l)
   (cond [(empty? l) empty]
         [(cons? l)  (cons (f (first l))
                           (map f (rest l)))]))

(map f (list x1 x2 ... xn-1 xn))

=

(list (f x1) (f x2) ... (f xn-1) (f xn))
foldr 
; foldr : (any1 any2 -> any2) any2 list-of-any1 -> any2
(define (foldr f base l)
   (cond [(empty? l) base]
         [(cons? l)  (f (first l)
                        (foldr f
                               base
                               (rest l)))]))

(foldr f base (list x1 x2 ... xn-1 xn))

=

(f x1 (f x2 (... (f xn-1 (f xn base)))))
foldl 
; foldl : (any1 any2 -> any2) any2 list-of-any1 -> any2
(define (foldl f base l)
   (cond [(empty? l) base]
         [(cons? l)  (foldl f
                            (f (first l) base)
                            (rest l))]))

(foldl f base l)

=

(f xn (f xn-1 (... (f x2 (f x1 base)))))

Abstract functions vs. templates and recipes

Using abstract functions often results in one-line non-recursive functions representing the variant part of the computation. The recursion is hidden inside the invariant abstract function. Thus, using the abstract functions often replaces the standard recursive templates.

In the short term, while you are still getting used to abstract functions, we strongly recommend that you first follow the design recipe to produce the familiar recursive solutions. 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 map and filter the easier to use at first. 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.

Where do we get those contracts?

In class, we briefly looked at the contract for foldr. Let's review that discussion, adding some details to understand one possible line of thought of obtaining the contract. foldr takes a function of two arguments, a value for the base case, and a list, and it returns something: 

     foldr : (?? ?? -> ??) ?? list-of-?? -> ??
foldr doesn't care what kind of things are in the list, nor of the kinds of things its function argument takes or returns, nor what the base case value is: 
     foldr : (any any -> any) any list-of-any -> any
foldr's return value can come from two places: the base case value and the return value of foldr's function argument. So, each of these must be the same kind of thing. Let's annotate the contract to clarify this sameness: 
     foldr : (any any -> any2) any2 list-of-any -> any2
Furthermore, the second argument of foldr's function argument has to be the same kind of thing, since that's where the recursive call is located: 
     foldr : (any any2 -> any2) any2 list-of-any -> any2
Also, the input list elements are used as the first argument to foldr's function argument: 
     foldr : (any1 any2 -> any2) any2 list-of-any1 -> any2
But, the input list elements need not be the same kind of thing as the eventual result, even though in many examples they are. E.g., foldr can be used to define the length of a list of symbols. 
     foldr : (any2 any2 -> any2) any2 list-of-any2 -> any2
If you're a mathematician, and thus like Greek letters, you may prefer a more traditional form: 
     foldr : (α β -> β) β list-of-α -> β

Contract exercise

Derive the given contracts for map and foldl in the same way.

An aside

That line of reasoning is very close to the steps a type inference system would go through to assign such a contract. In later courses, it will be important to understand the related ideas of type checking and type inference.

foldr vs. foldl

foldr embodies reverse accumulation on lists. It first applies the given function to the rightmost elements of the given list. E.g., to sum (list 7 3 -12 2 9), 

     7   3   -12   2   9
                      +0
                      =9
                  +9
                 =11
             +11
             =-1
       +-1
        =2
    +2
    =9

foldl embodies forward accumulation on lists. It first applies the given function to the leftmost elements of the given list. 

     7   3   -12   2   9
    +0
    =7
        +7
        =10
             +10
             =-2
                 +-2
                  =0
                      +0
                      =9

As we've seen before, these are sometimes essentially the same thing. In particular, given a function that is both associative and commutative, they give the same result. Reminder: A function f is associative if (f (f x y) z) = (f x (f y x)). A function f is commutative if (f x y) = (f y x).

Exercises

map, foldr, and foldl exercises

  1. Develop add-2-to-each using map: 

           (add-2-to-each (list 3 8 -1))   returns   (list 5 10 1)

  2. Develop add-n-to-each using map: 

           (add-n-to-each 5 (list 3 8 -1))   returns   (list 8 13 4)

  3. Try these as samples of when foldr and foldl behave the same. These should come as no surprise, since we've previously written these functions each with reverse and forward accumulation. 

           (foldr + 0 (list 7 3 -12 2 9))
       (foldl + 0 (list 7 3 -12 2 9))

       (foldr * 1 (list 7 3 -12 2 9))
       (foldl * 1 (list 7 3 -12 2 9))

  4. Using foldr or foldl, define a function to compute whether all elements in a list of booleans are true. (This is commonly called andmap.) (Note: and is not a function, but actually a special piece of syntax, since it doesn't always evaluate its second argument! You'll need to wrap it inside a lambda.)

  5. Using foldr or foldl, define a function to compute whether any elements in a list of booleans are true. (This is commonly called ormap.)

  6. Using foldr or foldl, write a function which takes a list of anything and returns the length of the list. (As we've already seen, this is commonly called length.)

  7. For the curious (since we've barely introduced visitors)... Repeat those last three exercises using the visitor-style version of foldr: 

           ;; A Visitor is a structure made up of two functions
       ;; One for the base case and 
       ;; one for the inductive case
       (define-struct Visitor (fBase fInduct))

       ;; execute: list-of-any1 Visitor any2 --> any3
       ;; Executes ("accepts") the visitor on the list
       ;; returning the result.
       ;; param is passed to the visitor unmodified.
       (define (execute  a-list visitor param)
          (cond
             [(empty? a-list) ((Visitor-fBase visitor) a-list param)]
             [(cons? a-list)  ((Visitor-fInduct visitor) a-list param)]))

       ;; Structure used for both foldrList and foldlList
       ;; f is the inductive case function
       ;; base is the base case value, of type any2
       (define-struct FoldInp (f base))

       ;; foldrVisitor implements foldr as a visitor
       (define foldrVisitor
         (make-Visitor
          ;; empty FoldInp --> any2
          ;; returns the base case value
          (lambda (a-list foldInp)
            (FoldInp-base foldInp))
          ;; non-empty-list-of-any1 FoldInp --> any2
          ;; applies the inductive case function to first and 
          ;; the recursive result and returns the result.
          (lambda (a-list foldInp)
            ((FoldInp-f foldInp) (first a-list) (execute (rest a-list) foldrVisitor foldInp)))))

  8. Try these as a sample of when they don't. First, figure out what they should do, and then use DrScheme to confirm. 

           (foldr / 1 (list 7 3 -12 2 9))
       (foldl / 1 (list 7 3 -12 2 9))
       
           (foldr - 0 (list 7 3 -12 2 9))
       (foldl - 0 (list 7 3 -12 2 9))
       
           (foldr cons empty (list 7 3 -12 2 9))
       (foldl cons empty (list 7 3 -12 2 9))
       
           (foldr append empty (list 7 3 -12 2 9))
       (foldl append empty (list 7 3 -12 2 9))

  9. Develop dot-product, which takes in two lists of n numbers (a1 a2 ... an) and (b1 b2 ... bn) and returns a1×b1 + a2×b2 + an×bn, for any n≥0. (What are some trivial test cases?)

    Hint: The built-in map actually can take in a binary function and two lists of arguments (or a ternary function and three lists, etc.).

  10. A previous lab described the prefix-sums function: 

           (prefix-sums (list 8 7 3))      returns    (list 8 15 18)
       (prefix-sums (list 1 8 7 3))    returns    (list 1 9 16 19)
       (prefix-sums (list 1 1 1 1))    returns    (list 1 2 3 4)

    One way of computing this fits very nicely with abstract functions. From the first two example uses, you should see that the previous add-n-to-each is useful. Finish the function with foldr or foldl, as appropriate.

Other abstract functions

These are certainly not the only abstract functions, but map, filter, foldr, and foldl have proven to be particularly useful because they correspond to common forms of computations on lists. Because Scheme has lists built in and these functions are so useful, Scheme has them predefined. But the same ideas are also useful on other data structures.

First, do the following exercises in our old non-visitor style. Then, repeat, but using visitors.

  1. Consider the idea of iterating a function: for instance, if I repeatedly double 3, I get 6, then 12, then 24, etc. That is, I take the output of a function, and again apply the function to that.

    Iterating square twice, starting with 5, yields (square (square 5)) = 625. If I had a function remove-max: list -> list, then iterating that three times starting with (list 7 18 2 9 3) means 

           (remove-max (remove-max (remove-max (list 7 18 2 9 3))))
       =
       (list 2 3)
    In general, iterating some function f three times starting with x means (f (f (f x))).

    Develop the function iterate, which takes a function f, a natural number n, and an initial input to the function x, and iterates the function n times. Don't forget to determine its general contract.

  2. For the curious... Develop a second version of iterate. Between the two versions, one should be tail-recursive, while the other isn't.

  3. Using iterate, develop remove-first-n, which takes a number n and list, and returns the list with the first n items removed. (Of course, an error would result if the list had fewer than n items.)

  4. Develop a folding function for binary trees. 

           ; A binary tree is either
       ;  - (make-EmptyTree)
       ;  - (make-NETree n left right),
       ;    where n is anything, and left and right are binary trees.
       (define-struct EmptyTree ())
       (define-struct NETree (n left right))

       ; The singleton empty tree.
       (define emptytree (make-EmptyTree))

    It takes a ternary (i.e., 3-input) function and a base value. Don't forget to determine its general contract. 

           (fold + 0 (make-NETree 5 (make-NETree 6 emptytree emptytree)
                                (make-NETree 7 emptytree emptytree)))
       =
       18

  5. Using your folding function on binary trees, define a function which computes the height of a tree. This is very similar to computing the length of a list. 

           (height (make-NETree 5 (make-NETree 6 emptytree emptytree)
                              (make-NETree 7 emptytree emptytree)))
       =
       2
       
           (height emptytree)
       =
       0