試圖解決一個任務計算可滿足一些斷言,像元素的平等概括給定的數字組合(有重複)的次數:添加修復記憶?
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 -- ??
你可以把一些建議如何解決執行或我的想法完全錯了?
你玩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