(* 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 []