0

我的树定义如下：（只是为了更好地理解，我的数据类型要复杂得多。）

  type tree = {
    mutable value : int;
    mutable nodes : tree list
  }

我需要找到一个0和1的序列，如下图：

    1  
    |
  0 0
  \ /
   1
   |
   1

输出将是根和 0 和 1 的序列。这是我的代码：（我假设该序列仅在树的值为 0 的节点（树列表）只有一个元素时才会出现，但我需要改变它，因为它没有必要。）

let rec getSequence tree = 
  match tree.value with
  | 0 ->
if (List.length tree.nodes) = 1 then
  let nextTree = List.hd tree.nodes in
  match nextTree.value with
  | 1 -> 
    nextTree.nodes <- [];
    tree.nodes <- [nextTree];
    [tree]
  | 0 -> List.concat (List.map (fun t -> getSequence t) nextTree.nodes)
else List.concat (List.map (fun t -> getSequence t) tree.nodes)
  | 1 -> List.concat (List.map (fun t -> getSequence t) tree.nodes)

由于某种原因，当我执行代码时，会引发异常 Stack_overflow。任何人都可以帮助我吗？

4

2 回答 2

0

我试过了，但你的示例输入也不例外。我猜你只会得到更大（特别是更深）输入的 Stack_overflow 异常。

以下是一些选项：

  1. 增加堆栈大小：

    export OCAMLRUNPARAM='l=64M' # 或其他

  2. 将您的函数重写为尾递归，因此它不需要太多的堆栈空间。您可以通过将您的状态作为参数传递来做到这一点。

其他建议：

  • 使用模式匹配代替List.lengthand List.hd。
  • 如果你选择2.，你也可以避免List.concat。
于 2013-10-04T21:08:08.670 回答
0 
let nextTree = List.hd tree.nodes in
nextTree.nodes <- [];

不等同于：

tree.nodes<-(List.tl tree.nodes);

首先，树不会更改它包含的列表，因此您始终执行相同的操作并且您有一个 stack_overflow

于 2013-08-27T22:43:24.750 回答