Simply Scheme Chapter 8 – Higher Order Functions

A function that takes another function as one of its arguments is called a higher-order function. This chapter discusses several such functions.


every is a function that lets us take a function as an argument and apply it to every word in a sentence or every letter in a word, regardless of the length of the sentence or word.

E.g. this gives you the first letter of every word in a sentence:

every is taking first as an argument, not invoking it.
every always returns a sentence.


keep takes a predicate and sentence as arguments and returns the words for which the predicate is true. If given a word instead of a sentence, it returns the letters (in word form) for which the predicate is true.


accumulate takes a procedure and sentence as arguments, applies that procedure to two elements of the sentence and gets a result. It then takes that result and applies the procedure to that result and the next element in the sentence, and keeps going until it’s combined everything together.

accumulate can also take a word as an argument instead of a sentence, treating the letters as elements.

Combining Higher Order Functions

You can combine higher order functions e.g.:

The keep number? takes the argument sent and returns a new sentence where number? is true for each element. Then that sentence gets passed to accumulate +. So the keep number? essentially acts as a filter for non-numbers, keeping them out of accumulate +‘s way and insuring that the sentence argument for accumulate + only has numbers to deal with.


the repeated procedure returns a procedure that invokes the original procedure repeatedly. E.g.

(repeated bf 3) returns a procedure that does (bf (bf (bf))) on some input. If you don’t give it an input then Scheme just tells you that you have a procedure:

Shorter Notes

Scheme’s treatment of sentences as first-class data and functions as first-class lets us generalize ideas like “apply this function to every word of a sentence.

keep always returns a function of the same type as its second argument.

every always returns a sentence. If you want a word for every, you can accumulate word the sentence that every returns.

every expects a function of just one argument as its first argument. if you give it a function like quotient that expects two arguments, you’ll get an error message about not having enough arguments

