[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

The class Ix


I have realised that the class Ix is under-documented in the Haskell Report.
I propose to add the following:

New section 6.9.1 "The Class Ix".  (Renumber subsections in 6.9).
Arrays may be subscripted by any type in the class @Ix@, which
is defined as follows (definition repeated from Section 4.3.2)

	class (Ord a) => Ix a where
		range   :: (a,a) -> a
		index   :: (a,a) -> a -> Int
		inRange :: (a,a) -> a -> Bool

The @index@ operation maps the upper and lower bounds of the array, and a
subscript, to an integer.  Typically, this integer is used to index a linear 
representation of the array.  The @range@ operation enumerates all
subscripts, and the @inRange@ operation tells whether a particular subscript
lies in the domain of the array.

An implementation is entitled to assume the following laws about these

	and [ index (l,u) l <= index (l,u) s &&
	      index (l,u) s <= index (l,u) u
	    | s <- range (l,u)

	inRange (l,u) i == i `elem` range (l,u)

The first law states that the index of any in-range subscript falls
between the index of the first subscript and that of the last.
The law is required so that the implementation can allocate a
suitably-sized array representation given only the array bounds.

The second law is an obvious consistency condition on @inRange@.

End of proposed text.

It would be possible to be a bit more draconian on the first law.  For
example the following is simpler but more restrictive:

	range (l,u) !! index (l,u) i  ==  i