First-class, Functional abstraction, Currying
The term first-class refers to the idea that values can be
Scheme, as a functional language, allows functions to be first-class, too, unlike languages such as C and Pascal. They can be in data structures, e.g., (list + - cons), can be created by lambda, and can be arguments to functions or returned by functions (cf. the following sections).
Congratulations, you have graduated to the Advanced language level!
Let's say we'd like to apply a function to an argument twice. That's easy, e.g.,
(add1 (add1 5))
I'd like to be able to do that for any function and argument. So, let's make a function twice-apply. It needs two arguments: a function to apply and an argument to apply that function to. In the body, we just do two applications like in the previous example.
(define twice-apply
(lambda (f arg)
(f (f arg))))
Then we can say, e.g., (twice-apply add1 5).
Ok, I'd also like to just give the function, e.g., add1, and get back a new function twice that applies it twice to something. E.g., given add1, I'd get back something that acts like add2. This seems kind of silly with just add1, but say you had a function that calculates derivatives, this would give back a function to calculate second derivatives.
To do this, we need a function which takes one argument, the function f, and returns a new function. The returned function takes one argument, the original arg, and does the applying as before.
(define twice
(lambda (f)
(lambda (arg) ; the function returned
(f (f arg)))))
We can use it either like ((twice add1) 5) or
(define add2 (twice add1)) (add2 5)
We are familiar with writing functions such as
(define double-nums
(lambda (nums)
(if (null? nums)
null
(cons (* 2 (car nums)) (double-nums (cdr nums))))))
(define lessthan3-nums
(lambda (nums)
(if (null? nums)
null
(cons (< (car nums) 3) (lessthan3-nums (cdr nums))))))
Since these functions are so similar, we'd like to package together the similar parts and separate out the different parts. We'll "package" the similar parts as a new function that can take either of the "different" parts as an argument that tells us what to do:
(define map
(lambda (f xs)
(if (null? xs)
null
(cons (f (car xs)) (map f (cdr xs))))))
(define double-num (lambda (num) (* 2 num)))
(define double-nums (lambda (nums) (map double-num nums)))
(define lessthan3-num (lambda (num) (< num 3)))
(define lessthan3-nums (lambda (nums) (map lessthan3-num nums)))
In a sense, map isn't useful of itself, in that it needs an functional argument such as double-num or lessthan3-num to get it to do anything. But map abstracts the general idea of "computing a new element from each old element and building a list of the new elements" away from what specifically you are computing from each element.
Using Donkey, evaluate (double-nums (list 2 4 6 8)) and watch in what order everything gets done.
We can even abstract from map something more general, the idea of "computing a new element from each old element and combining those new elements". In map, we combine the new elements by putting them in a list, but what if we wanted to add them together?
To do that, we need to abstract away from using null and cons to make the result list. Instead, we use new function arguments base and combinef as our base case and combining function:
(define map-and-fold
(lambda (f xs base combinef)
(if (null? xs)
base
(combinef (f (car xs)) (map-and-fold f (cdr xs) base combinef)))))
(define map
(lambda (f xs)
(map-and-fold f xs null cons)))
Frequently we just want to combine the elements of the original list, i.e., we don't need a function f. E.g., we may want to sum the numbers in a list, as we've done before.
(define identity (lambda (x) x)) (define sum (lambda (nums) (map-and-fold identity nums 0 +))) (define prod (lambda (nums) (map-and-fold identity nums 1 *)))
In fact, that's so common, that there's a standard name for "map-and-fold with no function f", called fold (which is why we used the name map-and-fold before).
(define fold
(lambda (xs base combinef)
(map-and-fold identity xs base combinef)))
or, equivalently,
(define fold
(lambda (xs base combinef)
(if (null? xs)
base
(combinef (car xs) (fold (cdr xs) base combinef)))))
Then,
(define sum (lambda (nums) (fold nums 0 +)))
(define prod (lambda (nums) (fold nums 1 *)))
(define add1-to-2nd (lambda (n1 n2) (+ 1 n2)))
(define length (lambda (xs) (fold xs 0 add1-to-2nd)))
(define member?
(lambda (x xs)
(fold xs #f (lambda (xx b) (or (eq? xx x) b)))))
Using Donkey, evaluate (sum (list 2 4 6 8)) for each of these definitions. As with our direct implementation we did previously, we eventually get to the computation (+ 2 (+ 4 (+ 6 (+ 8 0)))).
This definition of fold is equivalent to Scheme's built-in function foldr except that it takes the arguments in the opposite order.
Functions like map and fold can be very useful once you get used to them. Some functional languages like Haskell and Miranda consider them among the basic building blocks used in almost any program.
Say we have a bunch of sample functions on numbers, e.g., sin, add1, zero?. (Feel free to pick your own favorite functions.) We can make a list of these: (list sin add1 zero?).
We also like to map these functions over lists, e.g., (map sin (list 2 8 143 53)). Because we're obsessed, we want to map each of these functions over a bunch of lists. It should be clear that we need two uses of map to consider all combinations, but we can do this in a couple different ways:
(define map-each-fun1
(lambda (fs ls)
(map (lambda (f)
(map f ls))
fs)))
(define map-each-fun2
(lambda (fs ls)
(map (lambda (l)
(map (lambda (f) (f l))
fs))
ls)))
(map-each-fun1 (list sin add1 zero?) (list 2 8 143 53))
(map-each-fun2 (list sin add1 zero?) (list 2 8 143 53))
What's the difference between these?
We previously saw this insertion sort:
(define insert<-num
(lambda (num nums)
(if (null? nums)
(cons num null)
(if (< num (car nums))
(cons num nums)
(cons (car nums) (insert<-num num (cdr nums)))))))
(define isort<-nums
(lambda (nums)
(if (null? nums)
null
(insert<-num (car nums) (isort<-nums (cdr nums))))))
We might want to abstract this because it only sorts numbers in
ascending order (because of the test <). The following
sorts whatever you specify, as long as you give it an appropriate
comparison operator:
(define insert
(lambda (x xs comparef)
(if (null? xs)
(cons x null)
(if (comparef x (car xs))
(cons x xs)
(cons (car xs) (insert x (cdr xs)))))))
(define isort
(lambda (xs comparef)
(if (null? xs)
null
(insert (car xs) (isort (cdr xs) comparef) comparef))))
(define sort isort)
; sort a list of numbers in ascending order
(sort (list 2 98 43 1) <)
; sort a list of numbers in decending order
(sort (list 2 98 43 1) >)
; sort a list of lists in ascending order of lengths
(sort (list (list 1 2 3 4)
(list 'a 'b 'd 'e 'y)
(list 3 1)
(list 56 2 2435))
(lambda (l1 l2)
(< (length l1) (length l2))))
Try the examples.
Another advantage of this approach is that we could simply change the one definition of sort, say to be a mergesort routine, and all of our examples would then be using mergesort. If we had defined isort-<, isort->, and isort-<length, we'd have to change a lot more code to switch to mergesort.
How do you add 2 to a number? That's easy, for example:
(+ 2 3)But maybe I'm going to want to add 2 a bunch of times. Let's define a function which adds 2 to it's argument:
(define add2 (lambda (n) (+ 2 n))) (add2 3) (add2 56) (map add2 (list 3 5 8 0))
What if I also want to add 7 a bunch of times?
(define add7 (lambda (n) (+ 7 n)))I'm starting to see a pattern here, how would we abstract from these?
(define make-adder
(lambda (num)
(lambda (n) (+ num n))))
(define add2 (make-adder 2))
(define add7 (make-adder 7))
make-adder is the curried version of +.
(H.B. Curry was one of the first mathematicians to propose doing this.)
It takes one argument and returns a function which expects one argument
and returns the sum of the two.
You should also recognize the previous examples twice-apply and twice as an example of this.
Above we defined a verson of member?, which tests whether a symbol is in a list. We might want to test whether a symbol is in a bunch of different lists. A curried version of member? helps:
(define curried1-member?
(lambda (x)
(lambda (xs)
(member? x xs))))
(define is-car-member? (curried1-member? 'car))
(is-car-member? (list 'auto 'bike 'car 'plane))
(is-car-member? (list 'hydroplane 'pogostick 'truck))
Alternatively, we might want to check a bunch of different symbols
to see if they are in a list:
(define curried2-member?
(lambda (xs)
(lambda (x)
(member? x xs))))
(define in-mylist? (curried2-member? (list 'auto 'bike 'car 'plane)))
(in-mylist? 'car)
(in-mylist? 'truck)
What do the following functions do?
(define curry
(lambda (f)
(lambda (x)
(lambda (y)
(f x y)))))
(define uncurry
(lambda (f)
(lambda (x y)
((f x) y))))
How do you step through the following application? In particular, what x refers to what?
(define foo
(lambda (x)
(x (lambda (x) x))))
(foo (lambda (x) x))
When defining the evaluation of function application,
we described that the value of the argument is substituted
into the body of the function. How do we describe
substitution when the function body includes another function?
What does the following do?
(define brainteaser
(lambda (nums)
(fold nums identity (lambda (num k) (lambda (n) (k (+ num n)))))))
((brainteaser (list 2 4 6 8)) 0)
Aaaaack!!!! Why would anyone do this?!? Take COMP311 and learn about continuations!
Hint: The last argument is the base case for fold's accumulator. What is accumulated is a description of the rest of the computation to be performed.