Ocaml Review Part 2

Tail Recursion!

Tail recursion doesn't imply that a function has to be recursive to be tail recursive.
As long as a return value is immediately returned to the caller.

For example,

function foo1(data) {
    return a(data) + 1;
}

Is tail recursive because the return value of a is not in the tail position (return position of the current function).

function foo2(data) {
    var ret = a(data);
    return ret;
}

function foo3(data) {
    var ret = a(data);
    return (ret === 0) ? 1 : ret;
}

(Taken from http://en.wikipedia.org/wiki/Tail_call).

However these are not tail recursive because the return value of a is not in tail position.

(* assoc - finds the first matching key and returns value o.w. value *)
let rec assoc(value, key, list)= match list with
|[] -> value
| (key', value')::tail -> if key = key' then value'
                  else assoc(value, key, tail);;

(* remove duplicates *)
let removeDuplicates(list') =
  let rec removeDuplicatesHelper(list) = match List.rev(list) with
  |[]->[]
  |head::tail -> if List.mem head tail then
                  removeDuplicatesHelper(List.rev(tail))
                 else [head]@removeDuplicatesHelper(List.rev(tail))
  in List.rev(removeDuplicatesHelper(list'));;

Struggled a little with this one. I tried to do it without the Helper, but it wasn't doable because I would call List.rev(else [head]@removeDuplicatesHelper(List.rev(tail))) which reversed every substring being returned from the recursion.

I did it another way when I was taking the class:

(* fill in the code wherever it says : failwith "to be written" *)
let removeDuplicates l =
  let rec helper (seen,rest) =
      match rest with
        [] -> seen
      | h::t ->
        let seen' = if List.mem h seen then seen else h::seen in
        let rest' = t in
   helper (seen',rest')
  in
      List.rev (helper ([],l));;

(* wwhile - f returns (result, boolean) while boolean wwhile(f, result)
o.w. result.

Pretty much we just keep repeating f on its own result until we get false,
which will then get our result*)

let f x = let xx = x*x*x in (xx, xx < 100);;

let rec wwhile(f, x) = match f(x) with
|(result, boolean) -> if boolean then wwhile(f, result)
                      else result;;

(* fixpoint - if f(x) = x and f(f(x)) = f(x) then f(x) otherwise fixpoint(f, f(x))*)
let rec fixpoint(f, x) =
if f(x) = x && f(f(x)) = f(x) then f(x)
else fixpoint(f, f(x));;