Ocaml Type error in merge sort program

Question

I am trying to write a simple merge sort code in OCaml, which also removed duplicates.

The code that I have written is:

let mergesort l r = 
match l with 
    [] -> []
|   [x]-> [x]
| x::xs ->  let rec split l3 =
                match l3 with
                    []   -> ([], [])
                |   [h]  -> ([h], [])
                |   h1::h2::t -> let (left, right) = split t in
                                    (h1::left, h2::right) in
            let rec merge l1 l2 r = 
                match (l1, l2) with
                    ([], []) -> []
                |   ([a], []) -> [a]
                |   ([], [a]) -> [a]
                |   (a1::t1, a2::t2) -> if a1 = a2 then (a1::(merge (t1) t2))
                                        else if r(a1, a2) then (a2::(merge t1 (a2::t2)))
                                        else (a1::(merge (a1::t1) t2)) in
            let (l3, l4) = split l in
                merge (mergesort l3 r) (mergesort l3 r) r;;

I am getting following type error in my merge function:

|(a1::t1, a2::t2) -> if a1 = a2 then

(a1::(merge (t1) t2))

Error: This expression has type 'a -> 'b list but an expression was expected of type 'b list

I have no idea why I am getting this error, as all the branches in merge are returning the list of same type.

Can anyone help here?

Thank you very much, I feel stupid now that I missed such a trivial thing.. — Anurag Aggarwal
I think you have a bug in the merge case when a1 != a2 for both the < and > case. It should be (a2::(merge t1 (a1::t2))) and (a1::(merge (a2::t1) t2)). You can also write this better using | (a1::t1 as left, a2::t2 as right) -> ... and using left/reight later. This saves the compiler form allocating a new list for the recursive call. — Goswin von Brederlow

Unknown Unknown · Accepted Answer · 2017-08-31T12:05:34

Several issues in your code:

As mentioned in the comments, the merge function has 3 parameters, but you call it with 2,
the mergesort function is called recursively, yet it is not declared recursive.

Here's an existing implementation.

Ocaml Type error in merge sort program

1 Answers