Q:

OCaml merge sort errors?

I'm currently learning OCaml, and it's giving me some problems. I'm trying to implement a merge_sort function, but it keeps giving me an error on the 5th line of the given code. I'm just utterly confused as to why its giving me the error, if anyone could enlighten me, I'd greatly appreciate it. I'm not even really sure if I'm setting up the pattern matching (match statements) correctly, so if you could take look, that'd be really helpful.
let rec merge_sorted (l1:int list) (l2:int list) : int list =
let end_list = [] in
begin match l1, l2 with 
    | [], [] -> end_list
    | h1::t1, h2::t2 -> if h1 < h2 then merge_sorted t1 t2 (h1 :: end_list) else merge_sorted t1 t2 h2::end_list, h1::end_list
end

The error I'm getting is:

Error: This function is applied to too many arguments,
  maybe you forgot a `;'
  merge_sorted: int list -> int list -> int list

On the part where it says "if h1 < h2 then merge_sorted t1 t2..."
I was also wondering if there are any places to learn OCaml syntax? I've been trying to use Jason Hickey's book, but there are things that it doesn't go very in depth in (such as this multiple/parallel pattern matching). I've only mainly coded in Java, so coding in OCaml has been a bit of a frustrating new experience for me.

A:

You've declared merge_sorted as a function of type int list -> int list -> int list, or a function that takes two int lists as parameters and returns another int list.
The problem you're encountering is because you're invoking merge_sorted with three int list arguments:
h1::t1, h2::t2 -> if h1 < h2 then merge_sorted t1 t2 (h1 :: end_list) else merge_sorted t1 t2 h2::end_list, h1::end_list

specifically, merge_sorted t1 t2 (h1 :: end_list).  You've made no provision for the result list in your function definition.
You'll want to modify your function definition, maybe like so:
let rec merge_sorted l1 l2 results =
  (* code code code *)

Regarding your second question, a decent set of tutorials can be found here.
EDIT
In response to your comment-
First, the :: operator serves two purposes.  One, it creates a new list with a new head and an existing tail - 1 :: [2] yields [1; 2].  Second, it decomposes existing lists during pattern matches - match [1; 2] with x :: xs will bind x to 1 and y to [2].
That point being addressed, there are a few things in your approach that work fine in Java but will not work at all in OCaml.  First, you're re-declaring end_list as an empty list in each recursive invocation of your function. 
Second, because you have your list concatenation on the same line as your recursive call to merge_sorted, the compiler will (has no choice but to) think that you're specifying a third function call.  What you probably meant is:
h1::t1, h2::t2 -> if h1 < h2 then
                      merge_sorted t1 t2
                      h1 :: end_list
                  else
                      merge_sorted t1 t2
                      h2 :: end_list
                      h1 :: end_list

BUT! This isn't your solution, read on.
Third and far more importantly, OCaml don't work this way.  By default, OCaml lists (and all variables, actually) are immutable - that is, once you've bound a value to one, you can't change it.  When you say (h1 :: end_list), you're not changing end-list; what you're actually doing is creating a new list that has h1 as its head and end_list as its tail.  Because you have this all on the same line, the compiler thinks that you're doing the equivalent of merge_sorted(t1, t2, new List(h1, end_list)) in Java-land where you've defined merge_sorted(List t1, List t2).
Because you can't modify your list in-place, functional languages of this stripe have different idioms for list processing.  In this case, most functional programmers would have defined their function to take an additional accumulator argument.  For example:
let rec map f data acc =
    match data with
    | []      -> List.rev acc
    | x :: xs -> map f xs ((f x) :: acc);;

map (fun x -> x + 1) [1; 2; 3;] [];;  (* yields [2; 3; 4] *)

This is the canonical map function, which takes a list and a function, applies each item in the list to that function, and returns a new list containing the results.  As you can see, the results of applying each item in data to f are stored in acc and the result is passed to the next call, only to be returned when data is empty.  In this way we can achieve a series of list modifications without needing to mutate a variable.
If you don't like the extra argument in your function signature, you can hide it inside of a nested function like so:
let map f data =
    let rec loop d acc =
        match d with
        | []      -> List.rev acc
        | x :: xs -> loop xs ((f x) :: acc)
    in
        loop data []

I hope this makes some sense to you - transitioning from imperative to functional idioms can be truly mind-bending, and immutability can seem a cruel and arbitrary limitation to those new to it - I promise that the benefits and the beauty of functional programming will manifest themselves to you if you stick with it!

A:

Ben's answer is good, but I hope you won't mind a couple of extra comments.  First, your pattern matching isn't exhaustive.  It doesn't cover the case where one of the lists is empty but the other isn't.  Second, if you're just learning OCaml I'd start by writing the merge in a non-tail-recursive style.  That is, I wouldn't pass an accumulated result as a parameter.  You would end up with something roughly like this:
let rec merge_sorted l1 l2 =
    match l1, l2 with
    | (* Either one is empty *) -> (* answer is pretty obvious *)
    | h1::t1, h2::t2 ->
          if h1 < h2 then h1 :: (* Merge the rest *)
          else h2 :: (* Merge the rest *)

(I hope this doesn't give too much away and take the fun out of it.)
(Added)
In the block of code: "then h1 :: (* Merge the rest *)", does that :: allow you to call other functions?
Well, if you say (xxx) :: (yyy) you can have pretty much any function calls you want in the xxx and yyy parts (if they make sense type-wise).  This is in fact the essence of functional programming: it's possible to do everything with function calls.  Believe it or not, after you get used to it it's kind of hard to go back to programming other ways.
I thought that was an operator to append to front of the list?
Yes, that's what (::) is.  You want to return a list built up from the elements of your two input lists, so you'd expect to build up your list with the (::) operator.  It might be worth noting that (::) is just a function.
Also, in terms of matching multiple lists, when there is a comma in between one of the pattern matches, (such as "h1::t1, h2::t2 -> ", does that mean "both still have items left", or "either still have items left."
It means that both still have items left.
Also, why does h1::t1 represent a non empty list? Is that just a special case? I thought the :: was to append to the front of the list?
As Ben explains, the (::) is used as an operator and as a pattern component.  When you use it in a pattern it means you have a list with a head and a tail.  The tail can be empty, but the head has to be something.  So the pattern h1::t1 only matches a list that's at least 1 long.  The h1 matches the head of the list (an int in your example), and the t1 matches the tail of the list (another list that's 1 element shorter).
This isn't really a special case.  When you define your own types in OCaml, you get these same two things with the same name: a constructor (used to build up values of the type) and a destructor (used to do pattern matching).  The use of an operator (::) for the list constructor and destructor is a little special, though.  Lists do generally get a little bit of special treatment in OCaml.  But aside from the special syntax, it's just a normal type.

