ocaml tail-recursive functions

Question

I'm running Ocaml using utop, when I run the below function on a very long input:

let string_to_list str =
  let rec loop i limit =
    if i = limit then []
    else (String.get str i) :: (loop (i + 1) limit)
  in
  loop 0 (String.length str);;

it returns the following error:

Stack overflow during evaluation (looping recursion?).

What would be the tail-recursive version of the function?

Answer 1

As Jeffrey Scofield noted, your function is not tail-recursive. Converting it to use tail recursion (in an idiomatic way for OCaml) will involve introducing an accumulator argument to your loop function.

let string_to_list str =
  let rec loop i limit acc =
    if i = limit then acc
    else 
      let ch = String.get str i in
      loop (i + 1) limit (ch :: acc)
  in
  loop 0 (String.length str) [] |> List.rev

This way all of the necessary information for the evaluation of the function is contained in one stack frame, and the compiler can optimize away all of the previous stack frames.

To provide a bit of a visual in pure text, we look at the non-tail-recursive version of the function, called on "hello".

+-----------------------+
| string_to_list "hello"|->
+-----------------------+ |
^      v------------------+
| +--------+
<-|loop 0 5|->
  +--------+ |
  ^      v---+
  | +--------+
  <-|loop 1 5|->
    +--------+ |
    ^      v---+
    | +--------+
    <-|loop 2 5|->
      +--------+ |
      ^      v---+
      | +--------+
      <-|loop 3 5|->
        +--------+ |
        ^      v---+
        | +--------+
        <-|loop 4 5|->
          +--------+ |
          ^      v---+
          | +--------+
          <-|loop 5 5|
            +--------+

As we go through, each call needs the information in the previous call. But, if loop passes all of the necessary information (that accumulated result list) through arguments, then no iteration of loop needs any of the previous calls in order to fully evaluate.

     +-----------------------+
     | string_to_list "hello"|
     +-----------------------+
                |
                v
+----------------------------------+
|loop 0 5 []                       |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 1 5 ['h']                    |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 2 5 ['e'; 'h']               |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 3 5 ['l'; 'e'; 'h']          |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 4 5 ['l'; 'l'; 'e'; 'h']     |
+----------------------------------+
                |
                v
+----------------------------------+
|loop 5 5 ['o'; 'l'; 'l'; 'e'; 'h']|
+----------------------------------+
                |
                v
+----------------------------------+
|List.rev ['o'; 'l'; 'l'; 'e'; 'h']|
+----------------------------------+
                |
                v
+----------------------------------+
|['h'; 'e'; 'l'; 'l'; 'o']         |
+----------------------------------+

As of OCaml 4.14 (released March 2022) there is a simpler method to convert your function to be tail-recursive. Leverage the Tail Modulo Constructor program transformation.

let[@tail_mod_cons] string_to_list str =
  let rec loop i limit =
    if i = limit then []
    else String.get str i :: loop (i + 1) limit
  in
  loop 0 (String.length str)

Answer 2

The loop function is not tail recursive. You can see that it applies an operation (::) to the return value of the recursive call. This prevents it from being tail recursive. I.e., the recursive call is not at the tail.

Update

Here is a tail recursive function to change a string into a list of characters. I hope I'm not doing your homework for you.

let string_to_list str =
    let rec loop accum i =
        if i >= String.length str then
            List.rev accum
        else
            loop (String.get str i :: accum) (i + 1)
    in
    loop [] 0

As I said in the comment, this is something you absolutelly have to be familiar with to do functional programming. But it's not difficult once you see the trick.

Fairly often it's necessary to accumulate a list in reverse order, then reverse it at the end. Adding to the end of a list is too slow (it tends to give quadratic complexity).

Update 2

Here is an even more efficient tail-recursive version, which doesn't require the List.rev and String.length calls:

let string_to_list str =
    let rec loop accum i =
        if i < 0 then
            accum
        else
            loop (str.[i] :: accum) (i - 1)
    in
    loop [] (String.length str - 1)

(In fact this is a very good way to get the list of characters, but it doesn't teach the all-important technique of accumulating results backward and reversing at the end. :-)