On Tue, Nov 13, 2012 at 08:06:59AM -0000, oleg@okmij.org wrote:
Alex Stangl posed a problem of trying to efficiently memoize a function without causing divergence: ... But the problem can be fixed: after all, f k is a list of integers. A list is an indexable collection. Let us introduce the explicit index:
import Data.Array((!),Array,elems,listArray) import Data.List(intercalate)
solve = (intercalate " " . map show . elems) a where a :: Array Int Int a = listArray (0, 3) (0 : [f 0 i | i <- [0..]])
f 0 0 = 0 f 0 i = f 1 (i-1) f k i = f (a!0) i
This converges. Here is a bit related problem: http://okmij.org/ftp/Haskell/AlgorithmsH.html#controlled-memoization
Hi Oleg, That works well for the trivial toy test case that I reduced it down to, however it's not clear that it works well for the general case in which significant state is carried across the generation of the successive list elements. To make this concrete, here is the real solve function, which computes a border array (Knuth-Morris-Pratt failure function) for a specified string, before the broken memoization modification is made: solve :: String -> String solve w = let h = length w - 1 wa = listArray (0, h) w pI = 0 : solveR (tail w) 0 solveR :: String -> Int -> [Int] solveR [] _ = [] solveR cl@(c:cs) k = if k > 0 && wa!k /= c then solveR cl (pI!!(k-1)) else let k' = if wa!k == c then k + 1 else k in k' : solveR cs k' in (intercalate " " . map show) pI Here solveR corresponds to f in the toy program and pI is the list I would like to memoize since references to earlier elements could get expensive for high values of k. It is not obvious to me how to apply your index transformation to this, such that what you end up with isn't worse than what we started with. Thanks, Alex