All useful languages have a variety of "literal" values, such as integer literals (1, 2, etc.) and string literals ("hi", "bye"). Unlike C and other primitive languages, Scheme has a way of representing raw function "values", without names:
; Takes arg1 ... argN as arguments, and returns expr (lambda (arg1 arg2 ... argN) expr)
Function values can be passed around, just like any other values. Function values are applied just like variable names bound to functions---in fact both evaluate the same way:
(lambda (x) (+ x 1)) ; The "increment" function
((lambda (x) (+ x 1)) 2) ; A roundabout way of adding 1 to 2: the first element
; of this evaluates to a function, so we apply it to the
; rest of the list
(define increment ; Of course, we can bind functions to names
(lambda (x) (+ x 1))) ; as well, for later use.
(increment 2) ; Equivalent to applying the lambda directly, as above.
Functions can be passed as parameters and returned from other functions. This may sound mysterious and confusing at first, but it is only so because C has taught you to think of actions---that is, verbs---as "second-class". In other words, you can't treat functions in C the way you treat all other values. But a computer language without "first-class" functions is like a human language in which you can use verbs, but you cannot talk about verbs.
What do I mean? In English, you can say the following "first-order" sentences:
These sentences merely use verbs. But in English, verbs are first-class, so you can also have "higher-order" sentences that talk about other actions. Consider the following two exchanges:
In English, it is easy to recognize the common parts of the two conversations. The common pattern, or abstraction, of the two conversations is:
"Cleaning up stuff means:
`Take the stuff, and do something with it.'"
This sentence---"Take the stuff, and do something with it"---is an English "higher-order function". The "something" in "do something" is an English "function variable". Without higher-order functions, "do something with it" is hard to express. In Scheme, this thought is expressed as easily as it is expressed in English:
(define clean-up-this-stuff
(lambda (do-something list-of-stuff)
(map do-something list-of-stuff)))
Well, okay, I'm cheating, because the "do something to all this stuff" function is really another name for "map". There is an important difference, of course: "map" leaves the old stuff lying around and produces a whole new set of stuff---whereas in the real world, doing your laundry does not generally involve producing a new copy of your clothes. (We'll come back to map later.)
The previous example used a function parameter, "do-something". Functions can not only be passed as parameters, but also returned from other parameters. Again, this is very simple in English:
"Go to the receptionist and give him your ID number. He will give
you a slip of paper with instructions on it. Follow the instructions
on the piece of paper."
The "instructions" the receptionist gives you are a "function" that he returns. You have been told to execute this function when you get it, but you do not know what it is until you actually receive the instructions. This is easy to express in Scheme as well:
(define instructions (give receptionist id-number))
(instructions) ; Evaluate instructions, with no arguments
There are three higher-order functions which encapsulate many of the tasks that you will commonly want to perform on lists:
(map func alist)(map (lambda n (+ n 1)) '(7 0 4 2 9)) ; => (8 1 5 3 10)
(filter test? alist)(filter (lambda (n) (> n 5) '(7 0 4 2 9)) ; => (7 9)
(reduce func base alist)(reduce + 0 '(7 0 4 2 9)) ; => 22 (reduce cons () '(7 0 4 2 9)) ; => (7 0 2 4 9)
; Adds n to each item of a list
(define add-n
(lambda (n list)
(if (null? list)
()
(cons (+ n (car list))
(add-n n (cdr list))))))
(add-n 5 '(1 2 3 4))
; => (6 7 8 9)
; Adds n to each odd-numbered item of a list
(define add-n-odd
(lambda (n list)
(if (null? list)
()
(cons (if (odd? (car list))
(+ n (car list))
(car list))
(add-n-odd n (cdr list))))))
(add-n-odd 5 '(1 2 3 4))
; => (6 2 8 4)
; A minor generalization of the above?
(define add-n-if
(lambda (n test? list)
(if (null? list)
()
(cons (if (test? (car list))
(+ n (car list))
(car list))
(add-n-if n test? (cdr list))))))
(add-n-if 5 odd? '(1 2 3 4))
; => (6 2 8 4)
(add-n-if 5
(lambda (x) (= (+ x 2) 6))
'(1 2 3 4))
; => (1 2 3 9)
; A more useful generalization
(define map-if
(lambda (fn test? list)
(if (null? list)
()
(cons (if (test? (car list))
(fn (car list))
(car list))
(map-if fn test? (cdr list))))))
(map-if (lambda (x) (+ x 5))
(lambda (x) (and (odd? x) (> x 2)))
'(1 2 3 4))
; => (1 2 8 4)
; A shorter way of writing map-if, using built-in map
(define map-if
(lambda (fn test? list)
(map (lambda (item)
(if (test item) (fn item) item)
list))))
In general, anywhere you see a function doing "actual work", that's often an opportunity for abstraction and function parameters.
Consider a list of (last name, first name) lists:
'(("Dugan" "Ben")
("Huff" "Justin")
("Lee" "Keunwoo"))
Write a function that extracts all the first names without using map. Then rewrite it using map. Then use filter and map together to extract all the last names that are longer than 3 letters.
How could you use reduce to do the following tasks?
(count-in-range min max
alist), which takes three parameters:
Advanced exercise: Consider a list whose first element is a symbol '+, '-, or '*, and whose remaining elements are numbers. Examples of such lists:
'(+ 1 2 3) '(- 9 3) '(* 734 128 78271 8287 17)
'(+ 1 2 (- 5 6) (* 27 271))
Advanced exercise (recursion only): XML is a textual "document markup language" whose format is very similar to quoted lists in Scheme. XML looks like this:
<person>
<name>
<firstname>Keunwoo</firstname>
<lastname>Lee</lastname>
</name>
<webpage>http://www.cs.washington.edu/homes/klee/index.html</webpage>
</person>
<person>
<name>
<firstname>Justin</firstname>
<lastname>Huff</lastname>
</name>
<email>jjhuff@cs</email>
</person>
It is easy to see that the above is equivalent to:
(define atree
'((person
(name (firstname "Keunwoo")
(lastname "Lee"))
(webpage "http://www.cs.washington.edu/homes/klee/index.html"))
(person
(name (firstname "Justin")
(lastname "Huff")
(email "jjhuff@cs")))))
Suppose you had a parser that could turn XML into Scheme
data according to the above conventions. Devise a function
(query-tree tree symbol) that, given a Scheme
tree and a symbol, returns a list of all lists whose first
element matches that symbol. For example, consider the
following queries over the above tree:
(query-tree atree 'email)
; => ((email "jjhuff@cs))
(query-tree atree 'lastname)
; => ((lastname "Lee") (lastname "Huff"))
(query-tree atree 'name)
; => ((name (firstname "Keunwoo") ...)
(name (firstname "Justin") ...))