Chapter 2.2 (Hierarchical Data and the Closure Property)

Thus, Pairs provide the primitive glue from which we can construct compound data objects. This can be visualized like this:

a6e79771030e5a469f1871e6f8bc6546.png

This is called box-and-pointer notation. We can also create pairs from pairs, and visualize that as follows:

d4ab24561402cd3cbb89158abc6d904c.png

This ability to create pairs from pairs is the essence of list structure. We refer to this ability as the closure property of cons, (not to be confused with closures in functional programming, where a closure is an implementation technique for representing procedures with free variables).

In general, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation.

Representing Sequences

One of the useful structures we can build with pairs is a sequence, an ordered collection of data objects. The standard way of representing these is the following: 6a3e9fd6f70475938fec12a0ed157f52.png

This is basically a linked-list implementation. The car of each pair is the corresponding item, while the cdr of the pair is the next pair in the chain. The cdr of the final pair points to a distinguished value that is not a pair. This can be thought of as an empty list. The above can be constructed as follows:

(cons 1 (cons 2 (cons 3 (cons 4 nil))))

But this becomes unreadable fast, so we prefer:

list(1 2 3 4)

List Operations The use of pairs to represent lists allows us for multiple programming techniques with which to manipulate the list. For example:

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

Which returns the $n^{th}$ item of a list by recursively applying cdr. Or:

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

Which returns the length of a list. It uses null? to check if the current item represents an empty list. Or

(define (append list1 list2)
	(if (null? list1)
	list2
	(cons (car list1) (append (cdr list1) list2))))

Which appends two lists. It recursively checks if the first list is empty. If so, it returns the other list. Otherwise, it appends the first item of list1 onto the result append recursively with the cdr of list1.

Exercise 2.17 Define a procedure last-pair that returns the list that contains only the last element of a given (nonempty) list.

(define (last-pair list)
	(if (null? (cdr list))
	(car list)
	(last-pair (cdr list))))

Exercise 2.18 Define a procedure reverse that takes a list as argument and returns a list of the same elements in reverse

(define (reverse list)
	(if (null? list)
	list
	(cons (reverse (cdr list)) (car list))))

Exercise 2.19 Consider the change-counting program from waaay back. It would be nice to easily change the currency used by supplying a list. Rewrite the cc procedure so its second argument is a list as follows:

(define us-coins (list 50 25 10 5 1))
(define uk-coins (list 100 50 20 10 5 2 1 0.5))

(cc 100 us-coins)

(define (cc amount coin-values)
	(cond ((= amount 0) 1)
		  ((or (< amount 0) (no-more? coin-values)) 0)
		  (else
			(+ (cc amount
					(except-first-denomination
					coin-values))
				(cc (- amount
						(first-denomination
						coin-values))
					coin-values)))))

Define the procedures first-denomination, except-first-denomination and no-more? in terms of applying to list structures.

(define (first-denomination list)
	(car list))
(define (except-first-denomination list)
	(cdr list))
(define (no-more? list)
	(= list null?))

Exercise 2.20 Use the dotted-tail notation to write a procedure same-parity that takes one or more integers and returns a list of all the arguments that have the same parity as the first argument:

(same-parity 1 2 3 4 5 6 7)
// (1 3 5 7)

(define (same-parity . xs)
	(define (helper pred xs)
		(cond ((null? xs) xs)
 			  ((pred (car xs)) (cons (car xs)
						(helper pred (cdr xs)))))
			  (else (helper pred (cdr xs))))
	(cond ((null? xs) xs)
		  ((even? (car xs) (helper even? xs))
		  (else (helper odd? xs)))))

We define a helper function that takes as arguments a predicate even? or odd? and a list. If the list is empty, we return the empty list. If the predicate applied to the first element of the list is true we cons that element to the result of recursively calling the helper method with the rest of the list. If not, we continue with calling the helper method with the rest of the list.

Mapping over lists One extremely useful operation is to apply some transformation to each element in a list and generate the list of results:

(define (scale-list items factor)
	(if (null? items)
		'()
		(cons (* (car items) factor)
			  (scale-list (cdr items) factor))))

