原谅我的愚蠢问题,我是哈斯克尔新手。了解哈斯克尔懒惰评价
我试图在Haskell如下:
sum [fib n| n <- [1..], (even (fib n) && fib n < 4000000)]
这需要无限的时间。如果我忽略了n <- [1..]
,则解决方案立即生效。
我认为这不应该问题,因为哈斯克尔正在评估懒惰。我误解懒惰评估?
原谅我的愚蠢问题,我是哈斯克尔新手。了解哈斯克尔懒惰评价
我试图在Haskell如下:
sum [fib n| n <- [1..], (even (fib n) && fib n < 4000000)]
这需要无限的时间。如果我忽略了n <- [1..]
,则解决方案立即生效。
我认为这不应该问题,因为哈斯克尔正在评估懒惰。我误解懒惰评估?
注意
sum [ n | n <- [1..], n < 10 ]
不会终止为好,因为它会尝试以防万一多一个元素被发现,使得它被包含在总和为“小于10”所有可能的n
小号。
相比之下,
sum $ takeWhile (< 10) [ n | n <- [1..] ]
将终止,因为takeWhile
将作为一个项目被发现,但满足谓词<10
尽快丢弃列表的其余部分。
的
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..]