User defined Ix instances potentially unsafe

[Marcin 'Qrczak' Kowalczyk]

Mon, 7 May 2001 03:15:16 -0700, Simon Peyton-Jones <simonpj@microsoft.com> pisze:

> The constraint (*) also specifies that 'range' returns subscripts
> in increasing order of index.  That seems reasonable, but perhaps
> less important.

It is important if elems should return elements in the same order as
indices returns indices, and as listArray accepts.

I'm afraid that making arrays robust wrt. bogus Ix instances at the
cost of further overheads means a larger pressure to avoid Ix at all
in other contexts. It's already avoided in Manuel's parallel arrays,
and it was a trouble for me for making ghc's Array/UArray/IArray/MArray
operations faster - for example there is an better implementation of
compare which works only for index types with particular properties,
including Int but not (Int,Int), and sticking to 0-based Ints would
make this much simpler, as well as making packed strings implemented
in terms of UArrays more efficient.

There are other problems. The report says that repeated indices in
array construction is an error. Ghc doesn't check that and lets later
values win. To implement what the report says it would have to be
less efficient: avoiding a separate array for marking which elements
are initialized would need unsafePtrEq on each store and probably a
loop after the construction which would replace missing elements with
bottoms which are not unsafePtrEq, so initialization of another array
can distinguish absent elements from elements taken from this array.

I'm not sure whether I should still use Ix-based arrays in my unified
collection experiments etc., which don't fit there well, or say STOP
at some point, concentrate on 0-based Int-indexed dynamic vectors
with the interface of sequences, optionally adding Array support as a
Haskell 98 compatibility kludge. Having mutable arrays with immutable
bounds is also a small problem. Generally Ix-based Arrays may become
a larger trouble to support than they are really worth.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^                      SYGNATURA ZASTĘPCZA
QRCZAK