If you have not already done so, please take the quiz before continuing with lab.

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) list-of-X -> list-of-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) list-of-X -> list-of-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)))
```
 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 : list-of-number -> list-of-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 : list-of-number -> list-of-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) list-of-X -> list-of-Y
(define (map f l)
(cond
[(empty? l) empty]
[(cons? l)  (cons (f (first l)) (map f (rest l)))]))

(define (double-num n) (* 2 n))
(define (double-nums a-lon) (map double-num a-lon))

(define (lessthan3-num n) (< n 3))
(define (lessthan3-nums a-lon) (map lessthan3-num 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))
```
 Write `double-nums` using `map` and `local`, without a global function `double-num`. If you've read ahead a couple chapters: 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.

 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
 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))…)
```
 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
```
 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.