自我參照的功能

Question

我學習Haskell和我下面的表達式上Haskell Wiki 真的困擾了我：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

我不能完全弄清楚爲什麼這個工程。

如果我應用標準柯里格邏輯(zipWith (+))返回一個函數將列表作爲參數，然後返回另一個函數，它將另一個列表作爲參數返回一個列表（zipWith::(a -> b -> c) -> [a] -> [b] -> [c]）。因此，fibs是對列表的引用（尚未評估），(tail fibs)是相同（未評估）列表的尾部。當我們嘗試評估（take 10 fibs）時，前兩個元素綁定到0和1。換句話說，fibs==[0,1,?,?...]和(tail fibs)==[1,?,?,?]。第一次添加完成後fibs變爲[0,1,0+1,?,..]。同樣，在第二次加入後，我們得到[0,1,0+1,1+(0+1),?,?..]

• 我的邏輯是否正確？
• 有沒有一個更簡單的方式來解釋這一點？ （來自知道Haskell編譯器對此代碼做什麼的人的任何見解？）（鏈接和引用是受歡迎的）
• 確實，這種類型的代碼僅適用於懶惰評估？
• 我做什麼評估fibs !! 4？
• 此代碼是否假定zipWith首先處理元素？ （我想應該沒有，但我不明白爲什麼不）

EDIT2：我只是發現了上述問題，並問及回答here。如果我浪費了任何人的時間，我很抱歉。

編輯：這是一個比較困難的情況下，理解（來源：Project Euler forums）：

filterAbort :: (a -> Bool) -> [a] -> [a] 
filterAbort p (x:xs) = if p x then x : filterAbort p xs else [] 

main :: Int 
main = primelist !! 10000 
     where primelist = 2 : 3 : 5 : [ x | x <- [7..], odd x, all (\y -> x `mod` y /= 0) (filterAbort (<= (ceiling (sqrt (fromIntegral x)))) primelist) ] 

注意all (\y -> x mod y /= 0)...怎麼能指X這裏不是導致無限遞歸？

Answer 1

我會跟蹤評價你：

> fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 

有了：

> zipWith f (a:as) (b:bs) = f a b : zipWith f as bs 
> zipWith _ _  _  = [] 

> tail (_:xs)    = xs 
> tail []     = error "tail" 

所以：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 
↪ fibs = 0 : 1 : ((+) 0 1 : zipWith (+) (tail fibs) (tail (tail fibs))) 
↪ fibs = 0 : 1 : 1 : ((+) 1 1 : zipWith (+) (tail (tail fibs)) (taii (tail (tail fibs)))))  
↪ fibs = 0 : 1 : 1 : 2 : ((+) 1 2 : zipWith (+) (tail (tail (tail fibs))) (tail (taii (tail (tail fibs)))))) 
↪ fibs = 0 : 1 : 1 : 2 : 3 : ((+) 2 3 : zipWith (+) (tail (tail (tail (tail fibs)))) (tail (tail (taii (tail (tail fibs))))))) 

等，所以，如果你索引到這種結構，它會強制評估每一步纖維，直到找到指標。

爲什麼這樣高效？一個字：分享。

由於計算fibs，它在堆中增長，記錄已經計算機的值。之後對fibs的返回引用可重新使用fibs的所有先前計算的值。免費記憶！

分享在堆中看起來像什麼？

至於你問的列表的末尾對象，哈斯克爾計算未來值，記錄它，並移動，自我參照下一個節點。

這終止的事實嚴重依賴於懶惰。