附加到可变列表时堆栈溢出
Stack overflow when appending to a mutable 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
我在使用尾递归函数时遇到了同样的错误。
我不太明白这是怎么回事。编译器在堆栈上分配什么值?为什么不使用堆来存储列表元素?
解决此问题的最佳做法是什么?我应该选择其他数据结构还是使用具有破坏性更新的不可变列表?
感谢您的任何建议。
我认为问题在于 @
运算符(相当于 List.append
)不是尾递归的。
文件是这样说的:
Concatenate two lists. Same as the infix operator @. Not tail-recursive (length of the first argument).
您可以通过编写尾递归追加函数来解决问题。
我正在尝试编写一个适用于具有可变列表字段的记录类型的递归函数。
此函数应在递归调用期间修改可变字段,将新值添加到列表中。一切正常,但是当输入数据量开始增加时,我开始出现堆栈溢出错误。
这是一个演示我的问题的最小示例:
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
我在使用尾递归函数时遇到了同样的错误。
我不太明白这是怎么回事。编译器在堆栈上分配什么值?为什么不使用堆来存储列表元素?
解决此问题的最佳做法是什么?我应该选择其他数据结构还是使用具有破坏性更新的不可变列表?
感谢您的任何建议。
我认为问题在于 @
运算符(相当于 List.append
)不是尾递归的。
文件是这样说的:
Concatenate two lists. Same as the infix operator @. Not tail-recursive (length of the first argument).
您可以通过编写尾递归追加函数来解决问题。