Haskell中的尾部调用内存管理
我正在使用以下控制结构（我认为是尾递归）
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"
在每次迭代加深之后，是否会释放内存（因为它在技术上不再能够达到它），如果不是，我应该如何重写控制结构？
聚苯乙烯 其次，这看起来会失败，因为尾递归结构经常能够访问堆栈上的内容，例如添加到前一个值，即使在这种情况下不能。 – Roman A. Taycher 11 月 28 日 12:33 聚苯硫醚 第三，尽管这让我认为一旦 dfsWithMaxDepth 返回，它就可以丢弃 dfsWithMaxDepth 中的值，并且一堆答案不会占用太多内存。 – 罗曼·泰彻 (Roman A. Taycher) 11 月 2 日
I'm using the following control structure(which I think is tail recursive)
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)
to do iterative deepening
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"
will this free memory (since it will no longer technically be able to reach it) as at after each iterative deepening, if not how should I rewrite the control structure?
P.S.
On second though it looks like this will fail since tail recursive structures frequently be able to access things on the stack like adding to the previous value, even if it doesn't in this case. – Roman A. Taycher Nov 28 at 12:33
P.P.S.
On third though it makes me think that it can discard the values inside dfsWithMaxDepth as soon as dfsWithMaxDepth returns and a bunch of answers won't take up much memory. – Roman A. Taycher Nov 2
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
乍一看，没有理由不能正确地进行垃圾收集，也没有理由不执行 TCO。
一般来说，你应该在 Haskell 中以不同的方式考虑 tco 和垃圾收集——这里列出的许多相关问题似乎很有帮助。从根本上讲，您希望将 GHC Haskell 的操作语义想象为惰性图缩减。
想象一下，您的内存中只有整个 AST，还有从名称的每次使用到其定义的附加箭头，并且您要求“main”的值。现在要得到这个，你需要查看 main 中调用的第一个函数的值，并将其替换进去，这反过来意味着你需要追逐下一个需要评估的东西，等等。现在在某个时刻通过这种减少，您会注意到过去作为表达式指向的内容现在已被计算，并替换为它们表示的值。然后这些表达式可以被垃圾收集。同时，从图表顶部到您现在正在评估的任何部分所获得的跟踪就是“堆栈”。因此，如果要评估一个结构，您需要评估该结构的“内部”，那么这将增加您的堆栈。
上面的内容是草率和手作的，但可能有助于给出直觉。
At first glance, there's no reason that this won't be garbage collected properly, and why TCO won't be performed.
In general, you should think about tco and garbage collection in a different way in Haskell -- lots of related questions listed here on SO seem helpful. Fundamentally you want to imagine the operational semantics of GHC Haskell as lazy graph reduction.
Imagine that you just have the whole AST in memory, with additional arrows from every usage of a name to its definition, and you ask for the value of "main." Now to get that, you need to look at the value of the first function called in main, and substitute it in, which in turn means that you need to chase the next thing that needs to be evaluated, etc. Now at some point in this reduction, you'll notice that things that used to be pointed to as expressions have now been computed, and replaced with the values they represent. Then those expressions can get garbage collected. Meanwhile, the trace you've got from the top of the graph down to whatever piece you're now evaluating is the "stack". So if to evaluate a structure, you need to evaluate "inside" that structure, then that's going to grow your stack.
The above is sloppy and handwavy, but might help to give an intuition.