problems with Array.elems in ghc-5.02

[Marcin 'Qrczak' Kowalczyk]

Tue, 23 Oct 2001 22:01:07 +0200, Bostjan Slivnik <bostjan.slivnik at fri.uni-lj.si> pisze:

>    instance Ix Foo where
>     range (lo@(Foo _ foos),hi) = (filter ((<=)lo).filter ((>=)hi)) foos
>     inRange (Foo lo _,Foo hi _) (Foo f _) = inRange (lo,hi) f
>     index _ (Foo f _) = f

This instance doesn't fulfill the law from the Haskell 98 Report
which an implementation is entitled to assume:

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

For example if l = Foo 2 lstOfFoos, u = Foo 5 lstOfFoos, i = l
then range (l,u) !! index (l,u) i = Foo 4 lstOfFoos.

ghc-5.02 makes use of this for more efficient implementations of
various array operations. In particular the range size is computed
as the index of its last element + 1 (if the range is nonempty),
which gives two more than the length returned by range in your case,
so two elements are not initialized by the function array. The function
elems now iterates over the physical array elements instead of going
through range.

Perhaps it's possible to find a hole in the report by supplying
a bogus definition of (==) for indices, so although the law holds
when taken literally, some equal elements are not really equivalent...
I don't know.

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