Re: [Haskell-cafe] Strange behavior with listArray
On Wed, Nov 14, 2012 at 07:39:33AM -, o...@okmij.org wrote: > dimensional memo table. Luckily, our case is much less general. We do > have a very nice dynamic programming problem. The key is the > observation > k' : solveR (i+1) k' > After a new element, k', is produced, it is used as an argument to the > solveR to produce the next element. This leads to a significant > simplification: > > > solve2 :: String -> Array Int Int > > solve2 w = pI > > where > > h = length w - 1 > > wa = listArray (0, h) w > > pI = listArray (0,h) $ 0 : [ solveR i (pI!(i-1)) | i <- [1..] ] > > solveR :: Int -> Int -> Int > > solveR i k = > >let c = wa!i in > >if k > 0 && wa!k /= c > > then solveR i (pI!(k-1)) > > else let k' = if wa!k == c > >then k + 1 > >else k > >in k' > > > > t2s1 = solve2 "the rain in spain" > > t2s2 = solve2 "" > > t2s3 = solve2 "abbaabba" My hat's off to you, sir. This is kind of interesting -- I would normally consider this indexing transformation as an approach for defeating memoization, yet in this case it serves as the key that makes the broader memoization possible, lifting it up a level. Thanks! Alex P.S. A side benefit of this approach is that it's easy to switch from listArray to array, since we already have the index handy. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange behavior with listArray
Alex Stangl wrote: > 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. Ok, let's apply a few program transformations. First we notice that the list pI must have the same length as the string w. Since we have already converted the string w to an array, wa, we could index into that array. We obtain the following version. > solve1 :: String -> String > solve1 w = (intercalate " " . map show) pI > where > h = length w - 1 > wa = listArray (0, h) w > pI = 0 : solveR 1 0 > solveR :: Int -> Int -> [Int] > solveR i k | i > h = [] > solveR i k = >let c = wa!i in >if k > 0 && wa!k /= c > then solveR i (pI!!(k-1)) > else let k' = if wa!k == c >then k + 1 >else k >in k' : solveR (i+1) k' > > t1s1 = solve1 "the rain in spain" > t1s2 = solve1 "" > t1s3 = solve1 "abbaabba" We don't need to invent an index: it is already in the problem. The unit tests confirm the semantics is preserved. The _general_ next step is to use the pair of indices (i,k) as the key to the two dimensional memo table. Luckily, our case is much less general. We do have a very nice dynamic programming problem. The key is the observation k' : solveR (i+1) k' After a new element, k', is produced, it is used as an argument to the solveR to produce the next element. This leads to a significant simplification: > solve2 :: String -> Array Int Int > solve2 w = pI > where > h = length w - 1 > wa = listArray (0, h) w > pI = listArray (0,h) $ 0 : [ solveR i (pI!(i-1)) | i <- [1..] ] > solveR :: Int -> Int -> Int > solveR i k = >let c = wa!i in >if k > 0 && wa!k /= c > then solveR i (pI!(k-1)) > else let k' = if wa!k == c >then k + 1 >else k >in k' > > t2s1 = solve2 "the rain in spain" > t2s2 = solve2 "" > t2s3 = solve2 "abbaabba" The unit tests pass. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange behavior with listArray
On Tue, Nov 13, 2012 at 08:06:59AM -, o...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange behavior with listArray
On Mon, Nov 12, 2012 at 02:52:28PM +0100, Daniel Fischer wrote: > 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. > > g and h are not strict, they simply let the construction write thunks into > the array elements, and those can then later be evaluated after the > construction of a has returned. Thanks for the thoughtful, detailed answer. If you have a function like f that has conditional logic, and accesses earlier elements in the list stream, can this be memoized? It appears that constructing an array via array or listArray won't work, nor does an IntMap. I can layer my list index [1] on top to speed up the list access, but this isn't as good as using an array. Thanks, Alex [1] http://github.com/astangl/list-index > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange behavior with listArray
On 12 November 2012 14:52, Daniel Fischer wrote: > I see no loop in that, and ghci doesn't either: Oops you're right of course. Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange behavior with listArray
On Montag, 12. November 2012, 08:36:49, Bas van Dijk wrote: > On 12 November 2012 04:50, Alex Stangl wrote: > > I'm stymied trying to figure out why the program below blows up with > > <<>> when I use "f 0" > > If you replace the a!0 in f by its value 0, f is equivalent to: > > f k = if k > 0 > then f 0 > else 0 : f 1 > > Do you see the loop now? I see no loop in that, and ghci doesn't either: Prelude> let f :: Int -> [Int]; f k = if k > 0 then f 0 else 0 : f 1 Prelude> take 5 $ f 1 [0,0,0,0,0] and if you use (f 0) instead of (f (a!0)) there, it works. > > Maybe you meant f to be: > > f k = if k > 0 > then f (a!k) > else 0 : f 1 Loops too. 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. g and h are not strict, they simply let the construction write thunks into the array elements, and those can then later be evaluated after the construction of a has returned. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange behavior with listArray
On Mon, Nov 12, 2012 at 08:36:49AM +0100, Bas van Dijk wrote: > On 12 November 2012 04:50, Alex Stangl wrote: > > I'm stymied trying to figure out why the program below blows up with > > <<>> when I use "f 0" > If you replace the a!0 in f by its value 0, f is equivalent to: > > f k = if k > 0 > then f 0 > else 0 : f 1 > > Do you see the loop now? I realize it loops/recurses, just like h does, or any instance of building lazy infinite data structures. It works fine when you only extract a finite number of elements from the infinite structure. It's not clear why that is not happening here, as if there is a failure of laziness. f 0 should effectively yield [0, 0, ...], correct? > Maybe you meant f to be: > > f k = if k > 0 > then f (a!k) > else 0 : f 1 Actually it was that way in the original program. I switched it to 0 the process of trying to "distill" it down to a simplest test. Either way yield the same result, <<>>. If you take the array reference out, this code works fine, as it obviously should. But with the array reference intact, it appears listArray isn't accessing the list lazily enough. Thanks, Alex ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Strange behavior with listArray
On 12 November 2012 04:50, Alex Stangl wrote: > I'm stymied trying to figure out why the program below blows up with > <<>> when I use "f 0" If you replace the a!0 in f by its value 0, f is equivalent to: f k = if k > 0 then f 0 else 0 : f 1 Do you see the loop now? Maybe you meant f to be: f k = if k > 0 then f (a!k) else 0 : f 1 Regards, Bas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Strange behavior with listArray
I'm stymied trying to figure out why the program below blows up with <<>> when I use "f 0" for building the array, but if I substitute g or h in place of f, they work fine. Is this a bug or am I overlooking something? I am using GHC 7.4.2. Thanks, Alex P.S. Forgive the seemingly pointless program; I distilled this test from a longer actual program that was exhibiting this behavior. import Data.Array((!),Array,elems,listArray) import Data.List(intercalate) 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 g k = k : a!(k+1) : a!(k+1) : a!(k+2) : a!(k+3) : [] h k = a!k : h (k+1) in (intercalate " " . map show . elems) a main = putStrLn solve ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
