title: General merge of two lists
body: <p>I started learning OCaml and I have a problem with a simple function. This is from <code>Developing Application with Objective OCaml</code></p>
  
  <blockquote>
    <p>Write a general function merge which takes as argument a comparison function
    and two lists sorted in this order and returns the list merged in the same order.
    The comparison function will be of type 'a -> 'a -> bool.</p>
  </blockquote>
  
  <p>Here is what I got so far</p>
  
  <pre><code>(* func : 'a -&gt; 'a -&gt; bool) *)
  let rec merge2 listA listB func = match listA, listB with
      | list, [] | [], list -&gt; list
      | (headA :: tailA), (headB :: tailB) -&gt; 
          if (func headA headB) then headA :: merge2 tailA listB
          else merge2 :: merge listA tailB
  </code></pre>
  
  <p>and here is a error message</p>
  
  <pre><code>Characters 169-187:
          if (func headA headB) then headA :: merge2 tailA listB
                                          ^^^^^^^^^^^^^^^^^^
  Error: This expression has type ('a -&gt; 'a -&gt; bool) -&gt; 'a list
         but an expression was expected of type 'a list
  </code></pre>
  
  <p>I don't understand wht I get this error message. Obviously a dummy function</p>
  
  <p><code>let foo a b f = if (f a b ) then true else false</code></p>
  
  <p>work just fine. I also tried to state types explicitly.</p>
  
  <p>EDIT:</p>
  
  <p>Correct code</p>
  
  <pre><code>let rec merge2 listA listB func = match listA, listB with
      | list, [] | [], list -&gt; list
      | (headA :: tailA), (headB :: tailB) -&gt; 
          if (func headA headB) then headA :: merge2 tailA listB func
          else headB :: merge2 listA tailB func
  </code></pre>