OCaml 生成大量字母序列时出现堆栈溢出错误

Question

给定一个字母表["a"; "b"; "c"]，我想将长度为25的所有序列转储到文件中。（序列中的字母可以重复，它不是排列。）问题是，当我尝试使用以下代码时，会出现评估期间的堆栈溢出（循环递归？）：

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. *)

有没有更好的方法来做这个？我在考虑先生成整个列表，然后将整个列表转储到文件中，但是我是否需要重复生成部分列表然后转储？将某些内容变为lazy是否有帮助？

为什么会发生堆栈溢出？据我所知，我的generateWords函数是尾递归的。问题在于我正在生成的words列表太大而无法放入内存吗？

- grautur

---

OCaml 会优化尾递归吗？ - Aryabhatta

@Jeff：有趣！真的，我对OCaml一无所知。只知道我了解的语言似乎并不关心优化尾递归 :-) - Aryabhatta

你应该使用#trace来追踪generateWords函数，以便更好地理解这个问题。我认为问题在于你正在生成一个巨大的列表（潜在的26^25个单词），因此自然会耗尽内存。再加上你是递归生成的，会产生许多中间结果。 - Jeff Mercado

Answer 1

您的函数正在作为尾调用进行编译。我从本地编译器ocamlopt[.opt]的-dlinear选项获得的线性化代码中确认了这一点。

事实是，您的堆正在呈指数级增长，而在这种方法中，25个单词是不可持续的。尝试使用11个单词可以正常工作（并且是我能够处理的最高数量）。

是的，有更好的方法来完成这个任务。您可以通过查找组合的字典序排列或使用格雷码（同一页）来生成它们。这些方法只需要一个单词的存储空间，可以并行运行，并且永远不会导致分段错误--但是使用索引方法可能会溢出，此时您可以切换到大整数，但会牺牲速度，或者使用格雷码（具体取决于格雷码是否容易并行化）。

- nlucaroni

Answer 2

OCaml会优化尾递归，因此您的代码应该可以正常工作，但是：标准库中的List.map函数不支持尾递归，这可能导致栈溢出错误，特别是当列表变得很大时。

Batteries Included和Jane Street的Core库都提供了map的尾递归版本。尝试使用其中之一，看看是否可以解决问题。

- Michael Ekstrand

---

糟糕，我忘了那个。我只看他声明的尾递归函数。但是，他/她仍然必须处理那么大的字长所带来的内存问题。 - nlucaroni

在这种情况下，也可以使用List.rev_map（而不是更改List.map的实现）。 - gasche