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