Trying (every (quotient 6) '(1 2 3)) doesn’t help. Scheme tries to evaluate quotient 6 and throws an error.

This doesn’t work either: (every (+ 3) '(1 2 3))

(+ 3) returns 3. every wants a procedure as its first argument, and the number 3 isn’t a procedure:

accumulate can accept an empty sentence or word for +, *, word, and sentence.

Boring Exercises

What does Scheme return as the value of each of the following expressions? Figure it out for yourself before you try it on the computer.

✅❌ Exercise 8.1

(every last '(algebra purple spaghetti tomato gnu))

I predicted: '(aeiou)
❌ Woops. It should be (a e i o u)

(keep number? '(one two three four))

I predicted ().
✅I was correct.

(accumulate * '(6 7 13 0 9 42 17))

I predicted 0.
✅ I was correct.

(member? 'h (keep vowel? '(t h r o a t)))

I predicted false. keep vowel? returns a sentence of (o a) and ‘h is not a member of that sentence.

✅ I was correct.

(every square (keep even? ‘(87 4 7 12 0 5)))

I predicted '(16 144 0).

✅ I was correct.

(accumulate word (keep vowel? (every first ‘(and i love her))))

I predicted 'ai.
✅ I was correct.

((repeated square 0) 25)

I was not sure about this one so I just tried it.

It just returns 25. I guess repeated gets called 0 times? So you just return the value of the number. It’s interesting though … if you call (repeated square 0) you do get a procedure back. I wonder what the procedure is exactly.

(every (repeated bl 2) ‘(good day sunshine))

I predicted '(go d sunshi).

✅ I was correct.

✅ Exercise 8.2

Fill in the blanks in the following Scheme interactions:

✅ answer:

Forgot to include this one initially, didn’t see it until I saw Anne’s answer:

✅ answer:

✅ answer:

✅ answer:

✅ answer:

✅ answer:

✅❌ Exercise 8.3

Describe each of the following functions in English. Make sure to include a description of the domain and range of each function. Be as precise as possible; for example, “the argument must be a function of one numeric argument” is better than “the argument must be a function.”

❌ (wrong) f takes a word or sentence consisting entirely of numbers as an argument.

If provided a word as the second argument, it will return the subset of the word that consists of even numbers.

If provided a sentence as the second argument, it will return the subset of words in the sentence that consist of even numbers.

f‘s domain is words or sentences made entirely of numbers.

Its range is a word or sentence that consists entirely of even numbers.

✅ (FIXED) The domain is non-negative integers (by themselves) or integers (including negative integers) in a sentence. Its range is non-negative even integers (by themselves) or even integers (including negative integers) in a sentence.

g takes a function that operates on one word. it applies that function to every element of the sentence (blue jay way) and returns a sentence with the result. e.g.:

❌ (WRONG) g‘s domain is functions that accept one word-arguments, and its range is a sentence that is some transformation of (blue jay way).

✅ (CORRECTION) AnneB pointed out that you can actually get any output using g if you define a function that is always true and returns the sentence you want:

So the range is all sentences.

h takes a procedure c and calls it twice on an argument d.

For this procedure to work, the procedure used as the argument has to accept what it returns as input. So for example, even? would not work as a procedure because that returns booleans but does not accept them. butfirst, by contrast, both returns and accepts sentences, so that could work.

h can accept procedures that operate on numbers. for example:

So the domain for the procedure part (c) is a procedure that returns and can accept the same data type. There appear to be no restrictions on the domain in terms of the data part (d). I could not think of any restrictions on the range either.

i takes a number or sentence consisting of numbers and divides the total of the numbers by the number of numbers in the sentence (in other words, it finds the average)

❌ (WRONG)i‘s domain is a number or sentence consisting of numbers.
i‘s range is numbers.

✅ (FIXED) The domain is limited to positive integers or 0, or sentences with any numbers (including complex numbers and weird stuff like that). No empty words/sentences though (you get a division by 0 error)

accumulate takes a procedure that combines two arguments as its first argument, and a word or sentence as its second arguments, and goes through and combines the elements in the second argument until it runs out.

accumulate returns a combined value depending on the procedure provided to it.

for word, it takes a sentence and returns a combined word.
for se,
for +, it takes as sentence of numbers and returns the sum of those numbers.
for -, it seems to work a differently than you might expect. Consider (accumulate - '(10 25 43 69 1 2)). You might expect this procedure to subtract 25 from 10, getting -15, and then subtract 43 from -15, getting -58, and so on until arriving at a value of -130.


Why -42?

I think how the functions work (paralleling an example from the text) is something like this:

for accumulating a word, the order does not matter:

but for accumulating subtraction the order matters a lot.

Accumulate has a complicated domain and I’m not sure how to describe it comprehensively. Depending on the procedure provided, accumulate’s domain can include a word or sentence or number. For +, *, word, and sentence, accumulate can accept empty arguments.

Its range includes numbers, words or sentences.

AnneB says:

accumulate takes two arguments, a procedure and a word or sentence. The domain of accumulate is all sets of a procedure and a word or sentence that fit at least one of the following:

  1. A procedure that can accept two letters (words of length one) or two words (whichever it is paired with) and returns something that it will accept as an argument, along with a word or sentence that is at least 2 in length.
  2. Any procedure, along with a word or sentence of length 1.
  3. The procedures +, *, word, or sentence, along with an empty word or an empty sentence.

I’m not sure 2 is correct. Certain procedures don’t take certain inputs (like even? doesn’t take words) and will give error if you try to use them.
1 and 3 seem correct. More AnneB:

accumulate calls the procedure with the first two elements of the given word or sentence, then calls it again with that result and the third element, and continues until it has used all the elements of the given word or sentence. If the given word or sentence has only one element, accumulate returns that word or sentence. If the given word or sentence is empty, accumulate returns the identity element of the given procedure.

I agree.

sqrt takes a number and returns the square root of that number.
sqrt‘s domain is numbers and its range is a real or imaginary number.

This may be wrong re: range. I think maybe I meant complex numbers and not imaginary numbers. Anne wrote a lot of stuff about it:

The domain of sqrt is at least all real numbers. The version of Scheme I’m using does accept negative numbers. For instance:

> (sqrt -1)

I can’t figure out if there’s a way to input complex numbers like “2+3i” into this version of Scheme.

If you enter them as number + i, it works:

Just 4i by itself won’t work though. It’s detecting only the specific number+i format, at least for me.

If there is, then the domain might include them too.

Ya it seems to include complex numbers.

I found this:

Mathematically, numbers may be arranged into a tower of subtypes in which each level is a subset of the level above it:
For example, 3 is an integer. Therefore 3 is also a rational, a real, and a complex. The same is true of the Scheme numbers that model 3. For Scheme numbers, these types are defined by the predicates number?, complex?, real?, rational?, and integer?.

The sqrt procedure returns the principal square root of the number. This place explains what that is:

procedure: sqrt z
Returns the principal square root of z. The result will have either positive real part, or zero real part and non-negative imaginary part.

So if the domain of sqrt is the real numbers, then the range is the non-negative real numbers plus the complex numbers with a zero real part and non-negative imaginary part. If the domain of sqrt is the complex numbers, I’m not sure what the range is, but it might be all complex numbers with a positive real part or a zero real part and a non-negative imaginary part. If the domain of sqrt is all numbers, then I don’t know what the range is.

Seems fair to say sqrt‘s domain is complex numbers and range is complex numbers with a positive real part or a zero real part and a non-negative imaginary part.

repeated takes a procedure and a number and returns a procedure which consists of the procedure it was provided invoked a number of times equal to the number it was provided. e.g.:
((repeated bf 3)'(potato cheese ninja puff hat))
returns '(puff hat).

repeated‘s domain is a procedure and positive integer or 0, and its range includes many procedures. If the number provided to repeated is greater than 1, the procedure has to be able to take the value it returns as an input. For example, ((repeated even? 1) 2) works because even? is only getting invoked one time. OTOH, ((repeated even? 2) 2) does not work because the first invocation of even? returns a boolean, and even? returns but does not take booleans.

Forgot to discuss giving 0 as the second argument. If you use 0 as the number of times to invoke the procedure, then you just get the word or sentence returned back:

AnneB says:

repeated takes two arguments, a procedure and a number. The domain of repeated is all sets of procedures and whole numbers where the range of the procedure is a subset of the domain of the procedure (it doesn’t have to be a proper subset),

I think maybe “all sets of procedures and whole numbers where the range of the procedure is a subset of the domain of the procedure” is trying to get at a similar point as I was trying to get at with “If the number provided to repeated is greater than 1, the procedure has to be able to take the value it returns as an input.” The range has to be a subset of the domain so that the procedure can be called repeatedly in cases where you invoke the procedure > 1 times.

or the number is 0 or 1 and the procedure is any procedure. The range of repeated is the union of all the ranges of such procedures.

I think maybe I follow the part re: “union” but I’m not really sure. I think maybe it means that the range of repeated is the range of all the procedures previously described combined.

(repeated sqrt 3) takes a number and finds its square root 3 times. For example, (repeated sqrt 3) applied to 256 returns 2. (The square root of 256 is 16, the square root of 16 is 4, the square root of 4 is 2).

Seems like this would be the same as square root: domain is complex numbers and range is complex numbers with a positive real part or a zero real part and a non-negative imaginary part.

(repeated even? 2) returns a procedure which applies even? to a number, and then applies even? to the result of the first application of even?.

So in other words, it does something like:

(even? (even? 2))

If it was just even? once, then the domain would be a number and the range would be a boolean. With this function, however, things are different.

even? doesn’t accept booleans, which is all that even? can produce. You get an error message with this function regardless of the input.

So I think this function doesn’t have a domain or range. It’s like a broken procedure.

(repeated first 2) returns a procedure which takes takes first of some argument twice. So it does something like (first (first '(potato tomato))).

Invoking first twice on a sentence first returns the first word of that sentence and then returns the first letter of the first word.

Invoking first twice on a word returns the first letter of that word. It doesn’t matter how many times you invoke first on a word repeatedly – you keeping getting the first letter

So (repeated first 2) has the interesting property that it returns either the first letter of a word (or first character of a number) or the first letter of the first word of a sentence. For words and unnested sentences, it has the same output (a word consisting of a single letter).

If a sentence is nested one level, like '((potato tomato)), it will return the first word of the sentence (potato in my example).

If a sentence is nested two levels, like '(((potato tomato))), the function will return the entire sentence. If there are multiple nested sentences, it will return the first sentence.

There are invalid inputs to (repeated first 2). These include the empty sentence'() and empty word "".

❌ (wrong) The domain of (repeated first 2) is any non-empty word or sentence, and the range is either the first letter of a word or the first sentence within a nested sentence. Putting it more generally, we could say the range is the first element within a word or sentence (and keep in mind that with nesting the “first element” could be a whole nested sentence).

✅ (fixed). The domain of (repeated first 2) is any non-empty word or sentence. The range may likewise be non-empty words or sentences but I’m not sure.

(repeated (repeated bf 3) 2) results in butfirst being invoked 6 times.

the (repeated bf 3) returns a procedure that invokes butfirst 3 times. then the left-most repeated returns a procedure which invokes the (repeated bf 3) procedure twice on some input, resulting in 6 invocations.

We can see this in the following examples.

I defined the following function:

butfirst 6 times on the input sentence returns the 7th value, grape.

butfirst 6 times on the input returns a word starting at the 7th letter.

inputs to the function need to at least contain 6 values (in that case returning an empty list or sentence). If they have 5 or fewer values, an error will result.

So the domain of the function is any word or sentence with greater than 5 elements. The range is a word or sentence.

Real Exercises

✅ Exercise 8.4

Write a procedure choose-beatles that takes a predicate function as its argument and returns a sentence of just those Beatles (John, Paul, George, and Ringo) that satisfy the predicate. For example:


✅ Exercise 8.5

Write a procedure transform-beatles that takes a procedure as an argument, applies it to each of the Beatles, and returns the results in a sentence:


✅ Exercise 8.6

When you’re talking to someone over a noisy radio connection, you sometimes have to spell out a word in order to get the other person to understand it. But names of letters aren’t that easy to understand either, so there’s a standard code in which each letter is represented by a particular word that starts with the letter. For example, instead of “B” you say “bravo.”
Write a procedure words that takes a word as its argument and returns a sentence of the names of the letters in the word:**

(You may make up your own names for the letters or look up the standard ones if you want.)
Hint: Start by writing a helper procedure that figures out the name for a single letter.


✅ Exercise 8.7

Write a procedure letter-count that takes a sentence as its argument and returns the total number of letters in the sentence:


✅ Exercise 8.8

Write an exaggerate procedure which exaggerates sentences:

It should double all the numbers in the sentence, and it should replace “good” with “great,” “bad” with “terrible,” and anything else you can think of.


✅ Exercise 8.9

What procedure can you use as the first argument to every so that for any sentence used as the second argument, every returns that sentence?

sentence seems to work, though for nested sentences it doesn’t return the nesting.

AnneB noticed a couple of other things that work – word and a function that just returns the same input:

What procedure can you use as the first argument to keep so that for any sentence used as the second argument, keep returns that sentence?

word? seems to work for this, assuming no nesting. It works for the empty sentence too.

What procedure can you use as the first argument to accumulate so that for any sentence used as the second argument, accumulate returns that sentence?

sentence works, including for nesting.

✅ Exercise 8.10

Write a predicate true-for-all? that takes two arguments, a predicate procedure and a sentence. It should return #t if the predicate argument returns true for every word in the sentence.


✅ Exercise 8.11

Write a GPA procedure. It should take a sentence of grades as its argument and return the corresponding grade point average:

Hint: write a helper procedure base-grade that takes a grade as argument and returns 0, 1, 2, 3, or 4, and another helper procedure grade-modifier that returns −.33, 0, or .33, depending on whether the grade has a minus, a plus, or neither.*


Thought the slight implementation difference between my version and AnneB’s was interesting. AnneB added the modifiers up separately in the gpa part of the procedure while I added the modifier directly to the grade in base-grade using the grade-modifier helper procedure. I think maybe Anne’s organization is a bit more logical cuz it keeps the base grade and modifier separate until the final step.

✅ Exercise 8.12

When you teach a class, people will get distracted if you say “um” too many times. Write a count-ums that counts the number of times “um” appears in a sentence:


✅ Exercise 8.13

Write a procedure phone-unspell that takes a spelled version of a phone number, such as POPCORN, and returns the real phone number, in this case 7672676. You will need to write a helper procedure that uses an 8-way cond expression to translate a single letter into a digit.

✅ Exercise 8.14

Write the procedure subword that takes three arguments: a word, a starting position number, and an ending position number. It should return the subword containing only the letters between the specified positions:



I should think more carefully about handling erroneous inputs with else clauses and that kind of thing.

For figuring out domain and range of a function, I should pay attention to integer versus decimal, negative numbers etc. Also try to break down the different parts of a procedure’s domain somewhat more systematically and formally (as best as I can anyways).

Simply Scheme Chapter 7 – Variables

Quotes from here or elsewhere in Simply Scheme unless otherwise noted.

References to “SS” or “the book” are to Simply Scheme.


In functional programming, variable means something like a named constant in algebra (e.g. when x^3 – 8 = 0, x = 2). Formal parameters in a procedure definition aren’t variables but are mere names. However, when you invoke a procedure with a particular argument, the formal parameter/name is associated with a particular value, and so a variable is created. Later, if the procedure is invoked again, a new variable might be created with a different value.

Part of what functional programming means is that you don’t change the value of a variable once it exists. This contrasts with languages where you do change the value of the same variable after bringing it into existence (as opposed to creating a new variable). “Programs in those languages tend to be full of things like ‘X = X + 1.'”

One issue to keep in mind is you can have more than one variable with the same name at the same time, because you can invoke a procedure that in turn invokes a procedure and both of them use the same formal parameter name.

There might be one variable named x with the value 7, and another variable named x with the value 51, at the same time. The pitfall to avoid is thinking “x has changed its value from 7 to 51.”

These x’s are different variables.

As an analogy, imagine that you are at a party along with Mick Jagger, Mick Wilson, Mick Avory, and Mick Dolenz. If you’re having a conversation with one of them, the name “Mick” means a particular person to you. If you notice someone else talking with a different Mick, you wouldn’t think “Mick has become a different person.” Instead, you’d think “there are several people here all with the name Mick.”

Little People and Variables

Little people model can help understand how variables work.

In the above set of expressions, one little person (who the book calls Hortense) thinks x is 3 for the purposes of evaluating hypotenuse. Hortense hires Solomon to compute (square 3) and Solmon happens to associate x with 3, which is the same association between a formal parameter and a name that Hortense had in hypotenuse. But these associations represent different variables (and this is presumably reflected in the computer’s memory somewhere). When Hortense hires Sheba to compute square 4, Sheba associates x with 4, but again this is a different x than the x that Hortense associated with 3 (and for that matter, a different x than the x that Solomon associated with 3, despite the same procedure being invoked for both of them).

(Remember that we said a variable is a connection between a name and a value. So x isn’t a variable! The association of the name x with the value 5 is a variable. The reason we’re being so fussy about this terminology is that it helps clarify the case in which several variables have the same name. But in practice people are generally sloppy about this fine point; we can usually get away with saying “x is a variable” when we mean “there is some variable whose name is x.”)

The book also mentions that procedures invoked by other procedures don’t have awareness of the meaning of variables that the parent procedure is using, so you have to explicitly tell the procedure being invoked what’s a particular value is if you want that procedure to use it. So for example this doesn’t work:

the g procedure has no knowledge of the meaning of x to the f procedure that’s calling g. You can tell the g procedure the value explicitly though:

Global and Local Variables

You can use define to permanently associate a name with a value and not just for defining a procedure. This creates a global variable – an association between a name and a value that applies generally and not just for the purposes of evaluating a procedure. All the “little people” are aware of such a global variable, unlike in the case of local variables, where the association between a formal parameter and an actual argument is local to a procedure.

Chalkboards and Truth About Substitution

SS gives a chalkboard analogy for understanding variables. Global variables are up on a big chalkboard that all little people can see. What about local variables? Each little person evaluating a procedure has their own chalkboard that they work on to handle variables for that particular procedure.

SS also says the substitution model discussed earlier isn’t actually accurate. Instead of making a new copy of an expression with the appropriate values substituted in for the formal parameters, what Scheme actually does is use the original expression and look up the value of each name when it’s needed, maintaining variables on several “chalkboards” in order to be able to have local variables.


let lets you basically create a temporary procedure without getting it a name and lets you invoke that procedure with a specified argument value.

Let is a special form that takes two arguments. The first is a sequence of name-value pairs enclosed in parentheses. […] The second argument, the body of the let, is the expression to evaluate.


The book notes that if you’ve programmed in other languages before, you may be used to changing the value of a variable by assigning it a new value and thus want to write something like:

Definitions are meant to be permanent in functional programming.

When you create more than one temporary variable at once using let, all of the expressions that provide the values are computed before any of the variables are created. Therefore, you can’t have one expression depend on another:

“all of the expressions that provide the values are computed before any of the variables are created” means that, for example, (+ 4 7) and (* a 5) are calculated before the results of those expressions are associated with a and b and so on. No associations between names and values are made until all such calculations are done within the let. So if Scheme tries to evaluate the above, when it gets to the (* a 5) it has nothing to put in for the a.

Don’t think that a gets the value 11 and therefore b gets the value 55. That let expression is equivalent to defining a helper procedure

and then invoking it:

The argument expressions, as always, are evaluated before the function is invoked. The expression (* a 5) will be evaluated using the global value of a, if there is one. If not, an error will result. If you want to use a in computing b, you must say

This last one works because the value of the a in the first let is computed and then the a variable is created. Having been created, a is available for use as a value to provide to b within the second let.


Boring Exercises

✅ Exercise 7.1

The following procedure does some redundant computation.

Use let to avoid the redundant work.

my solution:

AnneB did this a bit differently and just figured out the article in the let, whereas I slapped the whole article + world combination in. Hers is probably better cuz I’m not sure how logical my grouping of article and word together is.

✅ Exercise 7.2

Put in the missing parentheses:



Real Exercises

✅ Exercise 7.3

The following program doesn’t work. Why not? Fix it.

It doesn’t work cuz it uses word as both a procedure name and a variable name.

It’s supposed to work like this:


✅ Exercise 7.4

What does this procedure do? Explain how it manages to work.

The let in this procedure causes the addition procedure + to act as the multiplication procedure * and the multiplication procedure * to act as the addition procedure + within the body of the let.

A correctly written sum of squares procedure should square its arguments and then add them. In the body of the procedure, we see that we instead have arguments each being added to themselves once and then multiplied. However, the definitions in the let will be evaluated before the body runs. Therefore, the redefinitions take effect, and the procedure actually works as intended. E.g. (+ a a) becomes (* a a) and likewise (+ b b) becomes (* b b). Multiplying a number by itself is squaring it. Then what was the * becomes a + and so the result is:

This is a correct sum of squares procedure, and so the procedure produces the correct output, contrary to what you might initially expect.

Scheme Skill-builder 2

Practicing Program Logic

Exercise 1

I made up this silly procedure to work on thinking about the logic of a program. The idea is that if x y and z are all true, you get the over 9000 message returned. If either x and y, x and z, or y and z are true, you get the 8000 message returned. If only one of x, y, or z is true, you get the 3000 message returned. If none are true, you get the message about low energy returned.

Exercise 2 – Requirements for Amending the Constitution

This is an exercise to practice trying different ways of logically representing a procedure.

Here are requirements for amending the U.S. Constitution stated “negatively”:

You CAN’T amend the U.S. Constitution if:
1) you have fewer than 290 votes in the House, OR
2) you have fewer than 67 votes in the Senate, OR
3) fewer than 38 states have ratified the Amendment.

If any one of these numbered statements is true, an amendment fails. Any one of these things being true, independently, makes an amendment passing impossible.

Here is an implementation of the above using if with some test cases:

Initially I put the parameters and the numbers in the wrong order (e.g. i had it as < 290 house) but I caught this error quickly.

This tree has logic which corresponds to the procedure above:

Another way to think of the procedure is “positively” as follows:

You can amend the U.S. Constitution if:
1) you have 290 votes or greater in the House, AND
2) you have 67 votes or greater in the Senate, AND
3) you have 38 states or greater that ratify the Amendment.

All of these must be true, together, for an amendment to succeed. If any one of them is false, the Amendment fails.

It’s a bit easier to represent the program in code by thinking of it in this way:

Here is a tree for this way of doing it:

It’s easier because with this way of framing things, you can rely on the value the and returns without needing to add the complication of an if. The if was necessary in the previous version because we wanted to return false if any of the expressions that were governed by/children of the or returned true. But with this way of organizing the program, we want the expression to return true if all the expressions that are governed by/children of the and return true, and to return false otherwise. Since the output we want matches how the and works logically, we don’t need the if statement.

Thinking about different ways of organizing a program and which ways might be simpler seems like it could be quite important for effective programming.