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.

Jeffrey Scofield · Accepted Answer · 2020-05-05 16:46:59Z

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.

answered May 5, 2020 at 16:46

Jeffrey Scofield

67k2 gold badges77 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

jubnzv Over a year ago

Tail-recusrive append is really solves the problem in this minimal example. But it doesn't works for me in the project, probably because some functions from JaneStreet's core library which I use is not tail recursive too. I'll go figure it out, thank you!

jubnzv Over a year ago

Yes, the problem was that I use not tail-recursive functions with the large lists. Thanks, everything works now. I also found a good way to get more informative backtrace for the same errors: I compile project into bytecode and run it using ocamlrun -b (maybe it could be useful for someone else).

Collectives™ on Stack Overflow

Stack overflow when appending to a mutable list

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related