Alex Stangl | 12 Nov 04:50 2012
Picon

Strange behavior with listArray

I'm stymied trying to figure out why the program below blows up with
<<<loop>>> 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
Bas van Dijk | 12 Nov 08:36 2012
Picon

Re: Strange behavior with listArray

On 12 November 2012 04:50, Alex Stangl <alex <at> stangl.us> wrote:
> I'm stymied trying to figure out why the program below blows up with
> <<<loop>>> 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
Alex Stangl | 12 Nov 14:43 2012
Picon

Re: 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 <alex <at> stangl.us> wrote:
> > I'm stymied trying to figure out why the program below blows up with
> > <<<loop>>> 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, <<<loop>>>. 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.
(Continue reading)

Daniel Fischer | 12 Nov 14:52 2012

Re: Strange behavior with listArray

On Montag, 12. November 2012, 08:36:49, Bas van Dijk wrote:
> On 12 November 2012 04:50, Alex Stangl <alex <at> stangl.us> wrote:
> > I'm stymied trying to figure out why the program below blows up with
> > <<<loop>>> 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.

(Continue reading)

Bas van Dijk | 12 Nov 14:55 2012
Picon

Re: Strange behavior with listArray

On 12 November 2012 14:52, Daniel Fischer
<daniel.is.fischer <at> googlemail.com> wrote:
> I see no loop in that, and ghci doesn't either:

Oops you're right of course.

Bas
Alex Stangl | 12 Nov 21:24 2012
Picon

Re: 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
> 
(Continue reading)

oleg | 13 Nov 09:06 2012

Re: 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
(Continue reading)

Alex Stangl | 14 Nov 03:21 2012
Picon

Re: Strange behavior with listArray

On Tue, Nov 13, 2012 at 08:06:59AM -0000, oleg <at> 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:
(Continue reading)

oleg | 14 Nov 08:39 2012

Re: 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 <at> (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
(Continue reading)

Alex Stangl | 14 Nov 15:01 2012
Picon

Re: Strange behavior with listArray

On Wed, Nov 14, 2012 at 07:39:33AM -0000, oleg <at> 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 "aaaaaaaaaaaa"
> > t2s3 = solve2 "abbaabba"

My hat's off to you, sir. This is kind of interesting -- I would
(Continue reading)


Gmane