了解Haskell懒惰评估

Question

原谅我的愚蠢问题,我是Haskell的新手.

我在Haskell中尝试了以下内容:

sum [fib n| n <- [1..], (even (fib n) && fib n < 4000000)] 

这需要无限的时间.如果我遗漏n <- [1..],解决方案立即出现.

我认为这无关紧要,因为Haskell正在评估懒惰.我是否误解了懒惰的评价？

Answer 1

注意

sum [ n | n <- [1..], n < 10 ]

也不会终止,因为它会尝试所有可能的ns,以防万一找到一个元素"小于10",以便它包含在总和中.

通过比较,

sum $ takeWhile (< 10) [ n | n <- [1..] ]

将终止,因为takeWhile一旦找到一个项目不满足谓词就会丢弃列表的其余部分<10.

Answer 2

你的列表理解

sum [fib n | n <- [1..], even (fib n) && fib n < 4000000]

相当于表达式

sum $ map fib $ filter (\n -> even (fib n) && fib n < 4000000) [1..]

看看定义filter:

filter :: (a -> Bool) -> [a] -> [a]
filter predicate [] = []
filter predicate (x:xs)
    | predicate x = x : filter predicate xs
    | otherwise   =     filter predicate xs

我们可以看到它始终会检查列表中的每个元素,直到它到达列表的末尾.提供给表达式中过滤的列表[1..]是无限的.这在Haskell中很好,它只是意味着如果强制评估整个列表,过滤器将永远不会完成.然后你把它传递给它map fib,它也可以处理无限列表,但是你得到的是你将它传递给它sum,这需要有一定数量的元素加在一起.

要解决这个问题,正如@chi指出的那样,您可以使用takeWhile:

sum $ map fib $ filter (\n -> even (fib n)) $ takeWhile (\n -> fib n < 4000000) [1..]

虽然我会注意到你fib在这个表达中应用了3次不同的时间.什么是最好的是map fib首先,然后你不必再次申请:

sum $ filter even $ takeWhile (< 4000000) $ map fib [1..]