Ix
The last type class I want to mention here is Ix. We encountered it before
when talking about arrays. It is the
class of all types that can be used as array indices. This includes integers,
characters, Booleans and more esoteric types such as ((Int, Bool), Char).
:info Ix
type Ix :: * -> Constraint
class Ord a => Ix a where
range :: (a, a) -> [a]
index :: (a, a) -> a -> Int
GHC.Ix.unsafeIndex :: (a, a) -> a -> Int
inRange :: (a, a) -> a -> Bool
rangeSize :: (a, a) -> Int
GHC.Ix.unsafeRangeSize :: (a, a) -> Int
{-# MINIMAL range, (index | unsafeIndex), inRange #-}
-- Defined in ‘GHC.Ix’
Ix is a subclass of Ord, so types in the Ix type class must be orderable.
Clearly, this makes sense because the entries in an array are arranged in a
linear order, and our mapping from indices to array slots reflects this
ordering.
A type that is an instance of Ix needs to support the following operations,
all of which are used under the hood of the implementations of the various
array functions:
The range function converts a range of array bounds represented as a pair
consisting of the minimum array index and the maximum array index into the list
of array indices. The indices function for arrays is really just a call to
range.
>>> range ((1,1),(3,3))
[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]
Even though we can use rather fancy types as array indices, Haskell programs
still run on real computers, so Haskell arrays are still only chunks of memory
and accessing an array element requires to determine its position in this chunk.
Under the hood, Haskell arrays are 0-based arrays as in C, Rust, Java, and every
other programming language. To translate an index of type a into a 0-based
integer index, we use the index function. Given the range of array indices, of
type (a, a), and a particular index value a, it converts the index into the
corresponding integer index.
>>> index ((1,1),(3,3)) (1,1)
0
>>> index ((1,1),(3,3)) (1,3)
2
There's also unsafeIndex. index calls inRange to check that the given
index is in the given range. Otherwise, bad things will happen if we try to
translate this index into an array position. unsafeIndex skips this check.
This is clearly more efficient, but you should never use unsafeIndex. It is
used under the hood of low-level array code exactly to make array operations
faster.
inRange rng ix checks whether ix is part of the range rng:
>>> inRange ((1,1),(3,3)) (2,3)
True
>>> inRange ((1,1),(3,3)) (1,4)
False
>>> inRange ((1,1),(3,3)) (2,0)
False
Finally, rangeSize and its unsafe cousin unsafeRangeSize return the number
of indices in a given range. It's the length of the list returned by range,
but it is implemented using arithmetic only, without generating this list. When
creating an array, the various array functions use rangeSize to determine the
amount of memory to be allocated for an array, based on the provided range of
array indices.
>>> rangeSize ((1,1),(3,3))
9
>>> length $ range ((1,1),(3,3))
9