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! Please adjust your DrScheme language level, and restart it.
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.
; twice-apply : (alpha->alpha) alpha -> alpha
(define twice-apply
(lambda (f arg)
(f (f arg))))
Q: What is the result of (twice-apply add1 5)?
Ok, I'd also like to just give the function, e.g., add1, and get back a new function add2 that applies it twice to something. 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.
; twice : ?? (see question below)
(define twice
(lambda (f)
(lambda (arg) ; the function returned
(f (f arg)))))
One way to use this is
(define add2 (twice add1)) (add2 5)but if we don't want to add two to a bunch of numbers, why bother naming this function add2? We can also say ((twice add1) 5).
Q: What is the contract for twice?
Q: Do our Laws of Scheme tell us how to evaluate ((twice add1) 5)?
We are familiar with writing functions such as
; double-nums : list-of-number -> list-of-number
(define double-nums
(lambda (nums)
(if (empty? nums)
empty
(cons (* 2 (first nums)) (double-nums (rest nums))))))
; lessthan3-nums : list-of-number -> list-of-boolean
(define lessthan3-nums
(lambda (nums)
(if (empty? nums)
empty
(cons (< (first nums) 3) (lessthan3-nums (rest 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:
; map : ?? (see question below)
(define map
(lambda (f xs)
(if (empty? xs)
empty
(cons (f (first xs)) (map f (rest 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.
Q: What is the template for map?
Q:
How can you write double-nums in one line using map
but without double-num?
A:
Just plug the function to map into the definition:
; double-nums : list-of-number -> list-of-number
(define double-nums
(lambda (nums)
(map (lambda (num) (* 2 num)) nums)))
To do: Using Donkey, evaluate (double-nums (list 2 4 6)) 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 empty and cons to make the result list. Instead, we use new function arguments base and combinef as our base case and combining function:
; map-and-fold : (alpha -> beta) list-of-alpha beta (beta beta -> beta)
; -> list-of-beta
(define map-and-fold
(lambda (f xs base combinef)
(if (empty? xs)
base
(combinef (f (first xs))
(map-and-fold f (rest xs) base combinef)))))
; map : (alpha -> beta) list-of-alpha -> list-of-beta
(define map
(lambda (f xs)
(map-and-fold f xs empty 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 +)))
Q: How would you use map-and-fold to define a function to multiply all the numbers in a list?
(Note: Mathematicians will notice the use of a ring algebra in those examples. Higher math can be useful to computer scientists.)
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).
; fold : ?? (see question below)
(define fold
(lambda (xs base combinef)
(map-and-fold identity xs base combinef)))
or, equivalently,
; fold : ?? (see question below)
(define fold
(lambda (xs base combinef)
(cond [(empty? xs) base]
[else (combinef (first xs)
(fold (rest xs) base combinef))])))
Then,
(define sum (lambda (nums) (fold nums 0 +))) (define prod (lambda (nums) (fold nums 1 *)))
Q: What is the contract for fold? Hint: It's a simplification of that for map-and-fold.
To do: Using Donkey, evaluate (sum (list 2 4 6)) for this definition, and compare it to the previous evaluation. As with our direct implementation we did previously, we eventually get to the computation (+ 2 (+ 4 (+ 6 0))).
Here are two more functions we know, now defined using fold:
(define add1-to-2nd (lambda (n1 n2) (add1 n2)))
(define length (lambda (xs) (fold xs 0 add1-to-2nd)))
; contains? : alpha list-of-alpha -> boolean
(define contains?
(lambda (x xs)
(fold xs #f (lambda (xx b) (or (eq? xx x) b)))))
(Note: This definition of fold is equivalent to Scheme's built-in function foldr ("fold right-associatively") except that it takes the arguments in the opposite order.)
Functions like collect (seen in lecture), 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:
; map-each-fun1 : (alpha -> beta) list-of-alpha -> ??
(define map-each-fun1
(lambda (fs ls)
(map (lambda (f)
(map f ls))
fs)))
; map-each-fun1 : (alpha -> beta) list-of-alpha -> ??
(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))
Q:
What's the difference between these? What are the contracts?
We previously saw this insertion sort (with different function names):
; insert<-num : number list-of-number -> list-of-number
; assumes the input list is sorted non-descending
; returns a new sorted non-descending list with the input number in it
(define insert<-num
(lambda (num nums)
(if (empty? nums)
(cons num empty)
(if (< num (first nums))
(cons num nums)
(cons (first nums) (insert<-num num (rest nums)))))))
; isort<-nums : list-of-number -> list-of-number
; returns a new sorted non-descending version of the input list
(define isort<-nums
(lambda (nums)
(if (empty? nums)
empty
(insert<-num (first nums) (isort<-nums (rest nums))))))
We might want to abstract this because it only sorts numbers in
non-descending order (because of the test <). The following
sorts whatever you specify, as long as you give it an appropriate
comparison operator:
; insert : alpha list-of-alpha (alpha alpha -> boolean) -> list-of-alpha
; assumes the input list is sorted by comparef
; returns a new sorted (by comparef) list with the input value in it
(define insert
(lambda (x xs comparef)
(if (empty? xs)
(cons x empty)
(if (comparef x (first xs))
(cons x xs)
(cons (first xs) (insert x (rest xs)))))))
; isort : list-of-alpha -> list-of-alpha
; returns a new sorted (by comparef) version of the input list
(define isort
(lambda (xs comparef)
(if (empty? xs)
empty
(insert (first xs) (isort (rest xs) comparef) comparef))))
(define my-sort isort)
; sort a list of numbers in non-descending order
(my-sort (list 2 98 43 1) <)
; sort a list of lists in non-descending order of lengths
(my-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))))
To do: Try these examples and some of your own. E.g., try sorting a list of numbers in non-ascending order.
Q:
Why did I introduce my-sort?
A:
We could simply change the
one definition of my-sort, say to be a mergesort routine,
and all of our examples would then be using 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?
; make-adder : number -> (number -> number)
(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 twice-apply and twice as examples of this.
Above we defined a verson of contains?, 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 contains? helps:
; curried1-contains? : ?? (see question below)
(define curried1-contains?
(lambda (x)
(lambda (xs)
(contains? x xs))))
(define is-car-contains? (curried1-contains? 'car))
(is-car-contains? (list 'auto 'bike 'car 'plane))
(is-car-contains? (list 'hydroplane 'pogostick 'truck))
Alternatively, we might want to check a bunch of different symbols to see if they are in a list:
; curried2-contains? : ?? (see question below)
(define curried2-contains?
(lambda (xs)
(lambda (x)
(contains? x xs))))
(define in-mylist? (curried2-contains? (list 'auto 'bike 'car 'plane)))
(in-mylist? 'car)
(in-mylist? 'truck)
Q: What are the contracts for curried1-contains? and curried2-contains??.
Q: What do the following functions do?
; curry : (alpha beta -> gamma) -> (alpha -> (beta -> gamma))
(define curry
(lambda (f)
(lambda (x)
(lambda (y)
(f x y)))))
; uncurry : (alpha -> (beta -> gamma)) -> (alpha beta -> gamma)
(define uncurry
(lambda (f)
(lambda (x y)
((f x) y))))
To do: Step through the following application using Donkey or by hand. What does it do?
(define foo
(lambda (x)
(x (lambda (x) x))))
(foo (lambda (x) x))
Q:
Which x refers to what?
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?
Q: What does the following do? Can you finish its contract?
; brainteaser : list-of-number -> ?? (see question above)
(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! It's weird, but it can be very useful.
Hint: The last argument acts as an accumulator, even though it's a function. What is accumulated is a description of the rest of the computation to be performed.