Subtract ordered lists

Question

Newbie OCaml review:

Given lists xs and ys that are both ordered in the same way (e.g. monotonically ordered integers), I want to return a list containing all elements of xs not in ys, with order preserved. I can assume that the elements in ys are a (perhaps improper) subset of xs.

The key is that I have to walk two lists, but they are different lengths and I don't necessarily move through them at the same rate, so I can't use one of the fold2 functions, as far as I can see.

let rec subtract_list xs ys =
  match xs with 
  | [] -> []
  | x::more_xs -> match ys with
                  | [] -> xs
                  | y::more_ys -> 
                      if x = y 
                      then subtract_list more_xs more_ys
                      else x::(subtract_list more_xs ys)

This is the best method I came up with, but I wonder if there's some better strategy that doesn't involve embedding a match inside a match or that's simpler or more idiomatic in some other way. This version isn't tail recursive, but that's OK. Comments on indentation or other formatting issues are welcome too.

Answer 1

You can merge all the testing into one match expression:

let rec subtract_list xs ys =
  match xs, ys with 
  | [], _ -> []
  | _, [] -> xs
  | x :: xs', y :: ys' when x = y ->
      subtract_list xs' ys'
  | x :: xs', _ ->
      x :: (subtract_list xs' ys)

This also gets rid of the if expression.