We use ‘() instead of nil, as this dialect of lisp (guile) works that way.

This concept is so prevalent, there is a higher-order function called map that does just this:

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

So we can define scale-list using map:

(define (scale-list items factor)
	(map (lambda (x) (* x factor)) items))

Exercise 2.21 The procedure square-list takes a list of numbers as arguments and squares them. Build 2 definitions, one without, and one with map

(define (square-list items)
	(if (null? items)
	'()
	(cons (* (car items)(car items)) (cdr items))))

(define (square-list items)
	(map (lambda (x) (* x x)) items))

Exercise 2.22 Weird shit Exercise 2.23 The procedure for-each is similar to map. However it returns nothing, it just applies the procedure to the elements. Give an implementation of for-each

(define (for-each proc items)
	(if (null? items)
	'()
	(proc (car items))
	(for-each proc (cdr items))))

2.2.2 Hierarchical Structures

So knowing we can make pairs with pairs, it stands to reason we can make lists with lists. And indeed we can, (cons (list 1 2) (list 3 4)) is valid syntax and represents the list ((1 2) 3 4). Important that the length of this list is 3, not 2. The list (1 2) is added as a single element to the list containing 3, and 4.

You can also think of sequences whose elements are itself sequences is as trees. 6ed7b0292a7c6946158c21950ef79e44.png

Recursion is a natural tool for dealing with tree structures, since we can often reduce operations on trees to operations on their branches, and so on, until we reach the leaves of a tree. For example, applying length to the list in question would return 3:

(define x (cons (list 1 2) (list 3 4)))
(length x)
3

But if we want to count how many leaves there are, we would need a recursive function:

(define (count-leaves x)
	(cond ((null? x) 0)
		  ((not (pair? x)) 1)
		  (else (+ (count-leaves (car x))
				   (count-leaves (cdr x))))))

If $x$ is empty, we return 0. If $x$ is not a pair, it is a single element, so we return 1. Otherwise count the leaves of the car and the cdr of c and add those together.

Exercise 2.24 Suppose we evaluate the expression (list 1 (list 2 (list 3 4))). Give the result printed by the interpreter, the corresponding box-pointer structure and the interpretation as a tree. Interpreter: $2 = (1 (2 (3 4))) Box-and-pointer: b1468b5bd61fb9ed1a34b0f1932d41cc.png Tree: 927527d5ad8d67879e9dd700d32c5ca1.png

Exercise 2.25 Give combinations of cars and cdrs that will pick 7 from each of the following lists: (1 3 (5 7) 9), ((7)), (1 (2 (3 (4 (5 (6 7))))))

1.
(define x (list (1 3 (list 5 7) 9))
(cdr (car (cddr x)))
// 7

2.
(define x (list (list 7)))
(car (car x))
// 7

3.
(define x (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))
(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr x))))))))))))
// 7

Exercise 2.26 Suppose we define $x$ and $y$ to be two lists

(define x (list 1 2 3))
(define y (list 4 5 6))

What does the interpreter print when evaluating the following:

(append x y)
// (1 2 3 4 5 6)

(cons x y)
// ((1 2 3) 4 5 6)

(list x y)
((1 2 3)(4 5 6))

Exercise 2.27 Modify your reverse procedure of Exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed, and with all sublists deep-reverted as well.

(define (reverse list)
	(if (null? list)
	list
	(cons (reverse (cdr list)) (car list))))

(define (deep-reverse list)
	(if (pair? x)
	(map deep-reverse (reverse x))
	x))

Exercise 2.28 Write a procedure fringe that takes as arguments a tree and returns all the leaves of the tree from left to right order such that:

(define x (list (list 1 2)(list 3 4)))
(fringe x)
//(1 2 3 4)

That is basically a flatmap (although not precisely according to Claude..)

The key differences:

  • flatmap applies a transformation function to each element before flattening, while fringe doesn’t transform the elements themselves
  • flatmap typically flattens only one level of nesting, while fringe completely flattens a tree of arbitrary depth
  • fringe specifically targets tree structures, while flatmap is more general-purpose
