Functions as First Class Objects
In Scheme, and other functional programming languages, functions are "First Class Objects". But what does that mean?
An object is first class if it can be treated the same way as a value, that is it can be:
- 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.