User defined Ix instances potentially unsafe

[Simon Peyton-Jones]

	[Here's a possible Haskell 98 Library Ix "typo"]

| > > An implementation is entitled to assume the following laws about=20
| > > these operations:
| > >=20
| > >         range (l,u) !! index (l,u) i =3D=3D i   -- when i is in =
range
| > >         inRange (l,u) i =3D=3D i `elem` range (l,u)
| >=20
| > So my "bug" is only in my mind.  Sorry for bothering everyone.
|=20
| I don't think it's quite as straight-forward as that.
| Hugs and ghc may conform to the Library Report, but the=20
| behaviour is still undesirable, and IMHO should be fixed.

I rather agree with this.  But I'm not sure what the fix is.

In thinking about this I've realised that there's an assumption in=20
the Ix interface that

(*)	map index (range (l,u)) =3D [0..rangeSize (l,u)-1]

That is, index maps an index densely into the range 0..N where
N is the size of the array.  Without this assumption, an array
implementation
would need to store the Int bounds of the array as well as the ix
bounds.
I bet that no Haskell implementation does this.

If this were not so, the implementation of rangeSize in Section 5.2=20
would be utterly wrong

	rangeSize b@(l,u) =3D index b h + 1


The constraint (*) also specifies that 'range' returns subscripts
in increasing order of index.  That seems reasonable, but perhaps
less important.  One could alternatively say=20

(*a)	index (l,u) l =3D 0
(*b)	index (l,u) u =3D rangeSize (l,u) - 1

In the spirit of making minimal changes/additions to H98, perhaps (*a)
and (*b)
would be better.

Any thoughts?


Simon

PS: none of this answers Matt's original question which I can rephrase
thus:
if a user provides implementations of index, range etc that do not obey
the specified invariants, can that crash the system?  I would rather the
answer were 'no'.  But that means the implementation would have to check
the output of 'index' against the size of the array allocated from the
supplied
bounds.  Which means that in the common case that 'index' also makes
such
a check there'd be two  checks.  Unless the compiler was clever enough=20
to eliminate one of them, which isn't easy since one is at the 'ix' type
and
the other at 'Int'.