Opened 7 years ago

Closed 7 years ago

Last modified 6 years ago

#2158 closed merge (fixed)

deriving (Ix) and listArray give unexpected results

Reported by: guest Owned by: igloo
Priority: normal Milestone: 6.8.3
Component: libraries/base Version: 6.6
Keywords: Cc: scook0@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Test Case: arr019
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

When arrayList is used together with a derived instance of Ix, the results are not the same as what the Haskell 98 report suggests.

import Data.Array
import Data.Ix

data Pos = Pos Integer Integer
  deriving (Show, Eq, Ord, Ix)

{-
-- copied from the H98 report, with (,) replaced by Pos
instance Ix Pos where
  range (Pos l l', Pos u u')
    = [ Pos i i' | i <- range (l, u), i' <- range (l', u') ]
  index (Pos l l', Pos u u') (Pos i i')
    = index (l, u) i * rangeSize (l', u') + index (l', u') i'
  inRange (Pos l l', Pos u u') (Pos i i')
    = inRange (l, u) i && inRange (l', u') i'
-}

contents = concat $
  [ "ABCD"
  , "wxyz"
  , "1234"
  ]

-- example definition of listArray from the H98 report
listArray98 b xs = array b (range b `zip` xs)

array1 = listArray   (Pos 0 0, Pos 2 3) contents
array2 = listArray98 (Pos 0 0, Pos 2 3) contents


main = if array1 == array2
  then putStrLn "arrays are equal"
  else putStrLn "arrays are NOT equal"

In this example, array1 and array2 should be equal, but they are not. The listArray function interprets its argument list in a different order from listArray98.

The underlying problem seems to be that the integer indices produced by the derived Ix do not agree with the order implied by range, but listArray assumes that they do. Replacing either the Ix instance or the listArray definition with the H98 version gives correct results.

Change History (5)

comment:1 Changed 7 years ago by igloo

  • difficulty set to Unknown
  • Milestone set to 6.8.3
  • Owner set to igloo

Right, http://haskell.org/onlinereport/ix.html says that

range (l,u) !! index (l,u) i == i   -- when i is in range

must hold, but

Prelude Foo Data.Array> let l = Pos 0 0; u = Pos 2 3; i = Pos 0 1 in range (l,u) !! index (l,u) i == i
False

I'll take a look.

comment:2 Changed 7 years ago by igloo

  • Test Case set to arr019
  • Type changed from bug to merge

Fixed in the HEAD:

Sun Mar 30 19:28:13 BST 2008  Ian Lynagh <[email protected]>
  * Derive a valid Ix instance for data Foo = Foo Int Int
  The old one didn't satisfy the axioms. See trac #2158 for details.

comment:3 Changed 7 years ago by igloo

  • Resolution set to fixed
  • Status changed from new to closed

Merged

comment:4 Changed 6 years ago by simonmar

  • Architecture changed from Unknown to Unknown/Multiple

comment:5 Changed 6 years ago by simonmar

  • Operating System changed from Unknown to Unknown/Multiple
Note: See TracTickets for help on using tickets.