CODEWITHSUNDEEP
haskell
wilywampa
wilywampa

Reputation: 1340

Strange <<loop>> exception in Array generation

I ran into an infinite loop problem in Haskell and can't understand what the cause is. I have three versions of the same code below. The first one causes an infinite loop while the latter two do not. This is some basic contrived code to generate an array recursively. In this case it has only three items and the only recursive call is for the third item which picks the bigger of the first two. The if a > b statement seems to cause a loop (but later I show that it can't be the cause).

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 following version, I simply use max a b instead of the if statement. No loop here.

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 a b)
            | otherwise = (i, 0)

In the following version, I keep the if but zip the indices instead of returning a tuple from func. This one also runs fine.

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

Those two other cases seem to show that there is no problem with the recursive definition or the use of the if statement.

What does that leave as the cause of the loop?

Upvotes: 6

Views: 70

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152682

Here is an interesting observation: in (i, max a b), we know (before computing either a or b) that this tuple has i in its first component. Similarly, in your zip code, we can observe that the first parts of the tuples are 0, 1, and 2 without computing 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 bottom, for example, then the result of this expression is bottom, not a tuple with i in the first part!

This matters because computing a > b requires computing a, which requires knowing which value is in position 0 in the array, which requires knowing whether i is 0 in the last element of the mapped list (and hence should overwrite the previous 0 value) -- a loop.

One fix is to lift the (i, _) part out of the if, and use (i, if a > b then a else b). This is essentially what your max solution does.

Upvotes: 6

Related Questions