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!
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.
We've gathered a bunch of sample functions on numbers, e.g., f2c, c2f, add2, double. (These functions are from lectures.) Let's say we have a list of these: (list f2c c2f add1 double).
We also like to map these functions over lists, e.g., (map f2c (list 2 8 143 53)). Because we're obsessed, we want to map each of these functions over a bunch of lists:
(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 f2c c2f add1 double) (list 2 8 143 53))
(map-each-fun2 (list f2c c2f add1 double) (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))))
; sort a list of numbers in ascending order
(isort (list 2 98 43 1) <)
; sort a list of numbers in decending order
(isort (list 2 98 43 1) >)
; sort a list of lists in ascending order of lengths
(isort (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.
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.
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!