(* This version of power is linear in exponent *)
let rec power base exponent =
if exponent = 0 then 1 else base * power base (exponent - 1)
(* This one, on the other hand, is logarithmic *)
let rec power base exponent =
if exponent = 0 then 1
else if exponent mod 2 = 1 then base * power base (exponent - 1)
else power (base * base) (exponent / 2)
(* Many different ways of adding up all elements of a list *)
(* This one isn't tail recursive:
* After getting the result of the recursive call addList tl,
* we need to add hd to it. So we need to keep track of the head of the list at
* each level of recursion. So we'll use stack space proportional to the number
* of elements in the list.
*)
let rec addList lst =
match lst with
| [] -> 0
| hd :: tl -> hd + addList tl
(* This one is tail recursive:
* After getting the recursive result of addList tl (hd + acc), we immediately
* return it without doing anything else to it.
* So this just looks like a loop where you're updating the values of lst and
* acc every time through. This uses constant stack space.
*
* But an obvious disadvantage of this one is that now the caller needs to
* rememver to pass in 0 as the accumulator before summing a list! They
* shouldn't have to remember to do that!
*)
let rec addList lst acc =
match lst with
| [] -> acc
| hd :: tl -> addList tl (hd + acc)
(* Okay, let's make the tail-recursive addList with accumulator a helper
* function to the "real" addList function which will just take a list.
* All the magic happens in my helper function addListAux, and addList just
* sets up the whole show by calling addListAux once.
*)
let addList lst =
let rec addListAux lst acc =
match lst with
| [] -> acc
| hd :: tl -> addListAux lst (hd + acc) in
addListAux lst 0
(* More on pattern matching *)
(* We didn't get to this part this year, but people had many questions on
* pattern matching, so this might have been useful.
*)
(* swapEveryTwo lst swaps every two elements in a list.
* [1; 2; 3; 4; 5] becomes [2; 1; 4; 3; 5]
* Notice how we use pattern matching to take two elements off the list at a
* time.
*)
let rec swapEveryTwo lst =
match lst with
| [] -> []
| hd1 :: hd2 :: tl -> hd2 :: hd1 :: swapEveryTwo tl
| hd :: tl -> lst
(* Notice that pattern matches go from top to bottom. What would have happened
* if we switch the order of two of them?
*)
let rec swapEveryTwoBroken lst =
match lst with
| [] -> []
| hd :: tl -> lst
| hd1 :: hd2 :: tl -> hd2 :: hd1 :: swapEveryTwoBroken tl
(* An underscore means we don't care about what we're binding to. It matches
* anything (that hasn't been matched by an earlier pattern)
*)
let rec swapEveryTwoCondensed lst =
match lst with
| hd1 :: hd2 :: tl -> hd2 :: hd1 :: swapEveryTwoCondensed tl
| _ -> lst
(* Finally, note that it doesn't matter what we name hd1, hd2, and tl. They're
* just names that we're binding values to.
*)
let rec swapEveryTwoFunkyNames lst =
match lst with
| lollerskates :: roflcopter :: lolcano ->
roflcopter :: lollerskates :: swapEveryTwoFunkyNames lolcano
| _ -> lst
(* Fibonacci *)
(* People had trouble with the linear-time fibonacci. It's much harder than
* list reversal. We'll either skip this one in the future, or leave it for the
* very last.
*)
(* This is the terrible exponential-runtime fibonacci function *)
let rec fibonacci n =
if n <= 1 then n else fibonacci (n - 2) + fibonacci (n - 1)
(* Here we use a helper function to do it in linear time *)
let fibonacci n =
let rec fibAux a b n = if n = 0 then a else fibAux b (a + b) (n - 1) in
fibAux 0 1 n
(* List reversal *)
(* This one uses @. But @ is linear in its first argument, so don't do this! *)
let rec reverse lst =
match lst with
| [] -> []
| hd :: tl -> reverse tl @ [hd]
(* We'll use a helper function to remove the @ operator *)
(* It might be confusing that the helper function is named the same as the
* outer function. But since the outer function is non-recursive, all
* instances of reverse refer to the inner (helper) function.
*)
let reverse lst =
let rec reverse lst acc =
match lst with
| [] -> acc
| hd :: tl -> reverse tl (hd :: acc) in
reverse lst []