理解哈斯克爾斐波那契

Question

fibs :: [Int] 
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)] 

這會生成斐波那契數列。

我瞭解警衛的行爲，:，zip和tail，但我不明白<-。它在這裏做什麼？

Answer 1

解析器如何知道進入（a，b）的內容？

編輯：感謝ViralShah，我會讓這個少一點gnomic。 「< - 」告訴解析器將右側的「zip fibs（tail fibs）」對的列表分配到左側的「（a，b）」。

Answer 2

列表理解在括號中：

[ a + b | (a, b) <- zip fibs (tail fibs)] 

返回包含輸出的列表（A + B），其中變量a和b來自的

zip fibs (tail fibs) 

Answer 3

結果由於upvotes我把我的評論變成了答案。

你看到的並不是一個警衛，但它是list comprehension。對於初學者來說，認爲它是一種表達數學集合符號的方式，如A = {x | x元素N}這意味着沿着以下幾行：集合A是所有自然數的集合。在列表理解將是[x | x <- [1..] ]。

您也可以對您的號碼使用約束：[x | x <- [1..], x `mod` 2 == 0 ]以及其他許多事情。

有很多好的哈斯克爾turorials那裏覆蓋列表理解，甚至有關haskell資源的StackOverflow問題。

Answer 4

唯一棘手的是zip fibs (tail fibs)。 zip只是從它的每個參數構成一個成對的列表。所以，如果你有兩個列表如下：

[ 1, 2, 3, 4 ] 
[ "a", "b", "c", "d" ] 

荏苒他們會讓：

[ (1,"a"), (2,"b"), (3,"c"), (4,"d") ] 

左箭頭（分配到解構模式）只是提取配對的元素，因此它們可以被加到一起。壓縮的兩個列表是fibs和(tail fibs) - 換句話說，斐波那契序列和斐波那契序列偏移1個元素。 Haskell是懶惰評估的，所以它可以計算列表，但是需要很多元素。這也適用於zip。

Answer 5

讓我們展開。

zip從兩個列表的內容中創建對。所以第一對zip fibs (tail fibs)給我們是(0, 1)，它加起來爲1.所以現在的列表是[0,1,1]。我們現在知道列表中的三個元素，因此列表理解可以繼續，從列表中獲取下一個項目，從尾部獲取下一個項目，這會使(1,1) - 加在一起，得到2.然後，我們得到下一對，即(1,2)，製作序列3中的下一個數字。這可以無限地繼續，因爲理解總會提供足夠的項目。

Answer 6

對於它的價值，我發現下面的版本更容易理解：

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

Answer 7

一個優點函數式編程的是，像這是一個數學問題，您可以評估通過手的表達式：

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)] 
    = 0 : 1 : [ a + b | (a, b) <- zip [0, 1, ??] (tail [0, 1, ??])] 

這裏??是尚未評估的部分。我們將在我們繼續時填寫它。

 = 0 : 1 : [ a + b | (a, b) <- zip [0, 1, ??] [1, ??])] 
    = 0 : 1 : [ a + b | (a, b) <- (0, 1) : zip [1, ??] [??]] 

請注意，我eliding的zip評價，因爲它的定義是這裏沒有給出細節是不是真的有密切關係的當前問題。這是我將用來顯示每對數字由zip創建並由列表理解消耗的符號。

 = 0 : 1 : 0+1 : [ a + b | (a, b) <- zip [1, ??] [??]] 
    = 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, ??] [??]] 

現在我們知道，在??下一個元素是1：

 = 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, 1, ??] [1, ??]] 
    = 0 : 1 : 1 : [ a + b | (a, b) <- (1, 1) : zip [1, ??] [??]] 
    = 0 : 1 : 1 : 1+1 : [ a + b | (a, b) <- zip [1, ??] [??]] 
    = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, ??] [??]] 

下一個元素是2：

 = 0 : 1 : 1 : 2 : [ a + b | (a, b) <- zip [1, 2, ??] [2, ??]] 

沖洗和重複。

Answer 8

它定義該流圖

  .----->>------->>----. 
     /     \ 
     /     / 
     \     /  
    <---- 0 <---- 1 ---<<--- (+)  
       /   \   
       \    \   
        \   /  
        *---->>------*  

因爲它產生了從本身拉動新的輸入，但總是由一個和兩個位置產生點之前，保持兩個「返回指針」到序列它是。這反映在定義fibs = 0:1:[ a+b | a <- fibs | b <- tail fibs]，並列表理解（:set -XParallelListComp等）。

因爲它只是使用它的最後元素，它相當於

map fst . iterate (\(a, b) -> (b, a+b)) $ (0,1) 

Answer 9

我還是不明白。我喜歡這個答案：https://stackoverflow.com/a/42183415/246387（來自code-apprentice）。

，但我不知道如何從這一行：

= 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, ??] [??]] 

將其移動到這一點：

= 0 : 1 : 1 : [ a + b | (a, b) <- zip [1, 1, ??] [1, ??]] 

再說這個，我有打擾我別的東西：

我如何在列表理解中使用fib如果我根本沒有fib（所以看起來，但肯定我錯了），因爲fib isn'尚未計算。 「等待」（在等號的左側）計算在右側（等號）。