瞭解哈斯克爾懶惰評價

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