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:
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
(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
even-fibs by base cases and recursive calls. Now, let's see what each function does from a different perspective:
squareonto each of the remaining nodes, and finally
fibonto each integer
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,
sequence, and returns the sequence with only the elements of that sequence that satisfy
(define (filter predicate sequence) (cond ((null? sequence) nil) ((predicate (car sequence)) (cons (car sequence) (filter predicate (cdr sequence)))) (else (filter predicate (cdr sequence)))))
(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
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
(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)
enumerate makes a sequence/list of elements. Our
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
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
(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
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.