[edit]
# Sequences as Conventional Interfaces

## Sequences as Abstractions

## Map

## Filter

**Test Your Understanding**

What do the following expressions return?
## Accumulate

## Enumerate

## Enumerate for Lists

## Enumerate for Trees

## Putting Everything Together

## Takeaways

Let's explore more into the concept of abstraction. One major benefit of using abstraction is that it helps us clean up code and increase readability. Some of the functions that we write for sequences can be generalized and abstracted using Higher Order Functions. This idea can be summarized by the following steps:

- Find a recurring pattern in our code
- Abstract each element in the pattern using HOFs
- Redefine our code with using the abstraction

Here are two example functions that will help demonstrate this idea.

`sum-odd-squares`

takes in a tree containing numbers and adds together the square of each **odd** element in the tree:

```
(define (sum-odd-squares tree)
(cond ((null? tree) 0)
((not (pair? tree))
(if (odd? tree) (square tree) 0))
(else (+ (sum-odd-squares (car tree))
(sum-odd-squares (cdr tree))))))
```

`even-fibs`

takes in a number `n`

, and returns a list of even fibonacci numbers up to and including `n`

:

```
(define (even-fibs n)
(define (next k)
(if (> k n)
nil
(let ((f (fib k)))
(if (even? f)
(cons f (next (+ k 1)))
(next (+ k 1))))))
(next 0))
```

From a first glance at the two functions, we might say "These two functions have nothing in common!". Sure, the functions look completely different but they do share the same logic:

The first step in our idea was to find a recurring pattern in our code. From how we've described recursion in previous lessons, you might dissect `sum-odd-squares`

and `even-fibs`

by base cases and recursive calls. Now, let's see what each function does from a different perspective:

`sum-odd-squares`

:

**enumerates**the leaves of a tree**filters**out the nodes with even data, leaving only odd-valued nodes**maps**the function`square`

onto each of the remaining nodes, and finally**accumulates**the results by adding them together, starting with 0.

`even-fibs`

:

**enumerates**the integers from 0 to`n`

**maps**the function`fib`

onto each integer**filters**out the odd numbers, leaving only even Fibonacci numbers, and finally**accumulates**the results using`cons`

, starting with the empty list.

What pattern do we see here? What at first seemed like two very different functions can now be summarized into four major parts: enumeration, filtering, accumulation, and computation. This is great, because now we can use HOFs to abstract our code. This leads us to step two of our abstraction idea. But before that, let's go over some HOFs.

We went over the `map`

HOF in Lesson 4. You may want to go back for a quick refresher.

`filter`

takes in two arguments, `predicate`

and `sequence`

, and returns the sequence with only the elements of that sequence that satisfy `predicate`

.

```
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
```

What do the following expressions return?

```
(filter (lambda (x) (= (remainder x 2) 0)) (list 0 1 2 3 4 5))
```

```
(filter equal? '(bongo celia momo laval laburrita bongo))
```

`accumulate`

takes in an operation `op`

, a starting value `initial`

, and a `sequence`

. Starting from `initial`

, `accumulate`

uses `op`

to combine all the values in `sequence`

into one. Here are some examples:

```
> (accumulate + 0 '(1 2 3 4 5))
15
> (accumulate append null '((1 2) (3 4) (5 6)))
(1 2 3 4 5 6)
```

Here is how we define `accumulate`

:

```
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
```

How this HOF works could be a little confusing, so here let's write out the evaluation steps explicitly:

Consider the expression:

`(accumulate + 0 (list 1 2 3 4 5))`

The recursive steps will proceed as follows:

`(+ 1 (accumulate + 0 (list 2 3 4 5)))`

`(+ 1 (+ 2 (accumulate + 0 (list 3 4 5))))`

`(+ 1 (+ 2 (+ 3 (accumulate + 0 (list 4 5)))))`

`(+ 1 (+ 2 (+ 3 (+ 4 (accumulate + 0 (list 5))))))`

`(+ 1 (+ 2 (+ 3 (+ 4 (+ 5 (accumulate + 0 (list)))))))`

`(+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0)))))`

`(+ 1 (+ 2 (+ 3 (+ 4 5))))`

`(+ 1 (+ 2 (+ 3 9)))`

`(+ 1 (+ 2 12))`

`(+ 1 14)`

`15`

What does `enumerate`

do? `enumerate`

makes a sequence/list of elements. Our
definition of `filter`

, `map`

, and `accumulate`

are designed for sequences but recall that
one of our functions, `sum-odd-squares`

is called on trees. Instead of making
several versions of accumulate, map, and filter, we can differentiate them by just having
different `enumerate`

functions.

Enumerate will return a list given a lower and upper range.

`(enumerate-interval 0 5)`

returns`(0 1 2 3 4 5)`

`(enumerate-interval 10 13)`

returns`(10 11 12 13)`

You can define enumerate (for lists) as:

```
(define (enumerate-interval low high)
(if (> low high)
nil
(cons low (enumerate-interval (+ low 1) high))))
```

For our tree-version of enumerate, we need a function that accepts a tree, and returns a list with all of the leaves, so that it is compatible with the rest of our HOFs.

```
(define (enumerate-tree tree)
(cond ((null? tree) nil)
((not (pair? tree)) (list tree))
(else (append (enumerate-tree (car tree))
(enumerate-tree (cdr tree))))))
```

Here, we reach our final step in our abstraction idea. With all of the helper functions we have defined, we can define a more modular, readable, and compact version of `sum-odd-squares`

and `even-fibs`

:

```
(define (sum-odd-squares tree)
(accumulate +
0
(map square
(filter odd?
(enumerate-tree tree)))))
```

What did we do here? We find all the leaves in the tree (**enumerate**), keep
everything that is odd (**filter**), square everything left (**map**), and add
up the results (**accumulate**).

Similarly we can define `even-fibs`

as follows:

```
(define (even-fibs n)
(accumulate cons
nil
(filter even?
(map fib
(enumerate-interval 0 n)))))
```

What happened this time? We make a list from 0 to `n`

(**enumerate**), find
the Fibonacci number for all of them (**map**), keep everything that is even
(**filter**), and put them together into a list (**accumulate**).

Sequences provide a strong foundation for abstraction with different
combinations of `map`

, `filter`

, `accumulate`

and `enumerate`

. Even functions
that may look to have different structures like the ones we used here as an
example, we may be able to break them down using similar process signals.