递归函数组合中的惰性

Question

我试图理解 Haskell 的惰性评估，并在 GHCi

中进行了以下尝试

GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Prelude> :set +m
Prelude> let iterateUntilError1 :: (a->a) -> (a->a)
Prelude|     iterateUntilError1 f = (iterateUntilError1 f) . f
Prelude| 
Prelude> let iterateUntilError2 :: (a->a) -> (a->a)
Prelude|     iterateUntilError2 f = \x -> (iterateUntilError2 f) . f $ x
Prelude| 
Prelude> let iterateUntilError3 :: (a->a) -> (a->a)
Prelude|     iterateUntilError3 f = \x -> (iterateUntilError3 f) . f $! x
Prelude| 
Prelude> let iterateUntilError4 x = foldl1 (.) (repeat (($!) x))
Prelude> iterateUntilError3 tail [1..5]
*** Exception: Prelude.tail: empty list
Prelude> iterate tail [1..5]
[[1,2,3,4,5],[2,3,4,5],[3,4,5],[4,5],[5],[],*** Exception: Prelude.tail: empty list

在显示的4个版本中，只有iterateUntilError3按预期工作，其他3个版本进入无限循环，必须通过Ctrl+[=20停止=]C。我不太明白为什么其他三个版本在这种情况下不起作用。

相关问题 laziness and function composition (haskell, erlang) 似乎没有解决此问题中提出的问题。

Answer 1

让我们从iterateUntilError1开始。如果你尝试评估

iterateUntilError1 tail [1..5] =

扩展 iterateUntilError1 的定义：

((iterateUntilError1 tail) . tail) [1..5] =

扩展 . 的定义：

(iterateUntilError1 tail) (tail [1..5]) =

等等，我们又来了iterateUntilError1 tail！

((iterateUntilError1 tail) . tail) (tail [1..5]) =
(iterateUntilError1 tail) (tail (tail [1..5]))

等等。

对于 iterateUntilError3 你有（插入一些额外的括号以使优先级更清楚）

iterateUntilError3 tail [1..5] =
((iterateUntilError3 tail) . tail) $! [1..5] =
((iterateUntilError3 tail) . tail) (1:[2..5]) = 
iterateUntilError3 tail (tail (1:[2..5])) =
(iterateUntilError3 tail . tail) $! (tail (1:[2..5])) =
(iterateUntilError3 tail . tail) (2:[3..5]) = ...

所以它最终得到一个错误。

使用 iterateUntilError2，你有类似的评估，直到最后一行，其中 $! 强制 tail 减少直到获得构造函数，而 $ 没有：

(iterateUntilError2 tail . tail) $ (tail [1..5]) =
(iterateUntilError2 tail . tail) (tail [1..5]) =
(iterateUntilError2 tail) (tail (tail [1..5])) = ...

最后（为简单起见，将 tail_ 用于 (tail $!)）：

iterateUntilError4 tail [1..5] =
foldl1 (.) (repeat tail_) [1..5] = 
foldl (.) tail_ (repeat tail_) [1..5] =
foldl (.) (tail_ . tail_) (repeat tail_) [1..5] =
foldl (.) (tail_ . tail_ . tail_) (repeat tail_) [1..5] = ...

（对于这个我没有遵循 the actual definition 但我认为这个想法应该仍然是正确的）。

递归函数组合中的惰性

Laziness in recursive function composition

recursion

haskell

lazy-evaluation

function-composition