[Haskell-cafe] Strange behavior with listArray

[Alex Stangl]

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
>