In Scheme, and other functional programming languages, functions are “First Class Objects”. But what does that mean?
- Assigned to a variable.
- Passed to a procedure.
- Returned from a procedure.
Having functions as first class objects provides another dimension for program abstraction. A procedure which receives a procedure as an input or generates a procedure as an output, is called a higher order procedure.
Another feature in practice of functional programming is the map-reduce pattern. In map-reduce an algorithm is split into two parts, the “map” where a calculation is done on each element in a list, and the “reduce” where the result of the individual calculations are aggregated.
Scheme has two methods which help implement simple cases of map-reduce:
- Map – Takes a procedure and a list as arguments, and returns a list containing the result of applying the procedure to each item in the list.
- Apply – Takes a procedure and a list as arguments, and returns the result of calling the procedure with all the values in the list.
So say you want to calculate the sum of the squares of a bunch of numbers:
(define square (lambda (x) (* x x))) (define sum-of-squares (lambda x (apply + (map square x)))) (sum-of-squares 2 2 2) => 12
Now, say you want to calculate the sum of the cubes of a bunch of numbers. Well you could just copy the sum-of-squares function, change the name and change the call to square to a call to cube:
(define cube (lambda (x) (* x x x))) (define sum-of-cube (lambda x (apply + (map cube x)))) (sum-of-cube 3 3 3) => 27
But you can see most of the sum-of-squares and sum-of-cubes functions are the same, only differing by the function which gets called. You can remove the duplication by exploiting first class functions. Define a sum-of-func procedure, which takes the function you want to apply as an argument, and returns a sum-of function as its result:
(define sum-of-func (lambda (f) (lambda x (apply + (map f x)))))
You use the higher-order procedure sum-of-func like this:
(define sum-of-square (sum-of-func square)) (sum-of-square 2 2 2) => 12 (define sum-of-cube (sum-of-func cube)) (sum-of-cube 3 3 3) => 27
It’s really quite beautiful.