1. Write a function merge_i which takes as input two integer lists sorted in
increasing order and returns a new sorted list containing the elements of
the first two.
This is one of the exercises in chapter 2 of Developing Applications with Objective Caml. Took me a little while since I don't use a lot of recursion in my day job. On my first pass, I nailed the base case but the recursive case I messed up. I discovered this handy little trick when using the interpreter.
Objective Caml version 3.08.3
# use "test.ml"
val merge_i : int list -> int list -> int list = <fun>
# #trace merge_i;;
merge_i is now traced.
# merge_i [1;2] [3;4];;
merge_i <-- [1; 2]
merge_i --> <fun>
merge_i* <-- [3; 4]
merge_i <-- [2]
merge_i --> <fun>
merge_i* <-- [3; 4]
merge_i <-- []
merge_i --> <fun>
merge_i* <-- [3; 4]
merge_i* --> [3; 4]
merge_i* --> [2; 3; 4]
merge_i* --> [1; 2; 3; 4]
- : int list = [1; 2; 3; 4]
#
Aha! Initiallly, I was only passing the tail of the two lists on the recursive call. I needed to modify it to pass the tail of the list which I had used and pass the other list untouched. That trace feature in the
interpreter sure is handy (I believe lisp and ruby also have this in their REPL).
The solution came to this:
let rec merge_i (x:int list) (y:int list) =
if x = [] && y = [] then []
else if x = [] then y
else if y = [] then x
else let a = List.hd x
and b = List.hd y
in if a > b
then b :: merge_i x (List.tl y)
else a :: merge_i (List.tl x) y ;;
(* in the last else, I had done (if a > b then b else a) :: merge_i (List.tl x) (List.tl y) initially *)
(* the if x = [] && y = [] then [] is probably superfluous but it's late and I'm going to sleep *)
P.S (* *) is an OCaml comment. Very /* */ if you ask me.
Recent Comments