Haskell is lazy

昨天在做Programming Haskell上面的一道练习，脚踏实地的感受了一下Haskell的lazy evaluation得特性。

题目很简单，给出了一个函数unfold，定义如下

unfold :: (b -> Bool) -> (b -> a) -> (b -> b) -> b -> [a]
unfold p h t x | p x = []
            | otherwise = h x : unfold p h t (t x)

unfold通过一个predicate p 来判x的值，如果为True则返回一个空List，否则的话递归计算unfold p h t (t x)，并且把h x的结果加在这个递归返回序列之前。
也就是说，在通常意义下面，predicate p用来结束递归的那个重要的条件。

要求是使用unfold来实现iterate f，(iterate 返回一个无限序列)。

一个解答是

iterate :: (a->a)->a->[a]
iterate f = unfold nf id f
                 where nf x = False

传统的命令式(imperative)程序员乍一看，便会指出一个显而易见的错误，递归的结束条件永远不为真，因为 nf x = False。然而这个判断，却在Haskell面前不成立，起码在当前的这个情况下，因为lazy的Haskell并不急匆匆的一定要找到递归的终止条件不可，才能完成计算。因为在很多情况下，这并非必要。比如，在GHCi下运行take 8 & iterate (*2) 1，便会得到[1,2,4,8,16,32,64]这样一个序列。 我只需要前8个元素，为什么一定要全计算完呢。