How does one pattern match two list exhaustively?

Learning
1

Why do I get this error:

# let rec f list1 list2 =
  match list1 with
  | [] -> match list2 with
    | [] -> true
    | l2::l2s -> false
  | l1::l1s -> match list2 with
    | [] -> true
    | l2::l2s -> false;;
Warning 11: this match case is unused.
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
_::_
val f : 'a list -> 'b list -> bool = <fun>

I am pattern matching both lists with all options but ocaml doesn’t agree?

2 
let rec f list1 list2 =
  match list1 with
  | [] -> match list2 with
    | [] -> true
    | l2::l2s -> false
  | l1::l1s -> match list2 with
    | [] -> true
    | l2::l2s -> false;;

is really

let rec f list1 list2 =
  match list1 with
  | [] -> (match list2 with
    | [] -> true
    | l2::l2s -> false
    | l1::l1s -> (match list2 with
      | [] -> true
      | l2::l2s -> false));;

That is, the trailing pattern matches are really part of the innnermost match expression. To get your intended meaning, you need to use parentheses:

let rec f list1 list2 =
  match list1 with
  | [] -> (match list2 with
    | [] -> true
    | l2::l2s -> false)
  | l1::l1s -> (match list2 with
    | [] -> true
    | l2::l2s -> false);;
3

You’ve hit OCaml’s ‘dangling else’ syntax issue. The parser thinks that the first nested match expression doesn’t end at l2::l2s -> false, because OCaml syntax is not whitespace-sensitive. The parse treats the next case branch, | l1::l1s -> match list2 with ..., as part of the nested match. That’s why you’re getting both ‘match case unused’ and ‘inexhaustive match’ warnings.

There are two ways to fix this. Specifically in this function, you can flatten the matches into a single one:

let rec f list1 list2 = match list1, list2 with
  | _, [] -> true
  | _ -> false

Note that this actually simplifies the branching logic. This is generally the case when flattening pattern matches. [EDIT: really your function just reduces to let f _list1 list2 = list2 = [].]

The second way is what @TheAspiringHacker posted, disambiguating the matches :slight_smile:

1 Like
4

Using the ocp-indent tool to format the code makes these issues pretty obvious in general. Using begin match ... with ... end is also more readable than parenthesis I think as well:

let rec f list1 list2 =
  match list1 with
  | [] ->
    begin match list2 with
    | [] -> true
    | l2::l2s -> false
    end
  | l1::l1s ->
    begin match list2 with
    | [] -> true
    | l2::l2s -> false)
    end;;

Or you can do it all to make it always unambiguous when reading:

let rec f list1 list2 =
  begin match list1 with
  | [] ->
    begin match list2 with
    | [] -> true
    | l2::l2s -> false
    end
  | l1::l1s ->
    begin match list2 with
    | [] -> true
    | l2::l2s -> false)
    end
  end;;