[GHC] #10465: Make listArray non-strict in structure of argument list

[GHC]

#10465: Make listArray non-strict in structure of argument list
-------------------------------------+-------------------------------------
              Reporter:  atze        |             Owner:  ekmett
                  Type:  feature     |            Status:  new
  request                            |         Milestone:
              Priority:  normal      |           Version:  7.10.1
             Component:  Core        |  Operating System:  Unknown/Multiple
  Libraries                          |   Type of failure:  Runtime crash
              Keywords:  laziness    |        Blocked By:
  array                              |   Related Tickets:
          Architecture:              |
  Unknown/Multiple                   |
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------
 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:

 {{{#!hs
 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:

 {{{#!hs
 Main> elems $ failureFunc (listArray (0,23) "participate in parachute")
 *** Exception: <<loop>>
 }}}
 The problem is that listArray is equivalent to:
 {{{#!hs
 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 elements.)

 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:
 {{{#!hs
 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:
 {{{#!hs
 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.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/10465>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler