Working with option and list in OCaml

Question

I am having problems with recursive functions that takes a list and return an option list. For example a function all_except_one:

val all_except_one : 'a -> 'a list -> 'a list option = <fun> 

Where the first occurrence of 'a is removed from the list. If the 'a is not in the list you should return None.

without the option I have code that looks like this:

let same_string s1 s2 =
  s1 = s2

let rec all_except_one str str_l =
  match str_l with
  | [] -> []
  | hd::tl -> if same_string hd str
              then tl
              else hd::(all_except_one str tl)

but whenever I try and add the option, it gets in the way when doing my recursive call.

Answer 1

An alternative to matching on the result of a recursive call is to write a helper function with an accumulator argument:

let remove_first elt list =
  let rec loop acc = function
    | [] -> None
    | x::xs ->
        if x = elt then Some (List.rev_append acc xs)
        else loop (x::acc) xs in
  loop [] list

A minor advantage of doing it this way is that the loop becomes tail recursive.

Answer 2

An option list looks like [ None; Some "abc"; None ]. I think you want a list option, which looks like Some ["a"; "b"; "c"] or None.

As for your main question, you have to handle the recursive call by cases. If your recursive call returns None you would return None also. If the recursive call returns a Some list, you would return Some (longer list). You also need to rethink the base case (when the list is empty), I would say.

Answer 3

To be honest, I don't understand why you need same_string function, when you can use = instead.

I suggest to implement the function you want like this:

let rec all_except_one str str_l = match str_l with
  | [] -> None
  | hd :: tl -> if hd = str then Some tl else 
      match all_except_one str tl with
      | None -> None
      | Some x -> Some (hd :: x)

What caused a problem in your case?