Does this function have a name?

Learning
1

Well I hope you’re intrigued now :slight_smile:

I’m reading “OCaml from the very beginning”, I’m on the last chapter and I should reverse the contents of a file, to another file.

This is my entry point:

let rev_file (Valid_path p) =
  let ic = open_in p in
  let oc = open_out (p ^ ".rev") in
  do_rev ic oc
  ; close_in ic
  ; close_out oc
;;

I’m only concentrating on do_rev from now on.

That was my iteration n°1, imperative style:

let do_rev ic oc =
  let out = ref [] in
  try
    while true do
      let line = input_line ic in
      out := line :: !out
    done
  with
  | End_of_file ->
      let output = String.concat "\n" !out ^ "\n" in
      output_string oc output
;;

On iteration n°2, I wondered if I could make the code cleaner by making it more functional:

let do_rev ic oc =
  let rec build_lines acc =
    try build_lines (input_line ic :: acc) with
    | End_of_file -> acc
  in

  let rec put_lines lst =
    match lst with
    | [] -> ()
    | h :: t ->
        output_string oc (h ^ "\n")
        ; put_lines t
  in

  build_lines [] |> put_lines
;;

At iteration n°3, I saw a pattern and could collapse put_lines into a terser construct:

let do_rev ic oc =
  let rec build_lines acc =
    try build_lines (input_line ic :: acc) with
    | End_of_file -> acc
  in

  let output_line line = output_string oc (line ^ "\n") in
  let put_lines = List.iter output_line in

  build_lines [] |> put_lines
;;

For the final version, I’d like to remove the exception that’s used as a control-flow mechanism. I wondered what I could do with build_lines if I had a different API to begin with:

let input_line' ic =
  try Some (input_line ic) with
  | End_of_file -> None
;;

This allows me to “collapse” new_lines in a similar fashion:

let what_is_it next =
  let rec loop next acc =
    match next () with
    | Some x -> loop next (x :: acc)
    | None -> acc
  in
  loop next []
;;

let do_rev ic oc =
  let new_lines = what_is_it (fun () -> input_line' ic) in

  let output_line line = output_string oc (line ^ "\n") in
  let put_lines = List.iter output_line in

  new_lines |> put_lines
;;

However, I’m wondering what the function what_is_it could be called? It’s similar, but different from all the functions I already know about.

Is there a commonly used function that does the same job? Even in an alternative standard lib? I wouldn’t want to re-invent the wheel.

2

One way of expressing it:

Seq.fold_left (fun accu x -> x :: accu) [] (Seq.of_dispenser next)

Also, you didn’t ask for it, but here’s a simpler version of do_rev:

let do_rev ic oc =
  In_channel.input_all ic
  |> String.split_on_char '\n'
  |> List.rev
  |> String.concat "\n"
  |> Out_channel.output_string oc

Cheers,
Nicolas

PS: ;; are not needed in files nowadays, they are only used when entering input interactively in the toplevel.

2 Likes
3

Interesting! I forgot to factor out List.cons. In that case the function becomes

let what_is_it f next =
  let rec loop next acc =
    match next () with
    | None -> acc
    | Some x -> loop next @@ f x acc
  in
  loop next []

And if I give back control over the accumulator, hand over an init, I can see I was indeed re-implenting fold_left minus a few features! (and minus the dispenser bit obviously)

let my_fold_left f init next =
  let rec loop next acc =
    match next () with
    | None -> acc
    | Some x -> loop next @@ f acc x
  in
  loop next init

And the calling code for comparaison:

let do_rev ic oc =
  let next () = input_line_opt ic in
  let new_lines =
    Seq.fold_left (fun acc x -> x :: acc) [] (Seq.of_dispenser next)
  in
  let new_lines = my_fold_left (fun acc x -> x :: acc) [] next in
...

Thanks for putting me on the right track @nojb

Thanks I appreciate it. Normally that’s what I’d do, read the whole file in memory and do the required transformations then.

I was trying to keep memory efficient in mind here (just as an exercise of course). I’m doing okay on the reading side, but not so much on the writing side. What I’d really want is to write lines in reverse order, but I don’t think that’s doable OS-wise.

Yeah I’ll remove them next time to avoid the confusion :slight_smile:

I added a rule to ocaml-format to add them automatically because:

  1. I read that’ll give me potentially better error messages, and also (and mainly)
  2. because it gives me a strong visual cue that the function is finished (I like that). Plus it gives a bit more breathing room vertically. Otherwise, the functions become pretty bunched up, I find the default formatting not very enjoyable.
4

That looks like to_rev_list if we think of next as modelling an ‘iterator’ structure. It traverses the iterable and collects the results in reverse order into a list.

EDIT: although in your second example you have added another concern which is mapping over the result list, so it’s more like to_rev_list_map.

5

Thanks, it looks like a really cool library :slight_smile:

1 Like
6

to me it looks like a variant of unfoldr which uses side-effects instead of an explicit state (b in the linked example)

7

unfoldr does indeed look very similar to the function in its first iteration, thanks!!

-- pretend we are reading 10 lines
Prelude> import Data.List
Prelude Data.List> unfoldr (\next -> if next > 10 then Nothing else Just (next, next + 1)) 1
[1,2,3,4,5,6,7,8,9,10]
8

I saw this thread and opened a repl then started sketching this with Seq.unfold followed by Seq.fold_left. I didn’t like how it looked and forgot to post on the thread haha, but yes this could be encoded as unfold |> fold_left |> iter

From my history.ml:

let (let@) = (@@)
let output_rev file =
  let@ i = In_channel.with_open_bin file in
  let@ o = Out_channel.with_open_bin (file ^ ".rev") in
  Seq.unfold (fun c -> Option.map (fun l -> l, c) (In_channel.input_line c)) i
  |> Seq.fold_left (fun s l -> Seq.cons (l ^ "\n") s) Seq.empty
  |> Seq.iter (Out_channel.output_string o)