4 The Ix Class

module Ix ( Ix(range, index, inRange) ) where class (Text a, Ord a) => Ix a where range :: (a,a) -> [a] index :: (a,a) -> a -> Int inRange :: (a,a) -> a -> Bool instance Ix Char where ... instance Ix Int where ... instance Ix Integer where ... instance (Ix a, Ix b) => Ix (a,b) where ... -- et cetera instance Ix Bool where ... instance Ix Ordering where ...

The class Ix provides operations range, index and inRange. The index operation maps the lower and upper 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 operations:

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

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

4.1 Deriving Instances of Ix

Derived instance declarations for the class Ix are only possible for enumerations (i.e. datatypes having only nullary constructors) and single-constructor datatypes (including tuples) whose constituent types are instances of Ix.

• For an enumeration, the nullary constructors are assumed to be numbered left-to-right with the indices 0 through n-1. For example, given the datatype:

  
  data  Colour = Red | Orange | Yellow | Green | Blue | Indigo | Violet
  

  we would have:

  
  range   (Yellow,Blue)        ==  [Yellow,Green,Blue]
  index   (Yellow,Blue) Green  ==  1
  inRange (Yellow,Blue) Red    ==  False
  

• For single-constructor datatypes, the derived instance declarations are created as shown for tuples in Figure 1.

class (Ord a) => Ix a where range :: (a,a) -> [a] index :: (a,a) -> a -> Int inRange :: (a,a) -> a -> Bool rangeSize :: (Ix a) => (a,a) -> Int rangeSize (l,u) = index (l,u) u + 1 instance (Ix a, Ix b) => Ix (a,b) where range ((l,l'),(u,u')) = [(i,i') | i <- range (l,u), i' <- range (l',u')] index ((l,l'),(u,u')) (i,i') = index (l,u) i * rangeSize (l',u') + index (l',u') i' inRange ((l,l'),(u,u')) (i,i') = inRange (l,u) i && inRange (l',u') i' -- Instances for other tuples are obtained from this scheme: -- -- instance (Ix a1, Ix a2, ... , Ix ak) => Ix (a1,a2,...,ak) where -- range ((l1,l2,...,lk),(u1,u2,...,uk)) = -- [(i1,i2,...,ik) | i1 <- range (l1,u1), -- i2 <- range (l2,u2), -- ... -- ik <- range (lk,uk)] -- -- index ((l1,l2,...,lk),(u1,u2,...,uk)) (i1,i2,...,ik) = -- index (lk,uk) ik + rangeSize (lk,uk) * ( -- index (lk-1,uk-1) ik-1 + rangeSize (lk-1,uk-1) * ( -- ... -- index (l1,u1))) -- -- inRange ((l1,l2,...lk),(u1,u2,...,uk)) (i1,i2,...,ik) = -- inRange (l1,u1) i1 && inRange (l2,u2) i2 && -- ... && inRange (lk,uk) ik

4.2 Library Ix

module Ix ( Ix(range, index, inRange) ) where

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

instance  Ix Char  where
    range (c,c')        =  [c..c']
    index b@(c,c') ci
        | inRange b ci  =  fromEnum ci - fromEnum c
        | otherwise     =  error "LibIx.index: Index out of range."
    inRange (c,c') ci   =  fromEnum c <= i && i <= fromEnum c'
                           where i = fromEnum ci

instance  Ix Int  where
    range (m,n)         =  [m..n]
    index b@(m,n) i
        | inRange b i   =  i - m
        | otherwise     =  error "LibIx.index: Index out of range."
    inRange (m,n) i     =  m <= i && i <= n

instance  Ix Integer  where
    range (m,n)         =  [m..n]
    index b@(m,n) i
        | inRange b i   =  fromInteger (i - m)
        | otherwise     =  error "LibIx.index: Index out of range."
    inRange (m,n) i     =  m <= i && i <= n

instance (Ix a,Ix b) => Ix (a, b) -- as derived, for all tuples
instance Ix Bool                  -- as derived
instance Ix Ordering              -- as derived

Next section: Array
The Haskell 1.3 Library Report