ocaml function asks me to return unit instead of 'a list

Question

I have recently started coding in ocaml and this programming language is hell sensible when it comes to defining what I want a function to return. I want to write a function that uses 2 lists as parameters (supposed to be in ascending order and with elements of type int) and returns a list that contains all the elements of the first 2 lists, also in ascending order.

Here is what I managed to get so far:

let inter l1 l2 =
let rec aux l1 l2 l3=
if List.hd l1<List.hd l2 then aux (List.tl l1) l2 (List.hd l1 :: l3)
else (if List.hd l1>List.hd l2 then aux l1 (List.tl l2) (List.hd l2::l3)
      else (if l1 = [] then List.fold_left (fun x y -> y::x) l3 l2
            else if l2=[] then List.fold_left (fun x y -> y::x) l3 l1
     ))
  in List.rev (aux l1 l2 []);;

But when I compile it, it returns me this error message:

Error: This expression has type 'a list
       but an expression was expected of type unit

When I call the function, it works just fine, but it works just as expected, but what bothers me is the error message. Any idea why it appears?

PS: I use Emacs - Tuareg Mode as a text editor and compiler.

ivg ivg · Accepted Answer · 2016-10-14T19:00:15

Th if/else syntactic construct is an expression. The type of the whole expression is defined by the type of expressions returned by the branches. Obviously, they must be of the same type. If you didn't specify the else branch, then it is assumed that the omitted else branch is an expression of type unit, basically if c then e is a shorthand for if c then e else ().

The expression:

 if l2=[] then List.fold_left (fun x y -> y::x) l3 l1

is actually a shorthand for:

 if l2=[] then List.fold_left (fun x y -> y::x) l3 l1 else ()

So OCaml tries to unify List.fold_left (fun x y -> y::x) l3 l1 with (). It they definitely have different types. If you add an explicit else branch, then everything will typecheck (not sure about the correctness):

let inter l1 l2 =
let rec aux l1 l2 l3=
if List.hd l1<List.hd l2 then aux (List.tl l1) l2 (List.hd l1 :: l3)
else (if List.hd l1>List.hd l2 then aux l1 (List.tl l2) (List.hd l2::l3)
      else (if l1 = [] then List.fold_left (fun x y -> y::x) l3 l2
            else if l2=[] then List.fold_left (fun x y -> y::x) l3 l1 else []
     ))
  in List.rev (aux l1 l2 []);;

Your frustration may be due to being comfortable with C-like programming languages. OCaml can be frustrating when trying to force a C programming style in it. Pattern matching is a very powerful feature of OCaml and would simplify your solution:

let rec inter l1 l2 =
  match l1, l2 with
  | [], _ -> l2
  | _, [] -> l1
  | (h1 :: t1), (h2 :: t2) ->
    if h1 <= h2 then
      h1 :: inter t1 l2
    else
      h2 :: inter l1 t2

The first pattern says "if l1 is the null list, then return l2". The second pattern says "if l2 is an empty list, return l1". When pattern three is tested, we know both lists are not empty so we can pattern match on their contents, so there's no need to use list.hd, et al. We use an if-statement to determine which head becomes the new head and which tails we use when recursing.

As you get more comfortable with OCaml idioms, these solutions will come to you naturally.

ocaml function asks me to return unit instead of 'a list

1 Answers