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

给定字母表["a"; "b"; "c"]我想将所有长度为25的序列转储到文件。（字母可以重复的序列;它不是一个置换）的问题是，我得到一个Stack overflow during evaluation (looping recursion?)当我尝试使用下面的代码：在ocaml中生成大量字母时堆栈溢出

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

是否有这样做的更好的办法？我正在考虑首先生成整个列表，然后将整个列表转储到一个文件，但是我是否必须重复生成partials列表然后转储？会做一些懒惰的帮助？

为什么发生堆栈溢出？ AFAICT，我的generateWords函数是尾递归的。问题是我生成的words列表变得太大而不适合内存？

来源

2011-03-30 grautur

ocaml优化尾递归吗？ – 2011-03-30 23:38:17

@Moron：当然是的！ – 2011-03-30 23:48:07

@Jeff：有趣！真的，我不知道ocaml是关于什么的。就这一点而言，我所知道的语言似乎并没有试图优化尾递归:-) – 2011-03-30 23:51:11

你的函数正在编译为tailcalls。我从线性化的代码证实;从本机编译器ocamlopt[.opt]中的-dlinear选项获得。

事实是，你的堆是成倍增长的，在这种方法中有25个词是不可持续的。尝试与11工作正常（并且是我可以处理的最高）。

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

来源

2011-03-31 01:05:11 nlucaroni

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

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

来源

2011-03-31 01:09:16

狗屎;我忘了那个。我只是看着他所宣布的尾递归函数。尽管如此，他/他仍然必须处理与这种尺寸的字长相关的记忆问题。 – nlucaroni 2011-03-31 01:16:39

在这种情况下，也可以使用'List.rev_map'（而不是改变'List.map'的实现）。 – gasche 2011-03-31 07:27:37

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

回答

相关问题