Переполнение стека при добавлении в изменяемый список

Question

Я пытаюсь написать рекурсивную функцию, которая работает с типом записи с изменяемым полем списка.

Эта функция должна изменять изменяемое поле во время рекурсивных вызовов, добавляя новые значения в список. Все работало нормально, но когда объем входных данных начал увеличиваться, я начал получать ошибки переполнения стека.

Вот минимальный пример, демонстрирующий мою проблему:

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

Это приводит к следующая ошибка:

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

И я получил ту же ошибку при использовании хвостовых рекурсивных функций.

Я не совсем понимаю, что здесь происходит. Какие значения компилятор размещает в стеке? Почему он не использует кучу для хранения элементов списка?

Каковы лучшие методы решения этой проблемы? Следует ли мне выбирать другие структуры данных или использовать неизменяемые списки с деструктивными обновлениями?

Спасибо за любые советы.

Answer 1

Я думаю, проблема в том, что оператор @ (эквивалент List.append) не является хвостовым рекурсивным.

В документе говорится следующее:

Объедините два списка. То же, что и инфиксный оператор @. Не хвостовая рекурсивная (длина первого аргумента).

Вы можете исправить ситуацию, написав хвостовую рекурсивную функцию добавления.