Unbound value length on mergesort algorithm

Question

I have the following task:

Complete the algorithm

let rec mergeSort (a, i, b, j, c, k) =
 if i = (length a) && j = (length b) || k = (length c) then 
   ()
 else if i = (length a) then 
   (c.(k) <- b.(j); 
    mergeSort (a, i+1, b, j+1, c, k+1))
 else if j = (length b) then 
   (c.(k) <- a.(i); 
    mergeSort (a, i+1, b, j, c, k+1))
 else if a.(i) < b.(j) then 
   ...
 else 
   ...

where I suppose the answer would be:

let rec mergeSort (a, i, b, j, c, k) =
  if i = (length a) && j = (length b) || k = (length c) then 
    ()
  else if i = (length a) then 
    (c.(k) <- b.(j); 
     mergeSort (a, i+1, b, j+1, c, k+1))
  else if j = (length b) then 
    (c.(k) <- a.(i); 
     mergeSort (a, i+1, b, j, c, k+1))
  else if a.(i) < b.(j) then 
    (c.(k) <- a.(i); 
     mergeSort (a, i+1, b, j, c, k+1))
  else 
    (c.(k) <- b.(j); 
     mergeSort (a, i, b, j+1, c, k+1))

So that it gives the in- and output as follows:

let a = [|1; 4; 7; 9|];;
let b = [|2; 3; 4; 5; 6|];;
let c = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]

mergesort(a, 0, b, 0, c, 0) ->
[|1; 2; 3; 4; 4; 5; 6; 7; 9; 0; 0; 0|]

However, I am getting an unbound value length error on the first line. I thought length was a part of the ocaml-library and the part of the error is the actual task, not the answer. How would I change this so that the function compiles?

Answer 1

This is so much simpler if you do it with lists:

# let mergeSort a b =
    let rec mergeSort' ?(acc=[]) = function
      | ([], []) -> List.rev acc
      | (a, []) -> List.rev_append acc a 
      | ([], b) -> List.rev_append acc b 
      | ((x::xs as a), (y::ys as b)) ->
        if x < y
        then mergeSort' ~acc:(x::acc) (xs, b)
        else mergeSort' ~acc:(y::acc) (a, ys)
    in
    Array.of_list (mergeSort' (Array.to_list a, Array.to_list b));;

val mergeSort : 'a array -> 'a array -> 'a array = <fun>

# let a = [|1; 4; 7; 9|]
  let b = [|2; 3; 4; 5; 6|]
  let c = mergeSort a b;;

val a : int array = [|1; 4; 7; 9|]
val b : int array = [|2; 3; 4; 5; 6|]
val c : int array = [|1; 2; 3; 4; 4; 5; 6; 7; 9|]

Answer 2

As per comments, the name length has to come from somewhere. Given that you're working with arrays, you almost certainly want Array.length. You could prepend your code with open Array but that's perhaps an overreaction.

You could also bind the name length to Array.length with let length = Array.length.

You could modify your code to explicitly specify which length you want:

let rec mergeSort (a, i, b, j, c, k) =
  if i = (Array.length a) && j = (Array.length b) || k = (Array.length c) then 
    ()
  else if i = (Array.length a) then 
    (c.(k) <- b.(j); 
     mergeSort (a, i+1, b, j+1, c, k+1))
  else if j = (Array.length b) then 
    (c.(k) <- a.(i); 
     mergeSort (a, i+1, b, j, c, k+1))
  else if a.(i) < b.(j) then 
    (c.(k) <- a.(i); 
     mergeSort (a, i+1, b, j, c, k+1))
  else 
    (c.(k) <- b.(j); 
     mergeSort (a, i, b, j+1, c, k+1))

But I might be more inclined to bind names for the length of each array, and only locally open Array.

let rec mergeSort (a, i, b, j, c, k) =
  let a_len, b_len, c_len = Array.(length a, length b, length c) in
  if i = a_len && j = b_len || k = c_len then 
    ()
  else if i = a_len then 
    (c.(k) <- b.(j); 
     mergeSort (a, i+1, b, j+1, c, k+1))
  else if j = b_len then 
    (c.(k) <- a.(i); 
     mergeSort (a, i+1, b, j, c, k+1))
  else if a.(i) < b.(j) then 
    (c.(k) <- a.(i); 
     mergeSort (a, i+1, b, j, c, k+1))
  else 
    (c.(k) <- b.(j); 
     mergeSort (a, i, b, j+1, c, k+1))

---

As an aside:

let c = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]

