Make listArray non-strict in structure of argument list
There is a subtle caveat when using Data.Array.IArray.listArray, which could be easily avoided.
The problem is that listArray strict in the structure of the list, and hence if this structure depends on the result of listArray, then the result is undefined. However, listArray does not have to be strict in the structure of the list.
As an example, consider computing the "failure function" for the Knuth-Morris-Pratt algorithm:
failureFunc :: Eq a => Array Int a -> Array Int Int
failureFunc string = result where
result = listArray (bounds string) (-1 : 0 : getMatch 2 0)
getMatch :: Int -> Int -> [Int]
getMatch p matchPos
| matchPos < 0 = 0 : getMatch (p+1) 0
| string ! (p - 1) == string ! matchPos = matchPos + 1 : getMatch (p+1) (matchPos+1)
| otherwise = getMatch p (result ! matchPos) -- use result!
This seems reasonable, we just use the result of elements < i to construct element i. However, it does not work:
Main> elems $ failureFunc (listArray (0,23) "participate in parachute")
*** Exception: <<loop>>
The problem is that listArray is equivalent to:
listArray b l = array b (zip (range b) l)
(Recall that array is strict in the structure of the given list, and in the first elements of the tuples in this list, but not in the second elements of the tuples.)
The structure of the list l=(-1 : 0 : getMatch 2 0) depends on the observing elements of the array (result ! matchPos). The structure of (zip (range b) l) is strict in the structure of l, and hence failure loops.
Proposed solution: redefine listArray as equivalent to:
listArray b l = array b (zipLazyRight (range b) l)
zipLazyRight :: [a] -> [b] -> [(a,b)]
zipLazyRight [] _ = []
zipLazyRight (h:t) l = (h,head l): zipLazyRight t (tail l)
The difference is that listArray is now non-strict in the structure of the argument list, because zipLazyRight is non-strict in the right argument. Using this definition, failureFunc does not fail:
Main> elems $ failureFuncArr (toArr "participate in parachute")
[-1,0,0,0,0,0,0,0,1,2,0,0,0,0,0,0,1,2,3,0,0,0,0,0]
This does not change the semantics uses of listArray which were already defined: it just makes more uses of listArray defined.