ghc/lib/std/Ix.lhs

   1 %
   2 % (c) The AQUA Project, Glasgow University, 1994-1999
   3 %
   4
   5 \section[Ix]{Module @Ix@}
   6
   7 \begin{code}
   8 {-# OPTIONS -fno-implicit-prelude #-}
   9
  10 module Ix
  11     (
  12         Ix
  13           ( range       -- :: (Ix a) => (a,a) -> [a]
  14           , index       -- :: (Ix a) => (a,a) -> a   -> Int
  15           , inRange     -- :: (Ix a) => (a,a) -> a   -> Bool
  16           )
  17     ,   rangeSize       -- :: (Ix a) => (a,a) -> Int
  18     -- Ix instances:
  19     --
  20     --  Ix Char
  21     --  Ix Int
  22     --  Ix Integer
  23     --  Ix Bool
  24     --  Ix Ordering
  25     --  Ix ()
  26     --  (Ix a, Ix b) => Ix (a, b)
  27     --  ...
  28
  29     -- Implementation checked wrt. Haskell 98 lib report, 1/99.
  30     ) where
  31
  32 #ifndef __HUGS__
  33 import {-# SOURCE #-} PrelErr ( error )
  34 import PrelTup
  35 import PrelBase
  36 import PrelList( null )
  37 import PrelEnum
  38 import PrelShow
  39 import PrelNum
  40
  41 default()
  42 \end{code}
  43
  44 %*********************************************************
  45 %*                                                      *
  46 \subsection{The @Ix@ class}
  47 %*                                                      *
  48 %*********************************************************
  49
  50 \begin{code}
  51 class  (Ord a) => Ix a  where
  52     range               :: (a,a) -> [a]
  53     index, unsafeIndex  :: (a,a) -> a -> Int
  54     inRange             :: (a,a) -> a -> Bool
  55
  56         -- Must specify one of index, unsafeIndex
  57     index b i | inRange b i = unsafeIndex b i
  58               | otherwise   = error "Error in array index"
  59     unsafeIndex b i = index b i
  60 \end{code}
  61
  62 %*********************************************************
  63 %*                                                      *
  64 \subsection{Instances of @Ix@}
  65 %*                                                      *
  66 %*********************************************************
  67
  68 \begin{code}
  69 -- abstract these errors from the relevant index functions so that
  70 -- the guts of the function will be small enough to inline.
  71
  72 {-# NOINLINE indexError #-}
  73 indexError :: Show a => (a,a) -> a -> String -> b
  74 indexError rng i tp
  75   = error (showString "Ix{" . showString tp . showString "}.index: Index " .
  76            showParen True (showsPrec 0 i) .
  77            showString " out of range " $
  78            showParen True (showsPrec 0 rng) "")
  79
  80 ----------------------------------------------------------------------
  81 instance  Ix Char  where
  82     {-# INLINE range #-}
  83     range (m,n) = [m..n]
  84
  85     {-# INLINE unsafeIndex #-}
  86     unsafeIndex (m,_n) i = fromEnum i - fromEnum m
  87
  88     index b i | inRange b i =  unsafeIndex b i
  89               | otherwise   =  indexError b i "Char"
  90
  91     inRange (m,n) i     =  m <= i && i <= n
  92
  93 ----------------------------------------------------------------------
  94 instance  Ix Int  where
  95     {-# INLINE range #-}
  96         -- The INLINE stops the build in the RHS from getting inlined,
  97         -- so that callers can fuse with the result of range
  98     range (m,n) = [m..n]
  99
 100     {-# INLINE unsafeIndex #-}
 101     unsafeIndex (m,_n) i = i - m
 102
 103     index b i | inRange b i =  unsafeIndex b i
 104               | otherwise   =  indexError b i "Int"
 105
 106     {-# INLINE inRange #-}
 107     inRange (I# m,I# n) (I# i) =  m <=# i && i <=# n
 108
 109 ----------------------------------------------------------------------
 110 instance  Ix Integer  where
 111     {-# INLINE range #-}
 112     range (m,n) = [m..n]
 113
 114     {-# INLINE unsafeIndex #-}
 115     unsafeIndex (m,_n) i   = fromInteger (i - m)
 116
 117     index b i | inRange b i =  unsafeIndex b i
 118               | otherwise   =  indexError b i "Integer"
 119
 120     inRange (m,n) i     =  m <= i && i <= n
 121
 122
 123 ----------------------------------------------------------------------
 124 instance Ix Bool where -- as derived
 125     {-# INLINE range #-}
 126     range (m,n) = [m..n]
 127
 128     {-# INLINE unsafeIndex #-}
 129     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 130
 131     index b i | inRange b i =  unsafeIndex b i
 132               | otherwise   =  indexError b i "Bool"
 133
 134     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 135
 136 ----------------------------------------------------------------------
 137 instance Ix Ordering where -- as derived
 138     {-# INLINE range #-}
 139     range (m,n) = [m..n]
 140
 141     {-# INLINE unsafeIndex #-}
 142     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 143
 144     index b i | inRange b i =  unsafeIndex b i
 145               | otherwise   =  indexError b i "Ordering"
 146
 147     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 148
 149 ----------------------------------------------------------------------
 150 instance Ix () where
 151     {-# INLINE range #-}
 152     range   ((), ())    = [()]
 153     {-# INLINE unsafeIndex #-}
 154     unsafeIndex   ((), ()) () = 0
 155     {-# INLINE inRange #-}
 156     inRange ((), ()) () = True
 157     {-# INLINE index #-}
 158     index b i = unsafeIndex b i
 159
 160
 161 ----------------------------------------------------------------------
 162 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
 163     {-# SPECIALISE instance Ix (Int,Int) #-}
 164
 165     {- INLINE range #-}
 166     range ((l1,l2),(u1,u2)) =
 167       [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
 168
 169     {- INLINE unsafeIndex #-}
 170     unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
 171       unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
 172
 173     {- INLINE inRange #-}
 174     inRange ((l1,l2),(u1,u2)) (i1,i2) =
 175       inRange (l1,u1) i1 && inRange (l2,u2) i2
 176
 177     -- Default method for index
 178
 179 ----------------------------------------------------------------------
 180 instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
 181     {-# SPECIALISE instance Ix (Int,Int,Int) #-}
 182
 183     range ((l1,l2,l3),(u1,u2,u3)) =
 184         [(i1,i2,i3) | i1 <- range (l1,u1),
 185                       i2 <- range (l2,u2),
 186                       i3 <- range (l3,u3)]
 187
 188     unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 189       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 190       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 191       unsafeIndex (l1,u1) i1))
 192
 193     inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 194       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 195       inRange (l3,u3) i3
 196
 197     -- Default method for index
 198
 199 ----------------------------------------------------------------------
 200 instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
 201     range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
 202       [(i1,i2,i3,i4) | i1 <- range (l1,u1),
 203                        i2 <- range (l2,u2),
 204                        i3 <- range (l3,u3),
 205                        i4 <- range (l4,u4)]
 206
 207     unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 208       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 209       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 210       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 211       unsafeIndex (l1,u1) i1)))
 212
 213     inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 214       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 215       inRange (l3,u3) i3 && inRange (l4,u4) i4
 216
 217     -- Default method for index
 218
 219 instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
 220     range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
 221       [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
 222                           i2 <- range (l2,u2),
 223                           i3 <- range (l3,u3),
 224                           i4 <- range (l4,u4),
 225                           i5 <- range (l5,u5)]
 226
 227     unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 228       unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
 229       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 230       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 231       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 232       unsafeIndex (l1,u1) i1))))
 233
 234     inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 235       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 236       inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
 237       inRange (l5,u5) i5
 238
 239     -- Default method for index
 240 \end{code}
 241
 242 %********************************************************
 243 %*                                                      *
 244 \subsection{Size of @Ix@ interval}
 245 %*                                                      *
 246 %********************************************************
 247
 248 The @rangeSize@ operator returns the number of elements
 249 in the range for an @Ix@ pair.
 250
 251 \begin{code}
 252 {-# SPECIALISE unsafeRangeSize :: (Int,Int) -> Int #-}
 253 {-# SPECIALISE unsafeRangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
 254 unsafeRangeSize :: (Ix a) => (a,a) -> Int
 255 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 256
 257 {-# SPECIALISE rangeSize :: (Int,Int) -> Int #-}
 258 {-# SPECIALISE rangeSize :: ((Int,Int),(Int,Int)) -> Int #-}
 259 rangeSize :: (Ix a) => (a,a) -> Int
 260 rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
 261                    | otherwise   = 0
 262
 263 -- Note that the following is NOT right
 264 --      rangeSize (l,h) | l <= h    = index b h + 1
 265 --                      | otherwise = 0
 266 --
 267 -- Because it might be the case that l<h, but the range
 268 -- is nevertheless empty.  Consider
 269 --      ((1,2),(2,1))
 270 -- Here l<h, but the second index ranges from 2..1 and
 271 -- hence is empty
 272 \end{code}
 273
 274 \begin{code}
 275 #else
 276 -- This module is empty; Ix is currently defined in the prelude, but should
 277 -- eventually be moved to this library file instead.
 278 #endif
 279 \end{code}