Re: [Haskell-cafe] Strange behavior with listArray
Alex Stangl posed a problem of trying to efficiently memoize a function without causing divergence:
solve = let a :: Array Int Int a = listArray (0, 3) (0 : f 0) f k = if k > 0 then f (a!0) else 0 : f 1 in (intercalate " " . map show . elems) a
Daniel Fischer explained the reason for divergence:
The problem, Alex, is that
f k = if k > 0 then f (a!0) else 0 : f 1
is strict, it needs to know the value of (a!0) to decide which branch to take. But the construction of the array a needs to know how long the list (0 : f 0) is (well, if it's at least four elements long) before it can return the array. So there the cat eats its own tail, f needs to know (a part of) a before it can proceed, but a needs to know more of f to return than it does.
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
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
participants (2)
-
Alex Stangl -
oleg＠okmij.org