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 <<<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.

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