[Haskell-cafe] Strange behavior with listArray

[Daniel Fischer]

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.

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.