添加修復記憶？

試圖解決一個任務計算可滿足一些斷言，像元素的平等概括給定的數字組合（有重複）的次數：添加修復記憶？

countChange :: Integer -> [Integer] -> Integer 
countChange n xs = fromIntegral . length $ filter ((== n) . sum) $ 
         concatMap (comb xs) [1..n] 
    where 
    comb _ 0 = [[]] 
    comb xs k = [y:ys | [email protected](y:xs') <- tails xs, ys <- comb l (k-1)]

以上幼稚的做法具有的comb遞歸調用一個顯著的性能問題重複計算k-1組合。

我想通過使用至少固定點，即增加結果的記憶化。通過Data.Function.fix。我添加了一個聲明自遞歸函數，但是失去的想法如何實現memoize功能：

countChange :: Integer -> [Integer] -> Integer 
countChange n xs = fromIntegral . length $ filter ((== n) . sum) $ 
         concatMap (fix (memoize . comb) xs) [1..n] 
    where 
    comb _ _ 0 = [[]] 
    comb xs f k = [y:ys | [email protected](y:xs') <- tails xs, ys <- f (fix (memoize . comb) l (k-1))] 
    memoize f  = undefined -- ??

你可以把一些建議如何解決執行或我的想法完全錯了？

來源

2014-10-30 David Unric

你玩CodeWars？ – Arnon 2014-10-30 21:43:22

@Arnon是的，但這是我的長期挑戰。已經用'Data.Map'寫了memoization，但很好奇怎麼用定點函數做。 – 2014-10-30 21:57:32

因爲如果你把它用數學，而不是編程方式解決這一卡塔非常簡單。我認爲數學解決方案就是他們的目標。它不需要任何memoization。 – Arnon 2014-10-30 22:18:13

當試圖使用遞歸自動記憶時，您必須在遞歸組合器本身中進行記憶，因爲每次遞歸調用都必須共享「記憶」（即存儲記憶值的位置）。

對於爲例，與斐波那契序列，你應該寫類似

fibo' _ 0 = 1 
fibo' _ 1 = 1 
fibo' _ n = (f (n-1)) + (f (n-2)) 

fibo = memoizingFix fibo'

凡memoizingFix取決於哪些功能要memoize的。最通用的方法可能是保持在一國單子一個Data.Map但您可能希望使用不太普遍（例如可變數組）更高效的數據結構。

最後一兩件事，實現您memoizeFix組合子的時候，要記住你是否要存儲從一個電話到另一個或者只是在當前遞歸值。（即：如果我運行fibo hugeValue然後fibo (hugeValue + 1)將第二個電話幾乎只要第一或立竿見影？）

（注：本人自願也沒有，因爲它似乎你願意給你memoizeFix組合子瞭解的東西，自己找，但隨時提出要求 - 甚至是谷歌，它幾乎無處不在互聯網上 - 如果你需要）

來源

2014-10-30 19:36:42 NougatRillettes

添加修復記憶？

回答

相關問題