Could be:

let c = Array.init 10 (fun _ -> 0)

And it doesn't feel very idiomatic to have your function mutate that array as an existing value and return unit. It would feel more idiomatic to have mergeSort return a merged, sorted array. We can actually use your existing code as a baseline local function. We'll rename it to mergeSort'.

let mergeSort (a, i, b, j) =
  let c = Array.(init (length a + length b) (fun _ -> 0)) in
  let rec mergeSort' (a, i, b, j, c, k) =
    let a_len, b_len, c_len = Array.(length a, length b, length c) in
    if i = a_len && j = b_len || k = c_len then 
      ()
    else if i = a_len then 
      (c.(k) <- b.(j); 
       mergeSort' (a, i+1, b, j+1, c, k+1))
    else if j = b_len then 
      (c.(k) <- a.(i); 
       mergeSort' (a, i+1, b, j, c, k+1))
    else if a.(i) < b.(j) then 
      (c.(k) <- a.(i); 
       mergeSort' (a, i+1, b, j, c, k+1))
    else 
      (c.(k) <- b.(j); 
       mergeSort' (a, i, b, j+1, c, k+1))
  in
  mergeSort' (a, i, b, j, c, 0);
  c

Now:

utop # mergeSort(a, 0, b, 0);;
- : int array = [|1; 2; 3; 4; 4; 5; 6; 7; 9|]

Heck, we can even make it simpler than that by hiding the i and j.

let a = [|1; 4; 7; 9|]
let b = [|2; 3; 4; 5; 6|]
let c = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]


let mergeSort (a, b) =
  let c = Array.(init (length a + length b) (fun _ -> 0)) in
  let rec mergeSort' (a, i, b, j, c, k) =
    let a_len, b_len, c_len = Array.(length a, length b, length c) in
    if i = a_len && j = b_len || k = c_len then 
      ()
    else if i = a_len then 
      (c.(k) <- b.(j); 
       mergeSort' (a, i+1, b, j+1, c, k+1))
    else if j = b_len then 
      (c.(k) <- a.(i); 
       mergeSort' (a, i+1, b, j, c, k+1))
    else if a.(i) < b.(j) then 
      (c.(k) <- a.(i); 
       mergeSort' (a, i+1, b, j, c, k+1))
    else 
      (c.(k) <- b.(j); 
       mergeSort' (a, i, b, j+1, c, k+1))
  in
  mergeSort' (a, 0, b, 0, c, 0);
  c

And use it like so:

utop # mergeSort (a, b);;
- : int array = [|1; 2; 3; 4; 4; 5; 6; 7; 9|]

---

Lets optimize that a bit more and curry the arguments:

let a = [|1; 4; 7; 9|]
let b = [|2; 3; 4; 5; 6|]

let mergeSort a b =
  let (a_len, b_len) = Array.(length a, length b) in
  let c_len = a_len + b_len in
  let c = Array.init c_len (fun _ -> 0) in
  let rec append x i k =
    if k = c_len
    then ()
    else (k -> c.(k) <- x.(i); append x (i + 1) (k + 1))
  in
  let rec mergeSort' i j =
    if i = a_len
    then append b j (i + j)
    else if j = b_len
    then append a i (i + j)
    else
      let (i', j') =
        if a.(i) < b.(j)
        then (c.(i + j) <- a.(i); (i+1, j))
        else (c.(i + j) <- b.(j); (i, j+1))
      in
        mergesort' i' j'
  in
  mergeSort' 0 0;
  c