ocaml - 在 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

您的函数被编译为尾调用。我从线性化代码中确认；从 -dlinear 获得 native 编译器中的选项，ocamlopt[.opt] .

事实是，您的堆正在呈指数增长，在这种方法中 25 个字是不可持续的。尝试使用 11 效果很好(并且是我可以处理的最高值)。

是的，有更好的方法来做到这一点。您可以通过查找 index of the combination in lexicographical order 来生成组合。或使用格雷码(同一页)。这些只需要存储一个单词，可以并行运行，并且永远不会导致段错误——尽管使用索引方法可能会溢出，在这种情况下，您可以切换到大整数，但会牺牲速度，或者格雷码(可能难以并行化，具体取决于格雷码)。