haskell - 递归函数组合中的懒惰

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+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 , 你有类似的评价，直到最后一行 where $!部队 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 但我认为这个想法应该仍然是正确的)。