通過(guò)什么機(jī)制這個(gè)斐波那契函數(shù)被記憶了？fib = (map fib' [0..] !!) where fib' 1 = 1 fib' 2 = 1 fib' n = fib (n-2) + fib (n-1) 在相關(guān)的說(shuō)明中，為什么這個(gè)版本不是？fib n = (map fib' [0..] !! n) where fib' 1 = 1 fib' 2 = 1 fib' n = fib (n-2) + fib (n-1)
3 回答
開(kāi)滿(mǎn)天機(jī)
TA貢獻(xiàn)1786條經(jīng)驗(yàn) 獲得超13個(gè)贊
我不完全確定，但這是一個(gè)有根據(jù)的猜測(cè)：
編譯器假定fib n在不同的情況下可能有所不同n，因此每次都需要重新計(jì)算列表。畢竟，where聲明中的位可能取決于n。也就是說(shuō)，在這種情況下，整個(gè)數(shù)字列表基本上是一個(gè)函數(shù)n。
沒(méi)有 的版本n可以創(chuàng)建一次列表并將其包裝在一個(gè)函數(shù)中。該列表不能取決于n傳入的值，這很容易驗(yàn)證。該列表是一個(gè)常量，然后被索引到。當(dāng)然，這是一個(gè)懶惰評(píng)估的常量，因此您的程序不會(huì)立即嘗試獲取整個(gè)（無(wú)限）列表。由于它是常量，因此可以在函數(shù)調(diào)用之間共享。
它被記憶了，因?yàn)檫f歸調(diào)用只需要查找列表中的值。由于fib版本一旦懶惰地創(chuàng)建列表，它只是計(jì)算得足以得到答案而不進(jìn)行冗余計(jì)算。這里，“懶惰”意味著列表中的每個(gè)條目都是thunk（未評(píng)估的表達(dá)式）。當(dāng)你做評(píng)估形實(shí)轉(zhuǎn)換，就變成了價(jià)值，所以下一次訪(fǎng)問(wèn)它并沒(méi)有重復(fù)計(jì)算。由于列表可以在調(diào)用之間共享，因此所有先前的條目都已在您需要下一個(gè)條目時(shí)計(jì)算。
它本質(zhì)上是一種基于GHC惰性語(yǔ)義的聰明且低廉的動(dòng)態(tài)編程形式。我認(rèn)為標(biāo)準(zhǔn)只規(guī)定它必須是非嚴(yán)格的，因此兼容的編譯器可能會(huì)編譯此代碼而不進(jìn)行 memoize。但是，在實(shí)踐中，每個(gè)合理的編譯器都會(huì)變得懶惰。
有關(guān)第二種情況的工作原理的更多信息，請(qǐng)閱讀理解遞歸定義的列表（根據(jù)zipWith的文件）。
天涯盡頭無(wú)女友
TA貢獻(xiàn)1831條經(jīng)驗(yàn) 獲得超9個(gè)贊
首先，使用ghc-7.4.2，編譯時(shí)-O2，非記憶版本并不是那么糟糕，F(xiàn)ibonacci數(shù)字的內(nèi)部列表仍然為每個(gè)頂級(jí)調(diào)用函數(shù)記憶。但它不是，也不可能合理地，在不同的頂級(jí)電話(huà)中備忘。但是，對(duì)于其他版本，列表將在調(diào)用之間共享。
這是由于單態(tài)限制。
第一個(gè)是由一個(gè)簡(jiǎn)單的模式綁定（只有名稱(chēng)，沒(méi)有參數(shù)）綁定，因此通過(guò)單態(tài)限制，它必須得到一個(gè)單態(tài)類(lèi)型。推斷類(lèi)型是
fib :: (Num n) => Int -> n
并且這樣的約束被默認(rèn)（在沒(méi)有默認(rèn)聲明的情況下另外說(shuō)明）Integer，將類(lèi)型修改為
fib :: Int -> Integer
因此，只有一個(gè)（類(lèi)型[Integer]）列表要記憶。
第二個(gè)是用函數(shù)參數(shù)定義的，因此它仍然是多態(tài)的，如果內(nèi)部列表在調(diào)用中被記憶，則必須為每個(gè)類(lèi)型記憶一個(gè)列表Num。那不切實(shí)際。
在禁用單態(tài)限制或具有相同類(lèi)型簽名的情況下編譯這兩個(gè)版本，并且兩者都表現(xiàn)出完全相同的行為。（對(duì)于較舊的編譯器版本，情況并非如此，我不知道哪個(gè)版本首先使用它。）
- 3 回答
- 0 關(guān)注
- 449 瀏覽
添加回答
舉報(bào)
0/150
提交
取消