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.

  • \$\begingroup\$ 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? \$\endgroup\$ – BKSpurgeon May 3 '17 at 14:45
  • \$\begingroup\$ 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. \$\endgroup\$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.