(define (fringe x)
	(cond ((null? x) x)
		  ((pair? (car x)) (append (fringe (car x))(fringe (cdr x))))
		  (else (cons (car x)) (fringe (cdr x)))))

Exercise 2.29 Given:

(define (make-mobile left right)
	(list left right))

(define (make-branch length structure)
	(list length structure))

a. Write the corresponding selectors left-branch, and right-branch which return the branches of a mobile, and branch-length, and branch-structure, which return the components of a branch.

(define (left-branch mobile)
	(car mobile))
(define (right-branch mobile)
	(cdr mobile)
(define (branch-length branch)
	(car branch))
(define (branch-structure branch)
	(cdr branch))

b. Using the selectors, define a procedure total-weight that returns the total weight of a mobile

(define (branch-weight branch)
	(if (number? (branch-structure branch))
	(branch-structre branch)
	(branch-weight (branch-structure branch))))
(define (total-weight mobile)
	(+ (branch-weight (left-branch mobile))
	   (branch-weight (right-branch mobile))))

Mapping over trees Just as map is a powerful abstraction for dealing with sequences, map together with recursion is powerful in dealing with trees. For instance the tree alternative to scale-list is as follows:

(define (scale-tree tree factor)
	(cond ((null? tree) '())
		  ((not (pair? tree)) (* tree factor))
		  (else (cons (scale-tree (car tree) factor)
					  (scale-tree (cdr tree) factor)))))

The plan for iterating over a tree is similar to the count-leaves procedure, which is in general:

  1. If the tree is empty, return something that is equivalent to nothing (0, empty list, etc)
  2. If the tree is not a pair (i.e. a single number), return something that is equivalant to a single value (the value itself, or 1 when counting)
  3. else, apply this function recursively to both the left and right side of this tree.

Exercise 2.30 Define a procedure square-tree analogous to the square-list procedure of 2.21. Directly

(define (square-tree x)
	(cond ((null? x) '())
		  ((not (pair? x)) (* x x))
		  (else (cons (square-tree (car x))
					  (square-tree (cdr x))))))

Using map and recursion

(define (square-tree x)
	(map (lambda (x)
		(if (pair? x)
			(square-tree x)
			(* x x)))
	x))

Exercise 2.31 Abstract the answer to 2.30 to produce a procedure tre-e-map that takes a procedure as input

Directly

(define (tree-map f tree)
	(cond ((null? tree) '())
		  ((not (pair? tree)) (f tree))
		  (else (cons (tree-map f (car tree))
					  (tree-map f (cdr tree))))))

Using map and recursion

(define (tree-map f tree)
	(map (lambda (x)
		(if (pair? x)
		(tree-map f x)
		(f x)))
	tree))

Exercise 2.32 We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3) then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

The definition given has two parts:

  1. Base case -> The Collection of all available subsets of an empty set is only the empty set.
  2. Recursive case -> The collection of all available subsets of a set $S$ with element $x$ added is the collection of subsets of $S$ with $x$ added to each of them.
(define (subsets s)
	(if (null? s)
		(list '())
		(let ((first-item (car s))
			  (subsets-rest (subsets (cdr s))))
			(append subsets-rest
				(map (lambda (set) (cons first-item set))
					  subsets-rest)))))

So this works as follows:

  1. The base-case, if the set is empty, we return an empty list
  2. Otherwise, we extract the first item in the set first-item and recursively calculate the list of subsets of the rest of the set subsets-rest. We then create new subsets by adding the first item to each subset in subsets-rest using a lambda function. Lastly we append the original subsets-rest with the result of the lambda function.
For S = {1, 2, 3}, the execution would be:
Call (subsets '(1 2 3))
Extract first-item = 1
	Call (subsets '(2 3)) recursively
	Extract first-item = 2
		Call (subsets '(3)) recursively
		Extract first-item = 3
			Call (subsets '()) recursively
			Returns '(())
		Create new subsets with 3: '((3))
		Return '(() (3))
	Create new subsets with 2: '((2) (2 3))
	Return '(() (3) (2) (2 3))
Create new subsets with 1: '((1) (1 3) (1 2) (1 2 3))
Return '(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

2.2.3 Sequences as Conventional Interfaces

So far, we’ve stressed how data abstraction permist us to design programs without being enmeshed in the details of data representations. In this section we introduce another powerfl design principle for working with data structures. The use of conventional interfaces. Consider, for example, the following procedure, analogous to count-leaves which computes the sum of the squares of the leaves that are odd:

(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))))))

On the surface, this is very different from the following one, which constructs a list of all the even Fibonacci numbers $Fib(k)$ where $k$ is less than or equal to a given integer $n$:

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

Despite that the structure seems to be extremely different, the more abstract description of the two reveals great similarities:

sum-odd-squares even-fibs
Enumerate the leaves of a tree Enumerate integers from 0 to n
Filter them, selecting the odd ones Computes the fibonacci for each integer
Square each of the selected ones Filter them, selecting the even ones
Accumulate the results using +, starting at 0 Accumulate the results using cons, starting with ()

You can kind of conceptualize this as a stream of data, flowing through one or more transformations. The “problem” is that the procedures above do not reflect this flow-like structure very well. Ideally you would want to write them in such a way where this would be visible, like (in pseudocode F#-ish):

(define (even-fibs n)
	(enumerate 0 n)
	|> (Compute fibonacci)
	|> (Filter even)
	|> Accumulate cons '())

(define (sum-odd-squares tree)
	(enumerate tree)
	|> (Filter odd)
	|> (Compute square)
	|> Accumulate + 0)

Sequence Operations The key to organizing programs to more clearly reflect this flow is to concentrate on the “signals” that flow. If we represent these as lists, then we can use list operations. Taking sum-odd-squares as an example, computing the square of a list of numbers is as easy as (map square list). Filtering requires a bit more code, but is conceptually quite easy:

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

In essence, if the sequence is empty, we return the empty list. If the result of applying the predicate to the first element of the list is true, we cons that element to the result of applying filter to the result of filtering the rest of the list. If it is false, we just drop this element and return the result of applying filter to the rest of the list.

An Accumulator we already built in a previous chapter, but for completeness:

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

All that remains is to enumerate a sequence of elements to be processed.

(define (enumerate-interval lo hi)
	(if (> lo hi)
	'()
	(cons lo (enumerate-interval (+ lo 1) hi))))

And to enumerate over leaves we just take the fringe process we created earlier (we just rename it):

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

Using these methods we can reformulate sum-odd-squares:

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

This kind of modual construction (even though in Lisp it is still quite unreadable imo) is a powerful strategy for controlling complexity. Besides this, the general set-up of methods such as filter and accumulate allows us to mix-and-match these standard elements to create different flows. For example, we can also calculate the product of the quares of the odd integers in a sequence using the exact same pieces:

(define (product-of-squares-of-odd-elements sequence)
	(accumulate * 1 (map square (filter odd? sequence))))

Taking it even further, we can also formulate conventional data-processing applications in terms of these sequence operations.

Suppose we have a sequence of personnel records and we want to find the salary of the higest-paid programmer.

Then we can write:

(define (salary-of-highest-paid-programmer records)
	(accumulate max 0 (map salary (filter programmer? records))))

Which is very understandable from just reading.

Exercise 2.33 Fill in the missing expressions

(define (map p sequence)
	(accumulate (lambda (x y) (cons (p x) y)) '() sequence))

(define (append seq1 seq2)
	(accumulate cons seq1 seq2)

(define (length sequence)
	(accumulate (lambda (x n) (+ n 1)) 0 sequence))

Exercise 2.34 Evaluating a polynomial in $x$ at a given value of $x$ can be formulated as an accumulation. A polynomial is evaluated using a well-known algorithm called Horner’s rule which basically does:

We start with $a_n$, multiply by $x$, add $a_{n-1}$, multiply by $x$, etc. until we reach $a_0$.

Produce a procedure that implements this:

(define (horner-eval x coefficient-sequence)
	(accumulate (lambda (this-coeff higher-terms) (+ (* higher-terms x) this-coeff)) 0 coefficient-sequence))

Exercise 2.35 Redefine count-leaves from Section 2.2.2 as an accumulation.

// Original
(define (count-leaves x)
	(cond ((null? x) 0)
		  ((not (pair? x)) 1)
		  (else (+ (count-leaves (car x))
				   (count-leaves (cdr x))))))

// Accumulation
(define (count-leaves t)
	(accumulate + 0 (map (lambda (x) 1) (enumerate-tree t))))

// Other accumulation
(define (count-leaves t)
	(accumulate (lambda (x n) (+ n 1)) 0 (enumerate-tree t)))

The difference in these two, is that in the first procedure, the sequence gets flattened into nothing more than a list of 1’s, which can then be easily added using +. The second method leaves the sequence in its original state, opting for a more difficult accumulation function.

Exercise 2.36

(define (accumulate-n op init seqs)
	(if (null? (car seqs))
	'()
	(cons (accumulate op init (map car x))
		  (accumulate-n op init (map cdr x)))))

In essence we cons the result of accumulating the first element of every sub-sequence (map car x) into the result of recursively calling this function with the rest of all the sublists (map cdr x).

Exercise 2.37 Given matrix algebra and the fact that a matrix like:

$$ \begin{bmatrix} 1 & 2 & 3 & 4 \\ 4 & 5 & 6 & 6 \\ 6 & 7 & 8 & 9 \end{bmatrix} $$

can be represented as the sequence ((1 2 3 4)(4 5 6 6)(6 7 8 9)) define the following procedures:

(define (dot-product v w)
	(accumulate + 0 (map * v w)))
(define (matrix-*-vector m v)
	(map (lambda (u) (dot-product u v)) m))
(define (transpose mat)
	(accumulate-n cons '() mat))
(define (matrix-*-matrix m n)
	(let ((cols (transpose n)))
		(map (lambda (r)
			(map (lambda (c)
				(dot-product r c))
				cols))
		m)))

Exercise 2.38 The current accumulate is also known as fold-right, as it combines the first element of the sequence with the result of the result of the elements to the right. There is also fold-left which is similar, but it combines elements working in the opposite direction.

(define (fold-left op initial sequence)
	(define (iter result rest)
		(if (null? rest)
		result
		(iter (op result (car rest))
		      (cdr rest))))
	(iter initial sequence))

What are the values of:

(fold-right / 1 (list 1 2 3)) => 3/2
(fold-left / 1 (list 1 2 3)) => 1/6
(fold-right list '() (list 1 2 3)) => (1 (2 (3 ())))
(fold-left list '() (list 1 2 3 )) => (((() 1) 2) 3)

Give a property op should satisfy to guarantee that fold-right and fold-left will produce the same values for any sequence.

op must satisfy $op(x y) = op(y x)$

Exercise 2.29 Complete the following definitions of reverse in terms of fold-right and fold-left

(define (reverse sequence)
	(fold-right (lambda (x y) (append y (list x))) '() sequence))
(define (reverse sequence)
	(fold-left (lambda (x y) (cons y x)) '() sequence))

Nested Mappings So the next problem becomes nested loops. How do we include those? As an example, lets consider the following problem:

Given a positive integer $n$, find all ordered pairs of distinct positive integers $i$ and $j$, where $1 \le j \le i \le n$ such that $i + j$ is prime. For example, if $n$ is 6, then the pairs are the following:
i 2 3 4 4 5 6 6
j 1 2 1 3 2 1 5
i + j 3 5 5 7 7 7

A natural way to organize this would be to:

  1. Generate the sequence of all ordered pairs of integers
  2. Filter to select those whose sum is prime
  3. For each pair, produce the triple $(i, j, i+j)$

To generate the sequence of ordered pairs, one can conceptually do the following: For each integer $i \le n$ enumerate the integers $j \le i$, and generate the pair $(i, j)$. This is a nested iteration, and would look something like this:

(accumulate
	append '() (map lambda (i)
					(map (lambda (j) (list i j))
						(enumerate-interval 1 (- i 1))))
				(enumerate-interval 1 n)))

This is ok-ish to read, but this is such a common operation, it is usually isolated in a separate procedure:

(define (flatmap proc seq)
	(accumulate append '() (map proc seq)))

Rewritten:

(flatmap (lambda (i)
			(map (lambda (j) (list i j))
				(enumerate-interval 1 (- i 1))))
			(enumerate-interval 1 n)))

If we then write the filter to select pairs whose sum is prime

(define (prime-sum? pair)
	(prime? (+ (car pair)(cadr pair))))

Remind that we are still dealing with lists. So we call it a pair, but it is really a 2-element list. hence the cadr instead of cdr, since the latter would return (j ()).

And lastly we create the triple:

(define (make-pair-sum pair)
	(list (car pair) (cadr pair) (+ (car pair)(cadr pair))))

This all can be combined into a single procedure:

(define (prime-sum-pairs n)
	(map make-pair-sum
		(filter prime-sum? (flatmap
							(lambda (i)
								(map (lambda (j) (list i j))
									  (enumerate-interval 1 (- i 1))))
								(enumerate-interval 1 n)))))

Which is still bloody unreadable, but I guess pipes were not invented yet.

Exercise 2.40 Define a procedure unique-pairs that, given an integer $n$, generates the sequence of pairs $(i, j)$ with $1 \le j < i \le n$

(define (unique-pairs n)
	(flatmap (lambda (i)
			(map (lambda (j) (list i j))
				(enumerate-interval 1 (- i 1))))
			(enumerate-interval 1 n)))

Exercise 2.41 Write a procedure to find all ordered triples of distinct positive integers $i, j,$ and $k$ less than or equal to a given integer $n$ that sum to a given integer $s$.

(define (sum-triplet? s pair)
	(= s (+ (car pair)(cadr pair)(caddr pair))))

(define (unique-triplets n)
	(flatmap (lambda (i)
		(flatmap (lambda (j)
			(map (lambda (k) (list i j k))
				(enumerate-interval 1 (- j 1))))
			(enumerate-interval 1 (- i 1))))
		(enumerate-interval 1 n)))


(define (solution n s)
	(filter (lambda (t) (sum-triplet? s t)) (unique-triplets n)))

2.2.4 Example: a Picture Language

This section present a simple language for drawing pictures that illustrates the power of data abstracion and closure. In this language, the data objects being combined are represented as procedures rather than as list structure. Just like cons, the operations in this language also satisfy the closure property, allowing us to easily build arbitrarily complicated patterns. 6fb7a623dc64a8994150c95f19e73dfd.png

The language Part of the elegance of this language is that there is only one kind of element, called a painter. A Painter draws an image that is shifted and scaled to fit within a designated prallelogram-shaped frame. The actual shape of the drawing depends on the frame. To combine images, we use various operations that consutrct noew painters from given painters. For example, beside takes two painters and produces a new, compound painter that draws the first painter’s image in the left half of the frame and the second painter’s image in the right half of the frame. As a more visual example, consider the following code:

(define wave2 (beside wave (flip-vert wave)))
(define wave4 (below wave2 wave2))

which would result in the following 2 images:

7a7fedf6dd96fc65bb99d3d5b24149dd.png

In building these complex images, we are exploiting the fact that painters are closed under the language’s means of combination. Any procedure that takes 1 or more painters as arguments returns in itself a painter that can be further combined.

And by implementing painters as scheme abstractions, we can abstract the pattern in wave4 as a procedure:

(define (flipped-pairs painter)
	(let ((painter2 (beside painter (flip-vert painter))))
		(below painter2 painter2)))

(define wave4 (flipped-pairs wave))

Exercise 2.44 Define the procedure up-split as used by corner-split

(define (corner-split painter n)
	(if (= n 0)
	painter
	(let ((up (up-split painter (- n 1)))
		  (right (right-split painter (- n 1))))
		(let ((top-left (beside up up))
			  (bottom-right (below right right))
			  (corner (corner-split painter (- n 1))))
			(beside (below painter top-left)
					(below bottom-right corner))))))

(define (up-split painter n)
	(if (= n 0)
	painter
	(let ((smaller (up-split painter (- n 1))))
		(below painter (beside smaller smaller)))))

Higher-order operations