Strange behavior with listArray

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Strange behavior with listArray

Alex Stangl
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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior with listArray

Bas van Dijk-2
On 12 November 2012 04:50, Alex Stangl <[hidden email]> 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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior with listArray

Alex Stangl
On Mon, Nov 12, 2012 at 08:36:49AM +0100, Bas van Dijk wrote:

> On 12 November 2012 04:50, Alex Stangl <[hidden email]> 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.

Thanks,

Alex

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior with listArray

Daniel Fischer
In reply to this post by Bas van Dijk-2
On Montag, 12. November 2012, 08:36:49, Bas van Dijk wrote:

> On 12 November 2012 04:50, Alex Stangl <[hidden email]> 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.

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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior with listArray

Bas van Dijk-2
On 12 November 2012 14:52, Daniel Fischer
<[hidden email]> wrote:
> I see no loop in that, and ghci doesn't either:

Oops you're right of course.

Bas

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior with listArray

Alex Stangl
In reply to this post by Daniel Fischer
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior with listArray

oleg-30
In reply to this post by Alex Stangl

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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior with listArray

Alex Stangl
On Tue, Nov 13, 2012 at 08:06:59AM -0000, [hidden email] 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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior with listArray

oleg-30
In reply to this post by Alex Stangl

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 "aaaaaaaaaaaa"
> 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 "aaaaaaaaaaaa"
> t2s3 = solve2 "abbaabba"


The unit tests pass.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Strange behavior with listArray

Alex Stangl
On Wed, Nov 14, 2012 at 07:39:33AM -0000, [hidden email] 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
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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe