section Examples
Here are some cumulative "problems" that cover some general ideas from this section. I include answers and sometimes rationale. Note that these examples may draw on information not directly found in the actual material that I've written. This is likely a pedagogical error, but consider this section in part a supplement rather than a full review.
Example: The Fibonacci sequence. We want a function that produces the nth Fibonacci number. For any n less than 1, just output 0.
The Fibonacci sequence is defined recursively. The nth Fibonacci number is the sum of the two Fibonacci numbers that precede it. That means our function definition should also be recursive.
We should probably identify some base cases where our recursive definition doesn't work. Those would likely be the 0th and 1st Fibonacci numbers. The first Fibonacci number is 0 and the 0th is essentially any numbers below 1 which we'll return 0 for.
That means our function looks something like the following.
We should probably identify some base cases where our recursive definition doesn't work. Those would likely be the 0th and 1st Fibonacci numbers. The first Fibonacci number is 0 and the 0th is essentially any numbers below 1 which we'll return 0 for.
That means our function looks something like the following.
let rec fibonacci n =
if n < 1 then 0
else if n = 1 then 1
else (fibonacci (n - 1)) + (fibonacci (n - 2))
;;
What should our type signature be?
Example: Reverse a List.
Reversing a list is pretty straight forward. We take each element off the head of the list and (in the order we get them) put them into another list. (I use the words take and put loosely, as we never mutate any lists).
Since we would imagine this function to be recursive, we should make this function tail recursive in an attempt to have solid coding. As we've seen, in order to generate a tail recursive function, we should probably have our function use an accumulator.
Now what should our base case be? The empty list probably. In the case of the empty list, we should probably return the accumulator. In any other case, we should append the head of the list to the accumulator and continue reversing the remaining list.
Let's see our this tail recursive function might look.
Since we would imagine this function to be recursive, we should make this function tail recursive in an attempt to have solid coding. As we've seen, in order to generate a tail recursive function, we should probably have our function use an accumulator.
Now what should our base case be? The empty list probably. In the case of the empty list, we should probably return the accumulator. In any other case, we should append the head of the list to the accumulator and continue reversing the remaining list.
Let's see our this tail recursive function might look.
let rec reverse lst acc =
match lst with
| [] -> acc
| hd :: tl -> reverse tl (hd :: acc)
;;
And let's test out our function.
reverse [10;9;8;7;6;5;4;3;2;1];;
- : int list -> int list = <fun>
That's not exactly what we expected. I forgot to include our default accumulator, the empty list ([]). We should probably write a shell around this helper function just so other people don't need to go through the hassle of including the empty list every time.
let reverse lst =
let rec helper list acc =
match list with
| [] -> acc
| hd :: tl -> helper tl (hd :: acc)
in
helper lst []
;;
So now when we attempt to test our function, we get the following:
reverse [10;9;8;7;6;5;4;3;2;1];;
- : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]
Example: List Merging. Take two sorted int lists and merge them together so that the numbers appear in order from smallest to largest. We can use this as part of merge sort if we wanted to. We should assume that the inputs are sorted as an invariant.
This should probably involve getting the head off of both lists and comparing them. Maybe we should have an accumulator for the remaining list, for tail recursion purposes (We won't achieve full tail recursion in every part of our function, but we should attempt to make our code as resilient as possible). So what should our base cases be, etc.?
More to come.