Everyone understands that numbers are first class citizens in most programming languages. You can store numbers, you can pass numbers as parameters to a function, and you can return numbers from a function. Novices find it a bit odd that boolean values are also first class citizens in most programming languages including Java, C, C++, Python, and so on. Novices often find it puzzling to think that a variable can store true or false and in intro Java courses students often find it challenging to write methods that have a boolean return type.
In functional languages, functions themselves are first class citizens. We have seen that they can be stored in variables in the sense that we can use a let definition or expression to bind a name to a function. We're about to explore passing functions as parameters and returning functions from a function. We call functions that take other functions as parameters or that return them as their result as higher order functions.
I said that I wanted to add a comparison function to the qsort function we wrote in the previous lecture. I showed it's current behavior using a short list of strings that I had defined:
# t;;
- : string list =
["to"; "be"; "and"; "not"; "to"; "be"; "that"; "is"; "the"; "question"]
# qsort(t);;
- : string list =
["and"; "be"; "be"; "is"; "not"; "question"; "that"; "the"; "to"; "to"]
As expected, it sorts it into alphabetical order. I asked people what
would have to change in order to have qsort take a comparison function
as a parameter. Clearly the header changed. And the two recursive
calls. And the test used in the if/else went from testing "x <=
pivot" to a call on the comparison function.
let rec qsort(f, lst) =
match lst with
| [] -> []
| pivot::rest ->
let rec split(lst, part1, part2) =
match lst with
| [] -> qsort(f, part1) @ [pivot] @ qsort(f, part2)
| x::xs -> if f(x, pivot) then split(xs, x::part1, part2)
else split(xs, part1, x::part2)
in split(rest, [], [])
With this version, we were able to sort the list by string length
instead of alphabetically:
- : string list =
["to"; "be"; "to"; "is"; "be"; "the"; "and"; "not"; "that"; "question"]
But now we weren't able to sort alphabetically. That's because we
have assumed that the comparison function will take a pair of values
and return a boolean value. The built-in operator less-than is of a
different from:
# shorter;;
- : string * string -> bool = <fun>
# (<);;
- : 'a -> 'a -> bool = <fun>
The less-than operator is what is known as a curried function. We'll
discuss that more in the next lecture, but for now we just need to
notice that it expects a different form for the two values to
compare. It is possible to convert a curried function into the
uncurried form:
let uncurry f(a, b) = f a b
With this function available to us, we were able to sort the list of
strings alphabetically and in reverse order:
# qsort(uncurry(<), t);;
- : string list =
["and"; "be"; "be"; "is"; "not"; "question"; "that"; "the"; "to"; "to"]
# qsort(uncurry(>), t);;
- : string list =
["to"; "to"; "the"; "that"; "question"; "not"; "is"; "be"; "be"; "and"]
I then introduced what can be thought of as the "big three" of
higher-order functions: map, filter, and reduce. I mentioned that I
am going to begin by showing versions of these functions that take a
pair (2-tuple) as parameters, like the other functions we've been
writing, but in OCaml we normally use a different version of these
functions that we'll discuss in future lectures.We first looked at map:
let rec map(f, lst) =
match lst with
| [] -> []
| x::xs -> f(x)::map(f, xs)
This function applies a function to every element of a list. I asked
people how to convert from int to float and someone said the function
is called float_of_int. We can map that over a list of int values
obtained using our -- operator:
# map(float_of_int, 1--10);;
- : float list = [1.; 2.; 3.; 4.; 5.; 6.; 7.; 8.; 9.; 10.]
I tried asking for the square root of a list of ints, but that
failed:
# map(sqrt, 1--10);;
Error: This expression has type int list
but an expression was expected of type float list
Type int is not compatible with type float
The sqrt function requires a parameter of type float, so this didn't
work. But we can fix it by first mapping float_of_int over the list
and them mapping sqrt over that:
# map(sqrt, map(float_of_int, 1--10));;
- : float list =
[1.; 1.41421356237309515; 1.73205080756887719; 2.; 2.23606797749979;
2.44948974278317788; 2.64575131106459072; 2.82842712474619029; 3.;
3.16227766016837952]
I pointed out that in a procedural style program we tend to write
command oriented functions like "convert this to double" and "compute
the square root." In a functional language we tend to compose
function calls, as in the example above (f(g(h(...)))).Then I showed the filter function, which takes a predicate function (a boolean test) and a list as arguments and that returns the list of values that satisfy the given predicate. We write it this way:
let rec filter(f, lst) =
match lst with
| [] -> []
| x::xs -> if f(x) then x::filter(f, xs)
else filter(f, xs)
There is a repeated computation of filter(f, xs) that we could factor
out by using a let expression to store the result in a local variable,
but this doesn't introduce the kind of inefficiency problems we saw
with the min function we wrote in an earlier lecture. Here the call
on filter is computed only once in each branch.Using this definition and the function is_prime we wrote in the previous lecture, I was able to ask for primes up to 100:
# filter(is_prime, 1--100);;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97]
The third higher-order function we looked at was reduce. The idea of
reduce is that we often work with binary functions that take two
values and combine them into one. This is true of simple arithmetic
with addition, subtract, multiplication, etc. For example, given two
numbers, we can find their sum. The reduce function takes a list of
values and use a binary function to turn it into a single value, like
the sum of a list.We intially wrote reduce this way:
let rec reduce(f, lst) =
match lst with
| [x] -> x
| x::xs -> f(x, reduce(f, xs))
This produced the following warning:
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
[]
An empty list poses a problem for us. What is the sum of an empty
list of numbers? It seems reasonable to say that it is 0. But what
is the product of an empty list of numbers? We probably want it to be
1 because 1 is the multiplicative identity (we start variables at 1
when we compute a cumulative product).There are several ways to deal with this and we will explore all of them. For now, I called the invalid_arg function.
let rec reduce(f, lst) =
match lst with
| [] -> invalid_arg("empty reduce")
| [x] -> x
| x::xs -> f(x, reduce(f, xs))
Using this we were able to add up the numbers 1 through 10:
# reduce(uncurry(+), 1--10);;
- : int = 55
The key to the reduce function is that it collapes a sequence of values to a
single value, as in the example above of adding them up to get the overall sum.
I asked people for other examples of collapsing operations and we came up with
a rather extensive list:
| function | 1st argument | 2nd argument | returns |
|---|---|---|---|
| map | function mapping 'a to 'b | list of n 'as | list of n 'bs |
| filter | predicate converting 'a to bool | list of n 'as | list of m 'as (m <= n) |
| reduce | function that collapses a tuple 'a * 'a into a single 'a |
list of n 'as | one 'a |
I then spent a few minutes discussing the fact that the reduce function has disappeared from the standard OCaml libraries. We still talk about the idea of a reduce function, but there were too many problems with the standard reduce. First, it doesn't handle empty lists well. The newer versions of reduce include an extra parameter that indicates a "default value" to use for the computation when there is no data to process (the answer for an empty list).
For example, when you are adding, the default value is 0. When you are multiplying, the default value is 1. Second, we sometimes want to make a distinction between processing the list from left-to-right versus processing the list from right-to-left. For many computations it doesn't matter, but when it does matter, it's nice to be able to control which direction it uses. Finally, reduce always reduces to a value of the same type as the original list. For example, lists of int values are reduce to a single int. Lists of strings are reduced to a single string. Sometimes you want to use a reducing function that reduces to some other kind of value.
The new terminology involves thinking of this as a "folding" operation, so the two replacement functions are known as List.fold_left and List.fold_right. They have an extra parameter that is often refered to as an accumulator. For addition, we would start with 0. For multiplication, we would start with 1. For example:
# List.fold_left (+) 0 (1--10);;
- : int = 55
# List.fold_left ( * ) 1 (1--10);;
- : int = 3628800
We were able to collapse our list of strings using this command:
# List.fold_left (^) "text: " t;;
- : string = "text: tobeandnottobethatisthequestion"
Notice how the string "text: " comes first in the resulting string as we fold
from left to right. This became even more clear when I introduced a function
that put parentheses around the strings being concatenated together:
# let paren s1 s2 = "(" ^ s1 ^ ", " ^ s2 ^ ")";;
val paren : string -> string -> string = <fun>
# List.fold_left paren "text: " t;;
- : string =
"((((((((((text: , to), be), and), not), to), be), that), is), the), question)"
You can see more clearly that the leftmost value in our list is the first one
to be concatenated with our initial string "text: ". Not surprisingly, when we
fold from the right the first concatenation involves the last value in our
list. For some reason, OCaml reverses the order of the accumulator and the
list as parameters, so it isn't as simple as changing "left" to "right":
# List.fold_right paren t "text: ";;
- : string =
"(to, (be, (and, (not, (to, (be, (that, (is, (the, (question, text: ))))))))))"
We're written reduce to fold from the right.Then I mentioned that in the early 2000s Google created a system they called MapReduce for performing large scale computations. Operations like map and reduce are relatively easy to split up across multiple processors. So this is one way to do parallel processing without having to think a lot about the fact that you are running on different machines. There was an open source version of MapReduce called Hadoop and Google even gave UW funding for a cluster of machines and to allow us to teach a class on Hadoop programming.
Then I mentioned that Java added functional constructs starting with Java 8 and that they included all of map, filter, and reduce. I have given a lecture on Java 8 features in some of my 143 classes. One of the more interesting bits of that lecture has to do with computing whether various numbers are prime. I wrote this method for testing whether something is prime:
public static boolean isPrime(int n) {
return IntStream.range(1, n + 1)
.filter(x -> n % x == 0)
.count()
== 2;
}
It examines the numbers 1 through n, filtering for numbers that are factors of
n, and it sees whether the count of factors is equal to 2. This matches the
standard mathematical defintion of a prime as an integer that has exactly two
factors (1 and itself). This is not a very efficient version, but it is
interesting how simple it is.The more interesting bit of code involves adding up the sum of prime numbers between 1 and 20,000. I ran the code twice keeping track of how long it took to execute but for the second execution I added a notation ".parallel()" which said to Java that it was allowed to compute this on multiple processors. When I ran this on a machine called barb which is one of the research unix servers in the Allen School, it indicated these times for the two different runs:
n = 21171191, time = 0.743
n = 21171191, time = 0.048
It got the same answer, but the version that was allowed to run in parallel ran
much faster (a little over 15 times faster). That's because we allowed Java to
run it on multiple cores at the same time. I suggested to students that they
download the program and run it on their own machine to see what results they
get.The key point is that functional approaches like using map, filter, and reduce are attractive to software engineers because they allow you to write code that runs in parallel without having to think much about how the tasks are split up across different computers.