ghc/lib/std/Array.lhs

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