# CS 1101: Lab 4 (Advanced)

## Lab Motivation and Goals

By the end of this lab, you should be able to:
• Use map and filter, Scheme's loops

You need to use Intermediate Language Level for this lab.

The material in this lab will not be tested in 1101 -- it's is for your educational enrichment only.

## Setup

By now, you've noticed that many of the functions we write over lists have the same flavor. For example, consider the following two functions:

```;; extract-positives : list-of-number -> list-of-number
;; consumes list of num and produces list of all positive nums in list
;;  (uses built-in operator positive?)
(define (extract-positives alon)
(cond [(empty? alon) empty]
[(cons? alon) (cond [(positive? (first alon))
(cons (first alon) (extract-positives (rest alon)))]
[else (extract-positives (rest alon))])]))

;; short-strings : number list-of-string -> list-of-string
;; consumes num and list of string and produces list of all strings shorter than given num
(define (short-strings limit alos)
(cond [(empty? alos) empty]
[(cons? alos) (cond [(< (string-length (first alos)) limit)
(cons (first alos) (short-strings limit (rest alos)))]
[else (short-strings limit (rest alos))])]))
```

These do almost the same thing, minus the test that they use to decide whether or not to keep the first item on the list. Shouldn't we be able to write a helper function that captures all the common code between these two functions? We certainly could, and as a matter of fact, that helper is already built-in: it is called `filter`. Here's the definition of filter:

```   ;; filter : (alpha -> boolean) list[alpha] -> list[alpha]
;; extracts elements of list for which given keep function returns true
(define (filter keep? alst)
(cond [(empty? alst) empty]
[(cons? alst)
(cond [(keep? (first alst))
(cons (first alst) (filter keep? (rest alst)))]
[else (filter keep? (rest alst))])]))
```

Notice a couple of things about filter: it takes a function as an argument; that is denoted in the contract as (alpha -> boolean). This is fine -- Scheme lets you pass operators as inputs to other functions. Notice also that the contract uses the greek letter alpha, rather than a type like number or string. That is because filter can work on lists of any type. We use alpha as a variable over types.

Using filter, we could write our original functions as follows:

```;; extract-positives : list-of-number -> list-of-number
;; consumes list of num and produces list of all positive nums in list
(define (extract-positives alon)
(filter positive? alon))
```

`extract-positives` is fairly easy -- just send the operator `positive?` as the `keep?` parameter.

`short-strings` is a bit harder:

```;; short-strings : number list-of-string -> list-of-string
;; consumes num and list of string and produces list of all strings shorter than given num
(define (short-strings limit alos)
(filter __________ alos))
```

We can't just put ```(< (string-length (first alos)) limit)``` in place of _________, because it is not a function. Yet we can't easily make an outside function for this, because the function (a) can only take one argument according to the filter contract, but (b) needs to use `limit`. To write this, we need to show you how to define functions inside other functions.

```;; short-strings : number list-of-string -> list-of-string
;; consumes num and list of string and produces list of all strings shorter than given num
(define (short-strings limit alos)
(local [(define (short? astr) (< (string-length astr) limit))]
(filter short? alos)))
```

Notice that `short?` looks like any other function definition, but since it is inside `short-strings`, it can refer to the inputs to `short-strings` without taking them as inputs itself. You can put as many definitions as you want between the square brackets of a local (but you can't define the same name more than once).

## Filter exercises

Use filter to write the following programs over dillos (recall that we had `(define-struct dillo (length dead?))`):

1. `dead-dillos`, which consumes a list of dillos and returns a list of the dead dillos from the list.

2. `live-dillos`, which consumes a list of dillos and returns a list of the live dillos from the list.

3. `short-and-dead`, which consumes a list of dillos and returns a list of dead dillos with length less than 5.

## Introduction to Map

Filter is good for extracting some elements from a list, but we've written other kinds of list programs as well. Consider a program like `double-all`, which consumes a list of numbers and returns a list of numbers of the same length, but with every number doubled:

```;; double-all : list-of-number -> list-of-number
;; consumes list of num and returns list with all nums doubled
(define (double-all alon)
(cond [(empty? alon) empty]
[(cons? alon) (cons (* (first alon) 2) (double-all (rest alon)))]))
```

For functions like this, that run some function on every element of a list and return the same size list, Scheme provides a built-in function called `map`:

```   ;; map : (alpha -> beta) list[alpha] -> list[beta]
;; returns list of results from applying function to each element
;;    of the input list
(define (map f alst)
(cond [(empty? alst) empty]
[(cons? alst) (cons (f (first alst))
(map f (rest alst)))]))
```

So, for example, we could write `double-all` as:

```(define (double-all alon)
(local [(define (double n) (* n 2))]
(map double alon)))
```

By combining map and filter, you can write a lot of list programs very compactly.

### Practice Exercises with Map and Filter

Assume that we want to develop an inventory database for an online CD store. For each CD, the database stores its title, artist, price, how many copies are in stock, and its category of music (such as rock, blues, or country). Write a data definition for CD inventories.

1. Write a function `all-titles` that consumes an inventory and produces a list of all titles in the inventory.

2. Write a function `titles-in-stock` that consumes an inventory and produces a list of all titles in the inventory with at least 1 copy in stock.

3. Write a function `restock` that consumes a CD title, number of new copies of that CD and an inventory and produces an inventory in which the named CD has the given number of additional copies (and all other CDs remain the same).

4. Write a function `titles-by` that consumes an artist name and inventory and produces a list of titles of CDs by that artist.

5. Write a function `copies-in-stock` that consumes a CD title, artist name and an inventory and produces the number of copies of that item that are in stock. Return 0 if the named CD isn't in the inventory.

6. Write a function `blues-sale` that consumes an inventory and produces an inventory in which all blues CDs are discounted by 10\%.

7. Write a function `carry-cd?` that consumes a title and artist name and produces a boolean indicating whether that item is in the inventory (whether in or out of stock).

You can make up a whole host of other functions to write for practice. Be creative!