I then reminded people of the idea I mentioned in the previous lecture that functions are first class citizens. That means that they can be stored in variables, as we do when we bind a name to a function definition. They can also be passed as parameters, as we saw with map, filter, and reduce. They can also be returned by a function and that is one of the ideas we want to explore in this lecture.
Passing tuples as parameters is not the usual approach for OCaml. Instead we tend to write what is known as a curried function. Then we turned our attention to curried functions. I mentioned that this concept seems to lead to some controversy. Some people really appreciate the power you get with curried functions. Others find that it leads them to a level where the air is so thin that they have trouble breathing. In any event, it is an interesting idea to explore and most of the standard OCaml functions are written this way, so we need to understand it.
Up to now we've been writing functions of two arguments using a tuple, as in:
# let sum(x, y) = x + y;;
val sum : int * int -> int = <fun>
Notice the response from OCaml. We know from the "->" arrow that we have a
function. It converts an int * int tuple into an int. But let's see
how OCaml describes the built-in plus operator:
# (+);;
- : int -> int -> int = <fun>
This is the curried version of the function. Notice the response this
time. We have two arrows ("->"). OCaml is telling us that this
version of sum is a function that takes just a simple int as an
argument. That function returns a function that maps an int into an
int. So instead of thinking of it as a single function that takes a
tuple, we think of it as a function that returns a function. When we
call it, we don't use parentheses and OCaml evaluates it from left to
right:
(+) 3 5 = ((+) 3) 5 = (a function that adds 3 to something) 5 = 8Notice how in evaluating ((+) 3), OCaml produces a new function. This new function is then applied to the number 5. Someone asked why a curried function is helpful. I said that it allows you to partially instantiate a function. For example, we can define an incrementing function and a doubling function as follows:
# let inc = (+) 1;;
val inc : int -> int = <fun>
# let double = ( * ) 2;;
val double : int -> int = <fun>
In the second case, we had to include spaces around the * operator so that
OCaml wouldn't think this is a comment.OCaml is very flexible in terms of converting a curried function into an uncurried function and vice versa. For example, we wrote these functions to produce an uncurried version of a curried function or to produce a curried version of an uncurried function:
let uncurry f (a, b) = f a b
let curry f a b = f(a, b)
For example, our version of reduce expects an uncurried function. So to use
the built-in arithmetic operators with our version, you would have to ask for
the uncurried version of the function, as in:
# reduce(uncurry(+), 1--10);;
- : int = 55
In fact, the only difference between the versions of map and filter I have
shown and the standard List.map and List.filter versions is that the standard
versions are curried functions. Here are calls on the standard version in
curried form versus our version that expects a tuple:
# List.map float_of_int (1--10);;
- : float list = [1.; 2.; 3.; 4.; 5.; 6.; 7.; 8.; 9.; 10.]
# map(float_of_int, 1--10);;
- : float list = [1.; 2.; 3.; 4.; 5.; 6.; 7.; 8.; 9.; 10.]
Then we reviewed the use of higher-order functions, particularly map, filter
and reduce. The standard List module includes map and filter. Instead of
reduce the List module has two functions called fold_left and fold_right. The
fold_left and fold_right functions are more general than reduce and that makes
them more versatile. It's still a good idea to study the simpler reduce
function because it's part of common terminology. For example, the Python
programming language includes all of map, filter and reduce and when Java
introduced functional constructs starting with Java 8 they included various
utilities called map, filter, and reduce.In the previous lecture we looked at each function and its implementation (included in a file called utility.ml that I'm using to collect together some of these common utility functions). Remember that the map function applies a function to each value in a list. For example, we had a double call on map to convert a list of ints into floats and then to apply the sqrt function to each:
# 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]
You can also map a function you define over a list. For example, instead of
calling map twice, we can define a function that does both the square root
computation and the conversion and then we can call map using that named
function:
# let f(x) = sqrt(float_of_int(x));;
val f : int -> float = <fun>
# map(f, 1--10);;
- : float list = [1.; 1.41421356237309515; 1.73205080756887719;
2.; 2.23606797749979; 2.44948974278317788; 2.64575131106459072;
2.82842712474619029; 3.; 3.16227766016837952]
This is even easier to write with what is known as an anonymous function.
Anonymous functions are sometimes refered to as lambdas. Python, for example,
uses the keyword "lambda" to define anonymous functions. The basic syntax
involves the keyword "fun" and the arrow symbol we have seen in pattern
matching. The general form is:
fun x -> sqrt(float_of_int(x))
I read this as, "A function that maps x into sqrt(float_of_int(x))."You can also define an anonymous function on a tuple, as in:
fun (x, y) -> x + y
which I read as, "A function that maps (x, y) into x + y."Using an anonymous function, we can rewrite our call on map to be:
map((fun x -> sqrt(float_of_int(x))), 1--10)
We had to include parentheses around the anonymous function. This will often
be the case in OCaml because of its precedence rules.We then used an anonymous function to find all multiples of 3 up to 50 using the filter function:
# filter((fun x -> x mod 3 = 0), 1--50);;
- : int list = [3; 6; 9; 12; 15; 18; 21; 24; 27; 30; 33; 36; 39; 42; 45; 48]
We saw that the reduce function collapses a list to a single value given a
function that collapses two values into a single value. We can use an
anonymous function for adding two numbers to add up all the numbers 1 to
100:
# reduce((fun (x, y) -> x + y), 1--100);;
- : int = 5050
We saw earlier that you can get the same functionality by passing the uncurried
version of the plus operator.As a challenging problem, I asked people to think about how we could write a function that would return Pascal's triangle. The rows of Pascal's triangle show the coefficients of the expansion of:
(x + y)nAs in:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
We'll return it as a list, so that the call triangle(5) should return:
# triangle(5);;
- : int list list = [[1]; [1; 1]; [1; 2; 1]; [1; 3; 3; 1];
[1; 4; 6; 4; 1]; [1; 5; 10; 10; 5; 1]]
The idea is to return the triangle up to row n. There is a row 0 that contains
just the number 1. I pointed out that the numbers in Pascal's triangle are
known as the binomial coefficients or "n choose m". This is also referred to
as the number of combinations of n items taken m at a time. In Excel, for
example, this is computed with a function called "combin".So we began by writing the combin function. If you look at Pascal's triangle, you will notice that each row begins and ends with a 1. These are the cases where m is either 0 or n. In terms of choosing items, this makes sense because there is only way way to choose 0 items or to choose all n items. So that gave us our base case:
let rec combin(n, m) =
if m = 0 || n = m then 1
else ...
For the recursive case, we can use another property of Pascal's triangle that
each value in row n is the sum of two values from the previous row. We can
also see this by thinking about choosing items. Suppose that we start with n
items and we want to choose m from those n. Consider a single item from among
the n. It is either in the list of chosen items or it isn't. If it isn't one
of our base cases, then both are possible. If it is among the m items we are
choosing, then there are m-1 items left to choose from the remaining n-1 items.
If it is not among the m items we are choosing, then there are m items left to
choose from the remaining n-1 itemsw. This is easily translated into a
recursive case:
let rec combin(n, m) =
if m = 0 || n = m then 1
else combin(n - 1, m - 1) + combin(n - 1, m)
So how do we use this to construct the triangle? Overall the triangle is a
list of rows:
[row 0; row 1; row 2; ...; row n]
I asked how we could get something like that and someone said that we could map
over the list 0--n:
let triangle(n) = map((fun x -> produce row x), 0--n)
This is a good start. It produces a list of the correct length with a
structure that will allow us to generate the different rows. Now we just have
to figure out how to generate row x for an arbitrary x. I said to consider 3
as an example. It ends up having 4 values. They come from:
[3 choose 0; 3 choose 1; 3 choose 2; 3 choose 3]
In other words, we want all of the binomial coefficients with 3 as the first
argument and the various values 0 through 3 as the second argument. This can
also be accomplished with a map. In producing row x, we want to map over the
values 0 through x:
map((fun y -> something), 0--x)
To fill in "something", we have to recognize that we want "x choose y", which
is simply a call on our combin function:
map((fun y -> combin(x, y)), 0--x)
This is the code for producing row x, so we put it into our previous
expression:
let triangle(n) =
map((fun x -> map((fun y -> combin(x, y)), 0--x)), 0--n)
This short function produces the rows of Pascal's triangle. I told people that
I think it's challenging to learn to write code this way and when you're first
learning, this code can be difficult to read. But I'm always impressed at how
concisely I can write some computations that seem very complex. There is
certainly no way to solve this problem with one line of code in Java with or
without a combin function.I then considered a short problem. What if you wanted a list of the square roots of the numbers 1 through 100 rounded to the nearest integer? You can use an anonymous function to do so:
# map((fun x -> Float.round(sqrt(float_of_int(x)))), 1--25);;
- : float list =
[1.; 1.; 2.; 2.; 2.; 2.; 3.; 3.; 3.; 3.; 3.; 3.; 4.; 4.; 4.; 4.; 4.; 4.; 4.;
4.; 5.; 5.; 5.; 5.; 5.]
Even though these are rounded to the nearest integer, they aren't ints, so we
would need yet another function call to turn these into ints:
# map((fun x -> int_of_float(Float.round(sqrt(float_of_int(x))))), 1--25);;
- : int list = [1; 1; 2; 2; 2; 2; 3; 3; 3; 3; 3; 3; 4; 4; 4; 4; 4; 4;
4; 4; 5; 5; 5; 5; 5]
This works, but there is a better way. Veteran OCaml programmers would say,
"Why introduce an anonymous function when you're just combining a set of
functions that already exist?" Notice the pattern we have in this function
where one function calls the other which calls the other, as in:
f(g(h(x)))Mathematicians refer to this as composition of functions and we can define an OCaml operator that allows you to more easily compose functions. I asked for suggestions of what special characters to use to make this an infix operator and someone suggest "<=" as a way to make it clear that the application of the functions occurs from right to left. This is easy to define in OCaml:
let (%) f g parameters = f(g(parameters))
Because we are using a parenthesized symbol in defining this function, OCaml
knows that we want this to be an infix operator. There are some fairly
esoteric rules about what combinations of characters can be used for such an
operator that I won't repeat here.Using this operator, we were able to rewrite our previous call on map to be:
# map(int_of_float % Float.round % sqrt % float_of_int, 1--25);;
- : int list =
[1; 1; 2; 2; 2; 2; 3; 3; 3; 3; 3; 3; 4; 4; 4; 4; 4; 4; 4; 4; 5; 5; 5; 5; 5]
Notice that we have formed an expression using the "%" operator that refers to
four different functions and that evaluates to a new function. Welcome to
functional programming. Here we are really seeing how functions are first
class citizens.As a final example, we used function composition and the curried versions of plus and times to define a function that computes (2 * n + 1):
# let f = (+) 1 % ( * ) 2;;
val f : int -> int = <fun>
It is easy enough to test this with a call on map:
# map(f, 1--10);;
- : int list = [3; 5; 7; 9; 11; 13; 15; 17; 19; 21]
This function definition is equivalent to saying:
let f(n) = 2 * n + 1
I ended by spending a few minutes in the Python interpreter to demonstrate that
many of these ideas have crossed over into Python. The Python interpreter has
the functions map, filter, and reduce, and it will tell you so:
>>> map
<built-in function map>
>>> filter
<built-in function filter>
>>> reduce
<built-in function reduce>
Python has a function called "range" that serves the same purpose as our --
operator. If you ask for range(n) you get the numbers 0 through (n-1). If you
ask for range(m, n) you get the numbers m through (n-1):
>>> range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> range(1, 11)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Using map, you can do the kinds of computatins we've been doing.
You can also declare an anonymous function using the keyword "lambda":
>>> map(lambda n : 2 * n, range(1, 11))
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
The notation is very similar to OCaml's. We are saying that we want an
anonymous function (a lambda) that maps n into (2 * n). Python separates those
with a colon rather than an arrow, but the idea is the same.I pointed out how you can define a function called factors that filters the numbers 1 through n for the factors of a number:
>>> def factors(n):
... return filter(lambda m : n % m == 0, range(1, n+1))
...
This gives us a list of the factors of a number, as in:
>>> factors(24)
[1, 2, 3, 4, 6, 8, 12, 24]
>>> factors(30)
[1, 2, 3, 5, 6, 10, 15, 30]
>>> factors(47)
[1, 47]