ghc/lib/std/Array.lhs

   1 %
   2 % (c) The AQUA Project, Glasgow University, 1994-1999
   3 %
   4
   5 \section[Array]{Module @Array@}
   6
   7 \begin{code}
   8 {-# OPTIONS -fno-implicit-prelude #-}
   9
  10 module  Array
  11
  12     (
  13       module Ix                 -- export all of Ix
  14     , Array                     -- Array type is abstract
  15
  16     , array         -- :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
  17     , listArray     -- :: (Ix a) => (a,a) -> [b] -> Array a b
  18     , (!)           -- :: (Ix a) => Array a b -> a -> b
  19     , bounds        -- :: (Ix a) => Array a b -> (a,a)
  20     , indices       -- :: (Ix a) => Array a b -> [a]
  21     , elems         -- :: (Ix a) => Array a b -> [b]
  22     , assocs        -- :: (Ix a) => Array a b -> [(a,b)]
  23     , accumArray    -- :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
  24     , (//)          -- :: (Ix a) => Array a b -> [(a,b)] -> Array a b
  25     , accum         -- :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
  26     , ixmap         -- :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a b
  27
  28     -- Array instances:
  29     --
  30     --   Ix a => Functor (Array a)
  31     --   (Ix a, Eq b)  => Eq   (Array a b)
  32     --   (Ix a, Ord b) => Ord  (Array a b)
  33     --   (Ix a, Show a, Show b) => Show (Array a b)
  34     --   (Ix a, Read a, Read b) => Read (Array a b)
  35     --
  36
  37     -- Implementation checked wrt. Haskell 98 lib report, 1/99.
  38
  39     ) where
  40
  41 #ifndef __HUGS__
  42 import Ix
  43 import PrelList
  44 import PrelShow
  45 import PrelArr          -- Most of the hard work is done here
  46 import PrelBase
  47 #else
  48 import Ix
  49 import List( (\\) )
  50 #endif
  51
  52 infixl 9  !, //
  53 \end{code}
  54
  55 #ifndef __HUGS__
  56
  57
  58 %*********************************************************
  59 %*                                                      *
  60 \subsection{Definitions of array, !, bounds}
  61 %*                                                      *
  62 %*********************************************************
  63
  64 \begin{code}
  65
  66 #ifdef USE_FOLDR_BUILD
  67 {-# INLINE indices #-}
  68 {-# INLINE elems #-}
  69 {-# INLINE assocs #-}
  70 #endif
  71
  72 {-# SPECIALISE listArray :: (Int,Int) -> [b] -> Array Int b #-}
  73 listArray             :: (Ix a) => (a,a) -> [b] -> Array a b
  74 listArray b vs        =  array b (zip (range b) vs)
  75
  76 {-# SPECIALISE indices :: Array Int b -> [Int] #-}
  77 indices               :: (Ix a) => Array a b -> [a]
  78 indices               =  range . bounds
  79
  80 {-# SPECIALISE elems :: Array Int b -> [b] #-}
  81 elems                 :: (Ix a) => Array a b -> [b]
  82 elems a               =  [a!i | i <- indices a]
  83
  84 {-# SPECIALISE assocs :: Array Int b -> [(Int,b)] #-}
  85 assocs                :: (Ix a) => Array a b -> [(a,b)]
  86 assocs a              =  [(i, a!i) | i <- indices a]
  87
  88 {-# SPECIALISE amap :: (b -> c) -> Array Int b -> Array Int c #-}
  89 amap                  :: (Ix a) => (b -> c) -> Array a b -> Array a c
  90 amap f a              =  array b [(i, f (a!i)) | i <- range b]
  91                          where b = bounds a
  92
  93 ixmap                 :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c
  94 ixmap b f a           =  array b [(i, a ! f i) | i <- range b]
  95 \end{code}
  96
  97
  98 %*********************************************************
  99 %*                                                      *
 100 \subsection{Instance declarations for Array type}
 101 %*                                                      *
 102 %*********************************************************
 103
 104 \begin{code}
 105 instance Ix a => Functor (Array a) where
 106   fmap = amap
 107
 108 instance  (Ix a, Eq b)  => Eq (Array a b)  where
 109     a == a'             =  assocs a == assocs a'
 110     a /= a'             =  assocs a /= assocs a'
 111
 112 instance  (Ix a, Ord b) => Ord (Array a b)  where
 113     compare a b = compare (assocs a) (assocs b)
 114
 115 instance  (Ix a, Show a, Show b) => Show (Array a b)  where
 116     showsPrec p a = showParen (p > 9) (
 117                     showString "array " .
 118                     shows (bounds a) . showChar ' ' .
 119                     shows (assocs a)                  )
 120     showList = showList__ (showsPrec 0)
 121
 122 {-
 123 instance  (Ix a, Read a, Read b) => Read (Array a b)  where
 124     readsPrec p = readParen (p > 9)
 125            (\r -> [(array b as, u) | ("array",s) <- lex r,
 126                                      (b,t)       <- reads s,
 127                                      (as,u)      <- reads t   ])
 128     readList = readList__ (readsPrec 0)
 129 -}
 130 \end{code}
 131
 132
 133 #else
 134 \begin{code}
 135 data Array ix elt = Array (ix,ix) (PrimArray elt)
 136
 137 array :: Ix a => (a,a) -> [(a,b)] -> Array a b
 138 array ixs@(ix_start, ix_end) ivs = primRunST (do
 139   { mut_arr <- primNewArray (rangeSize ixs) arrEleBottom
 140   ; mapM_ (\ (i,v) -> primWriteArray mut_arr (index ixs i) v) ivs
 141   ; arr <- primUnsafeFreezeArray mut_arr
 142   ; return (Array ixs arr)
 143   }
 144   )
 145  where
 146   arrEleBottom = error "(Array.!): undefined array element"
 147
 148 listArray               :: Ix a => (a,a) -> [b] -> Array a b
 149 listArray b vs          =  array b (zipWith (\ a b -> (a,b)) (range b) vs)
 150
 151 (!)                     :: Ix a => Array a b -> a -> b
 152 (Array bounds arr) ! i  = primIndexArray arr (index bounds i)
 153
 154 bounds                  :: Ix a => Array a b -> (a,a)
 155 bounds (Array b _)      =  b
 156
 157 indices           :: Ix a => Array a b -> [a]
 158 indices           = range . bounds
 159
 160 elems             :: Ix a => Array a b -> [b]
 161 elems a           =  [a!i | i <- indices a]
 162
 163 assocs            :: Ix a => Array a b -> [(a,b)]
 164 assocs a          =  [(i, a!i) | i <- indices a]
 165
 166 (//)              :: Ix a => Array a b -> [(a,b)] -> Array a b
 167 a // us           =  array (bounds a)
 168                         ([(i,a!i) | i <- indices a \\ [i | (i,_) <- us]]
 169                          ++ us)
 170
 171 accum             :: Ix a => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
 172 accum f           =  foldl (\a (i,v) -> a // [(i,f (a!i) v)])
 173
 174 accumArray        :: Ix a => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
 175 accumArray f z b  =  accum f (array b [(i,z) | i <- range b])
 176
 177 ixmap             :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c
 178 ixmap b f a       =  array b [(i, a ! f i) | i <- range b]
 179
 180
 181 instance (Ix a) => Functor (Array a) where
 182     fmap f a = array (bounds a) [(i, f(a!i)) | i <- indices a]
 183
 184 instance (Ix a, Eq b) => Eq (Array a b) where
 185     a == a'   =   assocs a == assocs a'
 186
 187 instance (Ix a, Ord b) => Ord (Array a b) where
 188     a <= a'   =   assocs a <= assocs a'
 189
 190
 191 instance  (Ix a, Show a, Show b) => Show (Array a b)  where
 192     showsPrec p a = showParen (p > 9) (
 193                     showString "array " .
 194                     shows (bounds a) . showChar ' ' .
 195                     shows (assocs a)                  )
 196
 197 instance  (Ix a, Read a, Read b) => Read (Array a b)  where
 198     readsPrec p = readParen (p > 9)
 199              (\r -> [(array b as, u) | ("array",s) <- lex r,
 200                                        (b,t)       <- reads s,
 201                                        (as,u)      <- reads t   ])
 202
 203 \end{code}
 204 #endif