# Subtract ordered lists

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.

• this is a common problem i've run into using .net applications. i'd recommend googling 'subtract one list from another .net c#' and to then copy some of the implementations for your own purposes? – BKSpurgeon May 3 '17 at 14:45
• Thanks @BKSpurgeon. I assume you meant F#. That's a good idea--to search for F# solutions--and maybe Haskell or even SML solutions--when looking for OCaml solutions. – Mars May 4 '17 at 2:58

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.

• One can understand your version more quickly. Is that a common idiom--using the tick/quote/prime that way? – Mars May 4 '17 at 3:14
• Yes. It looks more "math-y". :) OCaml supports multiple ticks, so you could have x''. But then it starts to get confusing. – RichN May 4 '17 at 17:03
• Right--OK. Makes sense. – Mars May 4 '17 at 23:47