Higher Order Functions
Due HW: Monday, April 22, PA: Monday, April 22
In this programming assignment we will investigate higher-order functions, or functionals. Recall from Chapter 15 of the text that a higher order function is a function that takes another function as argument, or returns a function as a result. We will do both in the course of this assignment. The book spends a lot of time talking about higher order functions in the Scheme language. We are using common Lisp, and unfortunately some of the syntax is not quite as elegant in Common Lisp as it is in Scheme. We will see this as we go along.
As with programming assignment 1, this programming assignment is divided into three parts. The first part guides you through an investigation of the idea of functionals. The second part is a series of written questions that you will hand in, on paper, as homework number 2. The third part is the actual programming assignment you are to hand in. The programming assignment itself is described near the end of this document. Sprinked throughout the first part will be pointers that indicate when you are ready to attempt solving portions of the programming assignment.
We first investigate functions that take other functions as arguments. The first functional form we will consider is named map. In order to not confuse our version with the built-in function, we will call ours myMap. A map of a list is formed by applying a one-argument function to each element of the list, resulting in a new list containing the function results. For example, suppose we have the initial list (2 a 3 b c 4) and we apply a map using the one argument function numberp. Recall that numberp returns either t or nil, depending upon whether its argument is a number of not. The result of the map would be the list (t nil t nil nil t).
We can define the function myMap as follows:
(defun myMap (fun lst)
(if (null lst) nil
(cons (funcall fun (car lst)) (myMap fun (cdr lst)))))
The function named funcall is specific to common-lisp, it is not found in Scheme (and hence, not found in the discussion in the textbook). The first argument to this function is the function to invoke, which we are here passing as a parameter. The remaining arguments are passed to the function. In this case, we are passing the first element of the list. To form the new result we create a list by concatenting the result to the value yielded by recursively invoking the myMap on the remainder of the list. (See homework question 1).
In addition to the funcall operator, common lisp uses a somewhat unusual syntax when you want to pass a function as an argument. Instead of simply passing the function name (as you do in Scheme), you must prepend the name with the combination of a sharp sign and a square bracket, as in the following:
> (myMap #'numberp '(2 A 3))
Try this and observe the result. (Then answer homework question 2).
The function myMap can be used with your own functions in exactly the same fashion. Remember the function square you wrote in the last homework? We could apply this function to every element of a list as follows:
> (defun square (x) (* x x)) > (myMap #'square '(2 4 3 9))Try this an observe the result.
If you are lucky the function you want to pass as argument to a functional may already exist, as did the square function above. However, often you are not so lucky. Frequently you need a special purpose function. One approach would be to simply define this function, then use it like we did with square. However, more often than not these functions are not useful on their own, and so there is no reason to define them or even give them a name. As the textbook describes, the solution is to define a lambda, a nameless function that you just create specifically as an argument to a functional. The following shows an example of this:
> (myMap '(lambda (x) (+ x 1)) `(2 5 7))
The nameless function being created here takes an argument and returns the value one larger than the argument. Notice that in common lisp we need to quote a lambda expression, something that is not shown in the textbook since it is not necessary in Scheme.
The second functional we will consider is called a reduction. A redunction of a list has two key parts, a binary operation and an identity element. The binary operation is placed between each element of the list and the reduction of the remainder. When the end of the list is encountered the identity is used for the second argument. A simple example is a plus-reduction, which computes the sum of a list. Suppose we have the list (2 3 4). A plus reduction with zero as the identity element would compute the following (writing now in normal infix notation, instead of the Lisp style prefix):
2 + (3 + (4 + 0))
The zero value, the identity, is used as the right argument when we reach the base case; that is, the empty list.
Written as a Lisp functional, the function myReduce will take three arguments, a function, and identity, and the list being reduced. Try writing this function, remembering that you need to use funcall to invoke a function that is passed as argument:
> (defun myReduce (fun ident lst) ... ) > (myReduce #'+ 0 '(2 3 4)) 9
Experiment with various different invocations of myReduce. For example, try the following (the addtoEnd function is the one you created in programming assignment one).
> (myReduce #'* 1 '(2 3 4)) > (myReduce #'cons nil '(a b c)) > (myReduce #'addToEnd nil '(a b c)) > (myReduce #'cons '(p q r) '(a b c))
What happens if you reduce using the function insert we defined in the previous programming assignment?
> (myReduce #'insert nil '(4 6 5 7 2 3))
Recall that mapping a predicate such as number (a predicate is simply a function that returns true or false) yields a list of true and false values:
> (myMap #'numberp `(2 a 3.4 b c 6))
Recall that the logical and function is true only if both arguments are true. For reasons that are too complex to get into here (we will discuss them a bit more in programming assignment 3) you cannot use the function and in a functional, but it is easy to create a new function that can be used:
> (defun funAnd (x y) (and x y))
Can you combine myMap, myReduce and the funAnd function to create a function that will take a list and return true if and only if ALL elements of the list are numbers?
Now do the programming assignment questions that refer to reduce.
The second major category of functionals are functions that return another function as a result. Once again we can do this using the idea of a lambda, this time embedded inside yet another function, named function. The function captures the environment in which it is defined, including the values of any variables named in the function body. Consider, for example, the following definition:
> (defun addX (x) (function (lambda (y) (+ x y))))When we execute addX the thing we get back is a function. We can then execute this function to produce the desired answer. What happens, for example, in the following:
> (myMap (addx 3) '(2 4 6))The two types of functional, functions passed as argument and functions returned as a result, are combined in an object called a curry. The name comes from Haskell P. Curry, a logician from the 1940's who first introduced the concept. The idea of a curry is to redefine a function with two (or more) arguments so that one of the arguments is fixed, resulting in a function that takes only one argument. We did something similar to a curry in programming assignment 0 when we took the two-argument addition function +, and bound one of the arguments to the integer 1, thereby getting the plusOne function.
We generalize the idea in the following, which curries a two argument function by binding the second argument to a constant value:
> (defun currySecond (fun y) (function (lambda (x) (funcall fun x y))))Experiment with curry by creating various different functions and passing them to myMap
> (myMap (currySecond #'+ 2) '(2 3 4)) > (myMap (currySecond #'* 2) '(2 3 4)) > (myMap (currySecond #'- 1) '(2 3 4))Remember the function setIncludes that you wrote for programming assignment 1? If we curry this function we can bind the second argument to a specific set. This gives us a one argument function that is true if the argument is a member of a set. If we then map this result onto another list, we will get a list of true and false values indicating whether or not each element is in the set:
> (myMap (currySecond #'setIncludes `(2 5 6)) `(1 2 3 4 5))Find a way to perform a reduce on the resulting list so that you get the value true if and only if all elements in the resulting map were true. Using this we can write a method to test if a set (represented as a list) is a subset of another set.
The last functional we will investigate is the filter. A filter takes a predicate and a list, and returns a list containing only those elements that satisfy the predicate. For example:
> (filter #'numberp `(2 A 4 3 B))would return the list (2 4 3), those being the only elements that are numbers.
We could write filter as a nested if statement, something like the following pseudo-code
if list is null return null
else
if predicate is true for car of list return cons(car recursive call)
else return recursive call
However, filter gives us a good opportunity to introduce a little bit more of Lisp syntax, namely the generalized condition. The general conditional is useful whenever you have a set of conditions that is more complex than just a simple if-then-else. The conditional takes a series of condition value pairs, and evaluates each in turn. When the first condition is found that is true, the matching expression is returned. Using this form we can write filter as follows:
(defun filter (pred lst)
(cond
((null lst) nil)
((funcall pred (car lst)) (cons (car lst) (filter pred (cdr lst))))
(t (filter pred (cdr lst))) ))
Notice that the always-true value t is used as the final condition. This will
always match if nothing else matches.
Here is an interesting function. It takes a list, and returns all the elements in the remainder of the list that are smaller than the first element:
(defun smallerThanFirst (lst) (filter (currySecond #'< (car lst)) (cdr lst)))Try this on a sample list to see how it works:
> (smallerThanFirst `(4 2 5 3 7 6 2 4))When would such a thing be useful? Remember the quicksort algorithm? This algorithm took a list, and selected a pivot value, which was often just the first element. It then recursively produced two new lists, which were the list of values smaller than the pivot, and the list of values larger than or equal to the pivot. Each of these can be generated using a filter. It then called itself recursively on each of these two lists. Finally, it tacked the results back together, placing the pivot in the middle. We can use a combination of append and cons to do the putting back together. Thus the framework for quicksort is something like the following:
(defun quickSort (lst)
(if (null lst) nil
(append (quicksort ....)
(cons (car lst) (quicksort ...)))))
Fill in the missing pieces to create the quicksort algorithm.
This section presents the written homework questions. You should hand in a paper in which you answer the following questions:
(myReduce #'cons nil `(2 3 4)) (myReduce #'addToEnd nil `(2 3 4)) (myReduce #'cons `(7 8 9) `(2 3 4))
> (myReduce #'insert nil `(4 6 5 7 2 3))
(myMap (addX 3) `(2 4 6))
(myMap (currySecond #'- 1) `(2 3 4))