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 import {-# SOURCE #-} PrelErr ( error )
  33 import PrelTup
  34 import PrelBase
  35 \end{code}
  36
  37 %*********************************************************
  38 %*                                                      *
  39 \subsection{The @Ix@ class}
  40 %*                                                      *
  41 %*********************************************************
  42
  43 \begin{code}
  44 class  (Ord a) => Ix a  where
  45     range               :: (a,a) -> [a]
  46     index               :: (a,a) -> a -> Int
  47     inRange             :: (a,a) -> a -> Bool
  48 \end{code}
  49
  50
  51 %*********************************************************
  52 %*                                                      *
  53 \subsection{Instances of @Ix@}
  54 %*                                                      *
  55 %*********************************************************
  56
  57 \begin{code}
  58 instance  Ix Char  where
  59     range (m,n)
  60       | m <= n          =  [m..n]
  61       | otherwise       =  []
  62     index b@(m,_) i
  63         | inRange b i   =  fromEnum i - fromEnum m
  64         | otherwise     =  indexError i b "Char"
  65     inRange (m,n) i     =  m <= i && i <= n
  66
  67 instance  Ix Int  where
  68     range (m,n)
  69       | m <= n          =  [m..n]
  70       | otherwise       =  []
  71     index b@(m,_) i
  72       | inRange b i     =  i - m
  73       | otherwise       =  indexError i b "Int"
  74     inRange (m,n) i     =  m <= i && i <= n
  75
  76 -- abstract these errors from the relevant index functions so that
  77 -- the guts of the function will be small enough to inline.
  78
  79 {-# NOINLINE indexError #-}
  80 indexError :: Show a => a -> (a,a) -> String -> b
  81 indexError i rng tp
  82   = error (showString "Ix{" . showString tp . showString "}.index: Index " .
  83            showParen True (showsPrec 0 i) .
  84            showString " out of range " $
  85            showParen True (showsPrec 0 rng) "")
  86
  87 -- Integer instance is in PrelNum
  88
  89 ----------------------------------------------------------------------
  90 instance Ix Bool where -- as derived
  91     range   (l,u)
  92       | l <= u    = map toEnum [fromEnum l .. fromEnum u]
  93       | otherwise = []
  94     index   (l,_) i = fromEnum i - fromEnum l
  95     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
  96
  97 ----------------------------------------------------------------------
  98 instance Ix Ordering where -- as derived
  99     range   (l,u)
 100       | l <= u    = map toEnum [fromEnum l .. fromEnum u]
 101       | otherwise = []
 102     index   (l,_) i = fromEnum i - fromEnum l
 103     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 104
 105 ----------------------------------------------------------------------
 106 instance Ix () where
 107     {-# INLINE range #-}
 108     range   ((), ())    = [()]
 109     {-# INLINE index #-}
 110     index   ((), ()) () = 0
 111     {-# INLINE inRange #-}
 112     inRange ((), ()) () = True
 113
 114 ----------------------------------------------------------------------
 115 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
 116     {- INLINE range #-}
 117     range ((l1,l2),(u1,u2)) =
 118       [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
 119
 120     {- INLINE index #-}
 121     index ((l1,l2),(u1,u2)) (i1,i2) =
 122       index (l1,u1) i1 * rangeSize (l2,u2) + index (l2,u2) i2
 123
 124     {- INLINE inRange #-}
 125     inRange ((l1,l2),(u1,u2)) (i1,i2) =
 126       inRange (l1,u1) i1 && inRange (l2,u2) i2
 127
 128 instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
 129     range ((l1,l2,l3),(u1,u2,u3)) =
 130         [(i1,i2,i3) | i1 <- range (l1,u1),
 131                       i2 <- range (l2,u2),
 132                       i3 <- range (l3,u3)]
 133
 134     index ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 135       index (l3,u3) i3 + rangeSize (l3,u3) * (
 136       index (l2,u2) i2 + rangeSize (l2,u2) * (
 137       index (l1,u1) i1))
 138
 139     inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 140       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 141       inRange (l3,u3) i3
 142
 143 instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
 144     range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
 145       [(i1,i2,i3,i4) | i1 <- range (l1,u1),
 146                        i2 <- range (l2,u2),
 147                        i3 <- range (l3,u3),
 148                        i4 <- range (l4,u4)]
 149
 150     index ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 151       index (l4,u4) i4 + rangeSize (l4,u4) * (
 152       index (l3,u3) i3 + rangeSize (l3,u3) * (
 153       index (l2,u2) i2 + rangeSize (l2,u2) * (
 154       index (l1,u1) i1)))
 155
 156     inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 157       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 158       inRange (l3,u3) i3 && inRange (l4,u4) i4
 159
 160 instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
 161     range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
 162       [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
 163                           i2 <- range (l2,u2),
 164                           i3 <- range (l3,u3),
 165                           i4 <- range (l4,u4),
 166                           i5 <- range (l5,u5)]
 167
 168     index ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 169       index (l5,u5) i5 + rangeSize (l5,u5) * (
 170       index (l4,u4) i4 + rangeSize (l4,u4) * (
 171       index (l3,u3) i3 + rangeSize (l3,u3) * (
 172       index (l2,u2) i2 + rangeSize (l2,u2) * (
 173       index (l1,u1) i1))))
 174
 175     inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 176       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 177       inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
 178       inRange (l5,u5) i5
 179 \end{code}
 180
 181 %********************************************************
 182 %*                                                      *
 183 \subsection{Size of @Ix@ interval}
 184 %*                                                      *
 185 %********************************************************
 186
 187 The @rangeSize@ operator returns the number of elements
 188 in the range for an @Ix@ pair:
 189
 190 \begin{code}
 191 {-# SPECIALISE rangeSize :: (Int,Int) -> Int #-}
 192 rangeSize :: (Ix a) => (a,a) -> Int
 193 rangeSize b@(l,h)
 194  | l > h  || isnull (range b) = 0
 195  | otherwise                  = index b h + 1
 196  where
 197   isnull [] = True
 198   isnull _  = False
 199
 200 \end{code}