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