非尾递归的递归生成的数组参与运算会是lazy的吗？

Magicloud

问题在于，每个人技术水平不同，一个人费劲心力写的代码可能另一个人觉得很容易优化。而并不是总有“另一个人”在旁边伺候，所以我们才要讨论，在语言技术层面上，非尾递归是否是lazy的。这不是一个“我们需要解决这个问题”的问题。

MMMIX

原帖由 Magicloud 于 2009-4-10 09:38 发表
问题在于，每个人技术水平不同，一个人费劲心力写的代码可能另一个人觉得很容易优化。而并不是总有“另一个人”在旁边伺候，所以我们才要讨论，在语言技术层面上，非尾递归是否是lazy的。

实际上 Haskell 的 lazy 体现在语言的各个层面，不是只有尾递归才是 lazy 的。看看下面两个链接应该有帮助：

http://en.wikipedia.org/wiki/Eva ... n-strict_evaluation
http://en.wikibooks.org/wiki/Haskell/Laziness

Magicloud

原帖由 MMMIX 于 2009-4-10 09:47 发表

实际上 Haskell 的 lazy 体现在语言的各个层面，不是只有尾递归才是 lazy 的。看看下面两个链接应该有帮助：

http://en.wikipedia.org/wiki/Eva ... n-strict_evaluation
http://en.wikibo ...

非尾递归可能导致在递归完成前，不能知道第一个元素。而这影响lazy就在于，比如head、甚至map（一直没研究为何map不分左右，而mapAccum分……）。
个人认为这个应该有数学证明……

MMMIX

原帖由 Magicloud 于 2009-4-10 10:36 发表

非尾递归可能导致在递归完成前，不能知道第一个元素。而这影响lazy就在于，比如head、甚至map（一直没研究为何map不分左右，而mapAccum分……）。

我觉得你还是先把上面那两个链接中的文章仔细的看完，然后再猜测，这样可能更靠谱些。

Magicloud

原帖由 MMMIX 于 2009-4-10 11:05 发表

我觉得你还是先把上面那两个链接中的文章仔细的看完，然后再猜测，这样可能更靠谱些。

正是类似内容告诉我，我最后举的例子可能被认为是“第一个元素依赖于其后的元素（虽然业务逻辑上不是这样）”而不能lazy。
这个问题准确的实现是怎样的，很抱歉我看不懂数学论文。所以我来请教这个问题会怎么样处理。

[ 本帖最后由 Magicloud 于 2009-4-10 14:37 编辑 ]

MMMIX

原帖由 Magicloud 于 2009-4-10 14:30 发表

正是类似内容告诉我，我最后举的例子可能被认为是“第一个元素依赖于其后的元素（虽然业务逻辑上不是这样）”而不能lazy。

Really?

这个问题准确的实现是怎样的，

具体细节就不清楚。

很抱歉我看不懂数学论文。

我也没贴什么数学论文，而且这个也不涉及什么数学论文

Magicloud

原帖由 MMMIX 于 2009-4-10 16:05 发表

Really?

具体细节就不清楚。

我也没贴什么数学论文，而且这个也不涉及什么数学论文

我上边说的不能lazy，是指“即使我只需要第一个元素，因为递归问题，而仍需要把所有元素计算一遍……”
包括你贴的wiki在内，都是编译器如何分析（基于数学证明）、实现lazy的概论。而我觉得我这个问题是可以有数学证明的。

MMMIX

原帖由 Magicloud 于 2009-4-13 09:47 发表

我上边说的不能lazy，是指“即使我只需要第一个元素，因为递归问题，而仍需要把所有元素计算一遍……”

非尾递归的程序，通过适当的变形，是可以转换为尾递归或者循环。Higher Order Perl 上有一些例子，可以看看。

[ 本帖最后由 MMMIX 于 2009-4-13 13:56 编辑 ]

Magicloud

原帖由 MMMIX 于 2009-4-13 10:15 发表

一些非尾递归的程序，通过适当的变形，是可以转换为尾递归或者循环。Higher Order Perl 上有一些例子，可以看看。

是的，也有文档提到这样的变形。问题是这种变形是“一些”啊……

MMMIX

原帖由 Magicloud 于 2009-4-13 11:09 发表

是的，也有文档提到这样的变形。问题是这种变形是“一些”啊……

表述不准确，没有“一些”。另外，如果你对这个存疑，可以试着构造一些不能变形为尾递归或者循环的递归的例子。

BTW，递归向循环的转换貌似是有数学证明的，可以翻翻计算理论方面的资料。