Longest prefix of an OCaml `string list` ending in a specific `string` value

Question

I am trying to work out whether there is a particularly neat or efficient way of truncating a string after the final occurrence of a specific element. For my purposes, it is a monomorphized string list and the string I am looking for the final (highest index) occurrence of is known at compile-time, since I am only using it in one case.

The motivation for this is to find the nearest ancestor in a Unix directory system of the CWD whose name in its parent is a particular folder name. I.E., if I wanted to find the nearest ancestor called bin and I was running the executable from a CWD of /home/anon/bin/projects/sample/src/bin/foo/, then I would want to get back /home/anon/bin/projects/sample/src/bin

The current implementation I am using is the following:

let reverse_prune : tgt:string -> string -> string =
  let rec drop_until x ys =
    match ys with
    | [] -> []
    | y :: _ when x = y -> ys
    | _ :: yt -> drop_until x yt
  in
  fun ~tgt path ->
    String.split_on_char '/' path
    |> List.rev |> drop_until tgt |> List.rev |> String.concat "/"

It isn't a particularly common or expensive code-path so there isn't actually a real need to optimize, but since I am still trying to learn practical OCaml techniques, I wanted to know if there was a cleaner way of doing this.

I also realize that it may technically be possible to avoid the string-splitting altogether and just operate on the raw CWD string without splitting it. I am, of course, welcome to such suggestions as well, but I am specifically curious if there is something that would replace the List.rev |> drop_until tgt |> List.rev snippet, rather than solve the overall problem in a different way.

Answer 1

I don't think this has anything to do with OCaml actually since I'd say the easiest way to do this is by using a regular expression:

let reverse_prune tgt path =
  let re =
    Str.regexp (Format.sprintf {|^[/a-zA-Z_-]*/%s\([/a-zA-Z_-]*\)$|} tgt)
  in
  Str.replace_first re {|\1|} path

let () =
  reverse_prune "bin" "/home/anon/bin/projects/sample/src/bin/foo/"
  |> Format.printf "%s@."

Is there a reason you want to reimplement regular expression searching in a string? If no, just use a solution like mine, I'd say.

---

If you want the part that comes before just change the group:

let reverse_prune tgt path =
  let re =
    Str.regexp (Format.sprintf {|^\([/a-zA-Z_-]*/\)%s[/a-zA-Z_-]*$|} tgt)
  in
  Str.replace_first re {|\1|} path