list - 附加到可变列表时堆栈溢出

问题描述

我正在尝试编写一个递归函数，该函数适用于具有可变列表字段的记录类型。

此函数应在递归调用期间修改可变字段，将新值添加到列表中。一切正常，但是当输入数据量开始增加时，我开始收到堆栈溢出错误。

这是一个演示我的问题的最小示例：

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

使用尾递归函数时我遇到了同样的错误。

我不太明白这里发生了什么。编译器在堆栈上分配什么值？为什么它不使用堆来存储列表元素？

解决此问题的最佳实践是什么？我应该选择其他数据结构还是使用具有破坏性更新的不可变列表？

感谢您的任何建议。

标签： listocamlstack-overflowmutable

我认为问题在于@运算符（相当于List.append）不是尾递归的。

该文件说：

连接两个列表。与中缀运算符@ 相同。不是尾递归的（第一个参数的长度）。

您可以通过编写尾递归附加函数来解决问题。

list - 附加到可变列表时堆栈溢出

问题描述

解决方案

推荐阅读