哈斯克爾：提高我的尾遞歸斐波那契實現

我想出了下面的尾遞歸斐波那契數發生器的工作原理：哈斯克爾：提高我的尾遞歸斐波那契實現

let { 
    fibo :: Integral x => [x]->x->x->x->[x] 
    fibo l x y 0 = l 
    fibo l x y n = fibo (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1) 
}

原諒我整個實現放在同一行，因爲我使用的GHCI並沒有完全學會如何把它放在一個文件中並運行（我還沒有到達那裏）。我想知道的是如何調用：

fibo [0, 1] 0 1 5

可以改進。我不想通過0和1的初始列表，然後再次通過0和1的限制。我相信實施可以改變。可以做些什麼改變？

來源

2012-07-25 badmaash

你可以像你的解釋（無需包裹將它寫在一個文件中逐行一切都放在let塊中），然後在解釋器中加載文件（在GHCi中使用：l filename） – Cubic 2012-07-25 18:58:02

您的代碼是尾遞歸的，但效率非常低，因爲（++）在其第一論據。但我想這不是問題的一部分。 – 2012-07-25 18:58:25

Haskell中的尾遞歸不像使用嚴格的語言那樣需要不斷的堆棧使用，反之非尾遞歸也不需要線性堆棧使用，所以我質疑您的練習的價值。坦率地說，我會用經典的'fibs = 0：1：zipWith（+）fibs（tail fibs）'或者其中一個變體'scanl'或'unfoldr'。看到[這個HaskellWiki頁面]（http://www.haskell.org/haskellwiki/The_Fibonacci_sequence）的一堆實現。 – 2012-07-25 20:13:50

你的算法是尾遞歸的，但它看起來像有其他的缺點，即1）你正在建立結果列表追加到它的末尾，2）它不是懶惰的。

對於1），請注意當附加兩個列表a ++ b時，您必須重新分配a。在你的情況下，a是斐波納契數字的增長列表，b是接下來的兩個術語。因此，每次迭代重新分配已經計算出的斐波納契數，並添加兩個更多的元素，這將導致二次運行時間。將b預先加到a的前面會更有效率。你將會生成斐波納契數字，但運行時間將是線性的。如果您希望序列按升序排列，則可以在末尾列表reverse。

請注意，按照相反的順序構建列表，您可以使用Code-Guru的模式匹配思路輕鬆獲取序列的最後兩個條件。

對於2），請注意，在整個計算完成之前，您無法獲取列表的第一個元素。用下面的懶惰代序列的比較：

fibs = 0 : (go 0 1) 
    where go a b = b : go b (a+b)

即使它看起來像遞歸從未停止，fibs只計算之多是必要的。例如，fibs !! 3只需撥打go幾次。

來源

2012-07-25 19:28:36 ErikR

...這意味着我可以控制從Haskell中的函數外部遞歸？ – badmaash 2012-07-26 03:39:25

是的 - 這是查看它的一種方法 - 您不必提前決定多少條款來計算 – ErikR 2012-07-26 03:42:53

我不打算去算法本身，但這裏有一些關於如何構建遞歸函數的建議。

首先，這裏你將如何格式化一個單獨的文件代碼

fibo :: Integral x => [x]->x->x->x->[x] 
fibo l x y 0 = l 
fibo l x y n = fibo (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

如果您保存此爲fibo.hs，那麼你就可以

ghci fibo.hs

開始GHCI加載文件在開始時。你也可以用命令

:l fibo.hs

（assumming您在保存fibo.hs相同的目錄開始GHCI）

另一個優點是，現在當你編輯的文件開始GHCI後加載文件，只需在GHCi提示符下輸入

:r

即可重新加載所有更改。

現在，爲了擺脫額外的參數，Haskell中的常規模式是將遞歸部分重構爲其自身的輔助函數，並將主函數作爲僅接受必要參數的入口點。例如，

fibo :: Integral x => x -> [x] 
fibo n = fiboHelper [0,1] 0 1 n 

fiboHelper :: Integral x => [x]->x->x->x->[x] 
fiboHelper l x y 0 = l 
fiboHelper l x y n = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

現在，您可以撥打fibo簡單地

> fibo 3 
[0,1,1,2,3,5,8,13]

此外，一個輔助函數像這樣的是沒有用的本身通常是隱藏在主函數中的使用let內部函數或where。

fibo :: Integral x => x -> [x] 
fibo n = fiboHelper [0,1] 0 1 n where 
    fiboHelper l x y 0 = l 
    fiboHelper l x y n = fiboHelper (l ++ [y+x] ++ [y+x+y]) (x+y) (y+x+y) (n-1)

像這樣的內部函數通常給出一個較短的名稱，因爲背景使得其目的明確，所以我們可以將名稱更改爲如fibo'。

go是遞歸輔助函數的另一個常用名稱。

來源

2012-07-25 19:37:40 shang

+1。 – badmaash 2012-07-26 03:41:37

只是爲了記錄：爲斐波那契數的列表的「通常」的定義是：

fibo = 0 : scanl (+) 1 fibo

來源

2012-07-26 13:01:30 Landei

或（少一點奧術）'fibo = 0：1：zipWith（+）fibo（尾纖維）' – fuz 2012-07-27 09:51:32

這很漂亮。 – 0sh 2013-10-14 12:25:20

哈斯克爾：提高我的尾遞歸斐波那契實現

回答

相關問題