1

我正在使用以下控制结构（我认为它是尾递归的）

untilSuccessOrBigError :: (Eq e) => (Integer -> (Either e a)) -> Integer -> e -> (Either e a)
untilSuccessOrBigError f count bigError
  = case f count of
         Right x -> Right x
         Left e -> (if e==bigError then Left e else untilSuccessOrBigError f (count - 1) e)

做迭代深化

iterativeDeepening :: (a -> [a]) -> (a -> Bool) -> (a -> Bool) -> a -> Either String a
iterativeDeepening stepFunc isAValidSolution isGraphBottom x
  = untilSuccessOrBigError
        (\count -> dfsWithMaxDepth stepFunc isAValidSolution isGraphBottom count x)
        (-1)
        "Reached graph bottom"

在每次迭代深化之后，这个空闲内存（因为它在技术上将不再能够到达它），如果不是，我应该如何重写控制结构？

PS在第二个虽然看起来这会失败，因为尾递归结构经常能够访问堆栈上的东西，比如添加到前一个值，即使在这种情况下它没有。– Roman A. Taycher 11 月 28 日 12:33 PPS 在第三个问题上，尽管它让我认为它可以在 dfsWithMaxDepth 返回后立即丢弃 dfsWithMaxDepth 中的值，并且一堆答案不会占用太多内存。– Roman A. Taycher 11 月 2 日

4

1 回答 1

2

乍一看，没有理由不能正确收集垃圾，也没有理由不执行 TCO。

一般来说，您应该在 Haskell 中以不同的方式考虑 tco 和垃圾收集——SO 上列出的许多相关问题似乎很有帮助。从根本上说，您想将 GHC Haskell 的操作语义想象为惰性图缩减。

想象一下，您在内存中只有整个 AST，从名称的每次用法到其定义都有额外的箭头，并且您要求“main”的值。现在要得到它，您需要查看 main 中调用的第一个函数的值，并将其替换，这反过来意味着您需要追逐下一个需要评估的东西，等等。现在在某个时刻通过这种缩减，您会注意到过去作为表达式指向的事物现在已被计算出来，并替换为它们所代表的值。然后这些表达式可以被垃圾收集。同时，您从图表顶部到您现在正在评估的任何部分的跟踪是“堆栈”。因此，如果要评估一个结构，您需要评估该结构的“内部”，那么这将增加您的堆栈。

以上内容草率且随意，但可能有助于提供直觉。

于 2010-11-28T15:02:12.527 回答