I first mentioned that you can use a pattern in a let definition:
# let x = (17.5, "hello");;
val x : float * string = (17.5, "hello")
OCaml provides functions called fst and snd that will return the first
and second value from a pair like this:
# fst(x);;
- : float = 17.5
# snd(x);;
- : string = "hello"
I almost never use those functions because I prefer to use the pattern
matching mechanism:
# let (a, b) = x;;
val a : float = 17.5
val b : string = "hello"
OCaml sees the pattern for a pair on the left side of the equals sign
and it has to match that to x which is the pair (17.5, "hello").
OCaml tells you that it can resolve this match by setting a to 17.5
and setting b to "hello". In this case, because we used a let
definition, the bindings for a and b are introduced in the top-level
environment. But you can also use pattern matching in a let
expression in which case the bindings apply only to the expression.
For example:
# let (a, b, _) = (17, 24, "foo") in a + b;;
- : int = 41
In this case a and b are local to this expression. Notice the use of
the underscore. It is normal practice to use the underscore when you
aren't going to be using the value later. It is considered a wildcard
that matches anything, but because it doesn't have a name, it can't be
used in forming an expression. In this case it's a way of saying,
"There will be a third thing, but I don't care what its value is."Patterns can also be used to describe lists. Here are some examples of patterns and their interpretation:
As an example, we wrote a function to compute the fibonacci sequence. we know that the Fibonacci sequence begins with the values 1, 1 and that each subsequent value is the sum of the previous two. We could write this with an if/else:
let rec fib(n) =
if n <= 2 then 1
else fib(n - 1) + fib(n - 2)
but we can also write this as a series of three cases, each with a different
pattern:
let rec fib(n) =
match n with
| 0 -> 1
| 1 -> 1
| n -> fib(n - 1) + fib(n - 2)
This is like a great big nested if/else construct. We would read this
expression as, "If n is 0, then the answer is 1, else if n is 1, then
the answer is 1, else the answer is fib(n-1) + fib(n-2). It is
generally considered good style to line up the arrows for each of the
different cases.I mentioned that this version of the fibonacci calculation is highly inefficient. It's complexity is a variation of the fibonacci sequence itself, which is exponential. I asked people how they would compute it in a language like Java and someone said that they'd have a loop that keeps track of the two most recently computed values from the sequence. The loop itself would be controlled by some value indicating which number in the sequence to compute. So we want a helper function with three parameters: a number indicating how many more values to compute and the two most recent values computed. I left this as an exercise for people to work on, but the solution is described at the end of these notes for those who want to see a solution.
Then I pointed out that the function called last that we wrote earlier turns out to be inefficient. We had written it this way:
let rec last(lst) =
if lst = [] then invalid_arg("empty list")
else if List.length(lst) = 1 then List.hd(lst)
else last(List.tl(lst))
I used the infix -- operator we discussed previously to test this
function by calling last(1--100000) and found that didn't come back
with an answer for a very long time. The problem, it turns out, is
that while List.hd and List.tl are constant time operations (executing
quickly no matter how many elements are in the list), the List.length
function is an O(n) operation. So this version of the last function
ends up being an O(n^2) operation.We could rewrite it by testing whether the tail of the list is the empty list, but it's also easy to rewrite it with pattern matching:
let rec last(lst) =
match lst with
| [] -> invalid_arg("empty list")
| [x] -> x
| x::xs -> last(xs)
This version ran quickly even when we asked for the last value of a
list that is one million long.Then we wrote a function to find the minimum value in a list. I asked what would be the easiest list to find the minimum of and someone said a list of one element. And for a list of more than one element, we can test to see whether the first value in the list is smaller than the minimum of the rest of the list. So we started with this version:
let rec min(lst) =
match lst with
| [x] -> x
| x::xs -> if x < min(xs) then x
else min(xs)
We got this response from the OCaml interpreter:
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
[]
This was only a warning, so it didn't prevent our code from running.
When you have a match expression, OCaml will let you know if your
patterns are not exhaustive. In this case, it is letting us know that
we missed the case of an empty list. For an empty list, we really
can't compute a minimum. There are several options for how to handle
this, but the easiest thing to do right now is to introduce a
precondition and to raise an exception if the precondition is not
satisfied. We do so by calling the invalid_arg function passing it a
string to display.
(* pre: lst is not empty *)
let rec min(lst) =
match lst with
| [] -> invalid_arg("empty list")
| [x] -> x
| x::xs -> if x < min(xs) then x
else min(xs)
With this extra case, we no longer got a warning. But this version of
the function turns out to be very inefficient. I tried asking the
interpreter to evaluate:
min(count_down(30))
it eventually figured out that the minimum is 0, but it took a long
time to compute. That's because the min function potentially
recomputes the recursive minimum twice. Giving it a list in reverse
order guarantees that it will always call it twice. Think of the
final branch as saying, "If the first value is less than the minimum
of the rest of the list (which it never will be in this case) then
return the minimum of the rest of the list."Consider this case where the list has 30 elements. To compute its minimum, we twice compute the minimum of the 29-element list that is the tail of this list. Each of those two calls requires two calls to find the minimum of the 28-element list that is tail of that list. There is a doubling going on where each recursive call is done twice as often as the one before. So this requires something on the order of 230 which is approximately 109 or a billion. No wonder it is taking a long time.
So how do we solve this problem? Someone asked if we can compute the recursive minimum once and store it in a variable. That's exactly what the let expression allows you to do:
(* pre: lst is not empty *)
let rec min(lst) =
match lst with
| [] -> invalid_arg("empty list")
| [x] -> x
| x::xs -> let m = min(xs)
in if x < m then x
else m
This version did not produce any warnings and worked well even when we
asked for min(count_down(1000)).Then we discussed how to write functions to return the values from a list in odd positions. I said that we'd assume that we are using one-based indexing, so the values in odd positions are the first, third, fifth, and so. Using patterns, we wrote the following function for odds:
let rec odds(lst) =
match lst with
| [] -> []
| [x] -> [x]
| x::y::zs -> x::odds(zs)
As a final example, I talked about writing a split function that would split a
list into two lists: those in odd positions and those in even positions. Since
it has to return two things, we'll assume it returns a tuple. For example, the
call split([1; 8; 6; 4; 9]) should return ([1; 6 9], [8; 4]). Someone said
that we could modify our odds function and write a similar evens function and
then define split as follows:
let split(lst) = (odds(lst), evens(lst))
That would work, but it would be inefficient. It would scan through the list
twice when it only needs to do so once. So we started to write it from
scratch. We included a case for the empty list:
let rec split(lst) =
match lst with
| [] -> ([], [])
and then I asked people to think about the general case where we have at least
two values:
let rec split(lst) =
match lst with
| [] -> ([], [])
| x::y::zs -> ?
I asked how we write this. Someone suggested that we make a recursive call
passing in zs. That seems like a good idea. But then what do we do with the
result? The result is a tuple. That's not particularly easy to work with. We
could store the tuple in a variable using let:
let rec split(lst) =
match lst with
| [] -> ([], [])
| x::y::zs -> let result = split(zs)
in ?
This would work, but we'd still have to pull apart the resulting
tuple. We can do even better by using a pattern that mentions the two
parts of the tuple:
let rec split(lst) =
match lst with
| [] -> ([], [])
| x::y::zs -> let (lst1, lst2) = split(zs)
in ?
This will recursively split the list and then bind the variables lst1
and lst2 to be the two parts of the resulting tuple. The overall
result in this case is a new tuple that puts x at the front of lst1
and y at the front of lst2:
let rec split(lst) =
match lst with
| [] -> ([], [])
| x::y::zs -> let (lst1, lst2) = split(zs)
in (x::lst1, y::lst2)
When we tried to load this into the interpreter, we got the warning that the
matches are not exhaustive. I said that for functions, you want to pay close
attention to this. Maybe it's okay because you have a precondition that a
certain case won't happen, but then be sure you've thought about it. In this
case, when we tried to split a list, we got an error when we tried
split a list of odd length:
# split([1; 2; 3]);;
Exception: Match_failure ("//toplevel//", 2, 12).
The problem is that we need a case in the original for a one-element
list. In fact, OCaml had told us as much when it said that we had
overlooked the possible case of "_::[]". Remember that the underscore
(_) is a wildcard so this expresion would be equivalent to [_], which
is a way of describing the one element list. So we added a case for
that:
let rec split(lst) =
match lst with
| [] -> ([], [])
| [x] -> ([x], [])
| x::y::zs -> let (lst1, lst2) = split(zs)
in (x::lst1, y::lst2)
This version of the function worked fine.We didn't discuss the following in lecture, but I include it here for those who want to understand how to write an efficient version of the fib function. We had written it this way:
let rec fib(n) =
match n with
| 0 -> 1
| 1 -> 1
| n -> fib(n - 1) + fib(n - 2)
As with our min function, this one recomputes many values. In the
general case (the last one), it computes a Fibonacci number by
computing two previous ones, both of which will tend to require computing
two previous ones, and so on. It isn't quite as inefficient as min,
but it's close (it's actually an exponential that is a slight
variation of the Fibonacci sequence itself).Here we need something extra. The key is to keep track of two values from the sequence that you update over and over. Our function has only one parameter, so it won't allow us to keep track of a changing pair of values. The solution is to introduce a helper function. We can pass it a pair of values and an indication of how many more computations to perform. We'd still have a base case for n of 1 or 2, in which case we return 1 (because the sequences starts with two 1s). But we can allow the helper function to compute the remaining values in the sequence:
let fib(n) =
if n <= 2 then 1
else fib_helper(n - 2, 1, 1)
For the helper function, we can compute pairs of values from the
sequence the appropriate number of times, and when we get down to 0
computations left, we can return the computed value from the
sequence:
let rec fib_helper(n, fib1, fib2) =
match n with
| 0 -> fib2
| n -> fib_helper(n - 1, fib2, fib1 + fib2)
This version can efficiently compute the result even for large values
of n. We can do even better by hiding the helper function inside of
the fib function with a let expression:
let fib(n) =
let rec fib_helper(n, fib1, fib2) =
match n with
| 0 -> fib2
| n -> fib_helper(n - 1, fib2, fib1 + fib2)
in if n <= 2 then 1
else fib_helper(n - 2, 1, 1)