Deleting Elements From a List by Indexes in OCaml Example

Implement an OCaml function which, given a list l : 'a list of items and a list r : int list of indices i such that 0 <= i && i < length l, computes the result of deleting from l those values with indices in r. The list r is sorted in ascending order of value and does not contain duplicates.

Solution

To solve this problem, we proceed by recursively traversing the structure of both input lists l and r. We also need to keep track of the index i of the element in l we're currently visiting. This is accomplished with the delete_aux helper function.

In the case where r = [], we have exhausted the indices list of elements to delete from l, so we simply return l. If both lists l and r are non-empty, then we need to check whether the value of the topmost element d of r is the index of the topmost element x of l.

ocaml

let delete : 'a list -> int list -> 'a list =
  let rec delete_aux : int -> 'a list -> int list -> 'a list =
    fun i l r ->
      match (l, r) with
      | l, [] -> l
      | x :: xs, d :: ds ->
          if i > d then
            raise (Failure "delete")
          else if i = d then
            delete_aux (i + 1) xs ds
          else
            x :: delete_aux (i + 1) xs r
      | _ -> raise (Failure "delete")
  in
  fun l r -> delete_aux 0 l r

The recursive call to delete_aux in x :: delete_aux (i + 1) xs r is not a tail call. We can fix this using continuation-passing style:

ocaml

let delete : 'a list -> int list -> 'a list =
  let rec delete_aux : int -> 'a list -> int list -> ('a list -> 'b) -> 'b =
    fun i l r return ->
      match (l, r) with
      | l, [] -> return l
      | x :: xs, d :: ds ->
          if i > d then
            raise (Failure "delete")
          else if i = d then
            delete_aux (i + 1) xs ds return
          else
            delete_aux (i + 1) xs r (fun l' -> return (x :: l'))
      | _ -> raise (Failure "delete")
  in
  fun l r -> delete_aux 0 l r (fun l' -> l')