了解哈斯克尔懒惰评价

Question

原谅我的愚蠢问题，我是哈斯克尔新手。

我试图在Haskell如下：

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

这需要无限的时间。如果我忽略了n <- [1..]，则解决方案立即生效。

我认为这不应该问题，因为哈斯克尔正在评估懒惰。我误解懒惰评估？

Answer 1

注意

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

不会终止为好，因为它会尝试以防万一多一个元素被发现，使得它被包含在总和为“小于10”所有可能的n小号。

相比之下，

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..]