在ocaml中生成大量字母时堆栈溢出

Question

给定一个字母表["a"; "b"; "c"]我想将所有长度为25的序列转储到一个文件中.(字母可以按顺序重复;它不是排列.)问题是,Stack overflow during evaluation (looping recursion?)当我尝试使用以下代码时,我得到了一个:

let addAlphabetToPrefix alphabet prefix =
  List.map (function letter -> (prefix ^ letter)) alphabet;;

let rec generateWords alphabet counter words =
  if counter > 25 then
    words
  else
    let newWords = List.flatten(List.map (function word -> addAlphabetToPrefix alphabet word) words) in 
    generateWords alphabet (counter + 1) newWords;;

generateWords ["a"; "b"; "c"] 0 [""];; (* Produces a stack overflow. *)

有没有更好的方法呢？我想先生成整个列表,然后将整个列表转储到文件中,但是我是否必须重复生成部分列表然后转储？会做一些懒惰的帮助吗？

为什么发生堆栈溢出？AFAICT,我的generateWords函数是尾递归的.问题是words我生成的列表变得太大而无法适应内存吗？

Answer 1

您的函数正在编译为tailcalls.我从线性化代码中确认了; 从本-dlinear机编译器中的选项获得,ocamlopt[.opt].

事实是,你的堆呈指数级增长,并且这个方法中有25个单词是不可持续的.尝试11个工作正常(并且是我可以处理的最高).

是的,有一种更好的方法可以做到这一点.您可以通过按字典顺序查找组合索引或使用格雷码(同一页面)来生成组合.这些只需要存储一个单词,可以并行运行,并且永远不会导致分段错误 - 你可能会使用索引方法溢出,在这种情况下你可以切换到大整数但会牺牲速度,或者格雷码(可能难以并行化,具体取决于格雷码).

Answer 2

OCaml优化了尾递归,所以你的代码应该可以工作,除了:List.map遗憾的是,标准库的函数不是尾递归的.堆栈溢出可能发生在其中一个调用中,因为列表变得相当大.

包含电池和Jane Street的核心库都提供尾递归版本map.尝试其中之一,看看它是否解决了问题.