[edit]
# List Operators and HOFs

## List Operators

## Higher Order Functions with Lists

## Summary of HOFs

Racket provides useful primitive procedures for lists:

`list-ref`

`list-ref`

takes as arguments a list and a number `n`

and returns the `n`

th item of the list. The first element of the list is indexed as `0`

, meaning it is the `0`

th element of the list. Here's how `list-ref`

is defined:

```
(define (list-ref lst n)
(if (= n 0)
(car lst)
(list-ref (cdr lst) (- n 1))))
```

and here is an example of how it works:

```
-> (define squares (list 1 4 9 16 25))
squares
-> (list-ref squares 3)
16
```

`null?`

`null?`

takes a list as an argument and returns `#t`

if the list is empty. Otherwise, it returns `#f`

:

```
(null? (list 1 3))
#f
(null? '())
#t
```

`length`

`length`

takes a list as an argument and returns the number of items in a list. Here's how `length`

is defined:

```
(define (length items)
(if (null? items)
0
(+ 1 (length (cdr items)))))
```

and here is an example:

```
-> (define odds (list 1 3 5 7))
odds
-> (length odds)
4
```

From here on out, we’ll be mostly using lists and pairs rather than sentences. This is great, since it means we'll be able to take a closer look at how data is represented by Racket. But, this also means that a lot of the important higher order functions we previously defined with sentences must now be rewritten to work with pairs.

`every`

vs. `map`

Recall the HOF `every`

, which takes in a function and a sentence, and returns a sentence with the function applied to every element of the sentence. The equivalent of this HOF using pairs is called `map`

, which it takes in a function and a *list*, and returns a list with the function *mapped* to every element in the list. `map`

is a recursively defined function, as you can see here:

```
(define (map proc items)
(if (null? items)
null
(cons (proc (car items))
(map proc (cdr items)))))
```

The procedure `null?`

for lists is analogous to the procedure `empty?`

for sentences, and checks whether or not the given argument is the empty list. Here are a few example calls to `map`

:

```
-> (map square (list 1 2 3 4 5))
(1 4 9 16 25)
-> (map car (list (cons 1 2) (cons 3 4) (cons 5 6)))
(1 3 5)
```

`keep`

vs. `filter`

We already had a quick glimpse of `filter`

in the `filtered-accumulate`

problem in Homework 2, so you should already have some idea of what the HOF `filter`

should do. `filter`

takes in two arguments, a predicate and a list, and returns a list with only elements that satisfy the predicate. Take a look at the formal definition:

```
(define (filter pred lst)
(cond ((null? lst) null)
((pred (car lst))
(cons (car lst) (filter pred (cdr lst))))
(else (filter pred (cdr lst)))))
```

And here are some examples:

```
-> (filter odd? '(1 2 3 4 5))
(1 3 5)
-> (filter (lambda (x) (> x 2)) '(1 2 3 4 5))
(3 4 5)
```

`accumulate`

Finally, there is the procedure `accumulate`

for sentences. This procedure takes in a function of two arguments, a base case value, and a sentence of values, and continuously combines the values in the list using this operation and ending/starting with the base case value. There are two equivalents to accumulate for lists: `foldl`

and `foldr`

. Both take in a function of two values, a base case value, and a list.

`fold-left`

starts from the last (right-most) element in the list and continuously applies the function recursively until it reaches the first element of the list. Thus, it *folds* to the left. For example, here are the steps to evaluate a call to `foldl`

:

```
-> (foldl cons '() '(1 2 3 4))
... (cons 4 (cons 3 (cons 2 (cons 1 '()))))
(4 3 2 1)
```

Here's another example:

```
-> (define combiner (lambda (x y) (cons (add1 x) y)))
combiner
(foldl combiner '() '(1 2 3 4))
... (combiner 4 (combiner 3 (combiner 2 (combiner 1 '()))))
... (5 . (4 . (3 . (2 . ()))))
(5 4 3 2)
```

On the other hand, `fold-right`

starts from the first (left-most) element in the list and continuously applies the function recursively until it reaches the last element of the list. Thus, it *folds* to the right. Take these calls for example:

```
-> (foldr cons '() '(1 2 3 4))
... (cons 1 (cons 2 (cons 3 (cons 4 '()))))
(1 2 3 4)
-> (foldr + 0 '(1 2 3 4))
... (+ 1 (+ 2 (+ 3 (+ 4 0))))
10
```

We now have two versions of `accumulate`

, where the values of `foldl`

and `foldr`

would only differ when they are called with combiner functions in which order matters.

To make the transition easier, here’s a table illustrating some operations on sentences and their equivalent for lists.

SENTENCE | LIST |
---|---|

`se/sentence` |
`cons/list/append` |

`first` |
`car` |

`bf/butfirst` |
`cdr` |

`last` |
NO EQUIVALENT |

`bl/butlast` |
NO EQUIVALENT |

`count` |
`length` |

`item` (one-indexed) |
`list-ref` (zero-indexed) |

`every` |
`map` |

`keep` |
`filter` |

`accumulate` |
`foldl/foldr` |