Stack overflow when appending to a mutable list

Question

I'm trying to write a recursive function that works with a record type with a mutable list field.

This function should modify the mutable field during recursive calls, adding new values to the list. Everything worked fine, but when the amount of input data started to increase, I started getting stack overflow errors.

Here is a minimal example that demonstrates my problem:

type ty = { mutable ll : int list; }

let build_list i n =
  let rec aux acc i =
    if i <= n then
      aux (i::acc) (i+1)
    else (List.rev acc)
  in
  aux [] i

let rec mod_rec (acc: int) (a: ty) : (int) =
    a.ll <- a.ll @ (build_list 0 4000);
    let acc = if acc > 0 then mod_rec (acc - 1) a else 0 in
    acc

let aty = { ll = [] } in
mod_rec 1000 aty

This leads to the following error:

Stack overflow during evaluation (looping recursion?).
Raised by primitive operation at file "stdlib.ml", line 296, characters 22-31
Called from file "stdlib.ml", line 296, characters 22-31

And I got the same error when using tail recursive functions.

I don't quite understand what is going here. What values does the compiler allocates on the stack? Why it doesn't use a heap to store list elements?

What are the best practices to solve this problem? Should I choice other data structures or use immutable lists with destructive updates?

Thanks for any advices.

Answer 1

I think the problem is that the @ operator (equivalent to List.append) is not tail recursive.

The document says this:

Concatenate two lists. Same as the infix operator @. Not tail-recursive (length of the first argument).

You can fix things up by writing a tail-recursive append function.