The Data.Array.* hierarchy is unsafe (or, Segfaulting for fun and profit)

Nils Anders Danielsson nad at
Tue Dec 5 13:50:28 EST 2006

On Tue, 05 Dec 2006, Simon Marlow <simonmarhaskell at> wrote:

> To me, the wording "An implementation is entitled to assume..."
> implies that there are no obligations on the implementation should the
> assumption not hold -
> no obligation to yield _|_ or any other behaviour.

I guess that's a valid interpretation.

As an aside, it is interesting to note that the Ix instance for
Integer does not satisfy the first law (if a wraparound semantics is
used for Int; this is allowed by the report). With
  l = 0, u = toInteger (maxBound :: Int) + 1 and i = u
we have
  inRange (l,u) i = True
  range (l,u) !! index (l,u) i = ⊥ ≠ i.

Furthermore, more seriously, the third law isn't type correct, and a
corrected version,

  map (index (l,u)) (range (l,u)) == [0..rangeSize (l,u)],

isn't satisfied by the Ix instance for Int, since (with
b = (0, 0 :: Int))
  map (index b) (range b) = [0]
  [0..rangeSize b] = [0, 1].
I think the law should really be

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

This law is also prone to overflow errors, by the way.


More information about the Libraries mailing list