Strange exception <<loop>> in array generation

Question

I ran into an infinite loop problem in Haskell and can't figure out what the reason is. I have three versions of the same code below. The first causes an infinite loop, and the last two do not. This is some basic contrived code to generate an array recursively. In this case, it has only three elements and a single recursive call for the third element, which selects more of the first two. The if a > b seems to trigger a loop (but later on I show that this cannot be the reason).

 import Data.Array main :: IO () main = print grid where grid = array (0, 2) $ map func [0 .. 2] func i | i == 2 = let a = grid ! (i - 1) b = grid ! (i - 2) in if a > b then (i, a) else (i, b) | otherwise = (i, 0) 

In the next version, I just use max ab instead of the if . There is no loop.

 main :: IO () main = print grid where grid = array (0, 2) $ map func [0 .. 2] func i | i == 2 = let a = grid ! (i - 1) b = grid ! (i - 2) in (i, max ab) | otherwise = (i, 0) 

In the next version, I keep the if indexes, but zip instead of returning a tuple from func . This also works great.

 main :: IO () main = print grid where grid = array (0, 2) $ zip [0 .. 2] $ map func [0 .. 2] func i | i == 2 = let a = grid ! (i - 1) b = grid ! (i - 2) in if a > b then a else b | otherwise = 0 

These two other cases seem to indicate that there is no problem with recursively defining or using an if .

What does this leave as the cause of the cycle?

Answer 1

Here's an interesting point: in (i, max ab) we know (before computing either a or b ) that this tuple has i in its first component. Similarly, in your zip code, we can notice that the first parts of the tuples are 0 , 1 and 2 without calculating the second parts of the tuples. However, in if a > b then (i, a) else (i, b) it is not obvious that we have a tuple with i in the first part: if a > b is the bottom, for example, then the result of this expression is a lower, not a tuple with i in the first part!

This is because the calculation of a > b requires the calculation of a , which requires knowing what value is at position 0 in the array, which requires knowing whether i 0 in the last element of the matched list (and therefore must overwrite the previous value 0 ) - cycle.

One fix is ​​to remove the (i, _) from if and use (i, if a > b then a else b) . This is essentially what your max solution makes.