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
  67 {-# SPECIALISE listArray :: (Int,Int) -> [b] -> Array Int b #-}
  68 listArray             :: (Ix a) => (a,a) -> [b] -> Array a b
  69 listArray b vs        =  array b (zip (range b) vs)
  70
  71 {-# INLINE elems #-}
  72 elems                 :: (Ix a) => Array a b -> [b]
  73 elems a               =  [a!i | i <- indices a]
  74
  75 ixmap                 :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c
  76 ixmap b f a           =  array b [(i, a ! f i) | i <- range b]
  77 \end{code}
  78
  79
  80 %*********************************************************
  81 %*                                                      *
  82 \subsection{Instance declarations for Array type}
  83 %*                                                      *
  84 %*********************************************************
  85
  86
  87 #else
  88 \begin{code}
  89 data Array ix elt = Array (ix,ix) (PrimArray elt)
  90
  91 array :: Ix a => (a,a) -> [(a,b)] -> Array a b
  92 array ixs@(ix_start, ix_end) ivs = primRunST (do
  93   { mut_arr <- primNewArray (rangeSize ixs) arrEleBottom
  94   ; mapM_ (\ (i,v) -> primWriteArray mut_arr (index ixs i) v) ivs
  95   ; arr <- primUnsafeFreezeArray mut_arr
  96   ; return (Array ixs arr)
  97   }
  98   )
  99  where
 100   arrEleBottom = error "(Array.!): undefined array element"
 101
 102 listArray               :: Ix a => (a,a) -> [b] -> Array a b
 103 listArray b vs          =  array b (zipWith (\ a b -> (a,b)) (range b) vs)
 104
 105 (!)                     :: Ix a => Array a b -> a -> b
 106 (Array bounds arr) ! i  = primIndexArray arr (index bounds i)
 107
 108 bounds                  :: Ix a => Array a b -> (a,a)
 109 bounds (Array b _)      =  b
 110
 111 indices           :: Ix a => Array a b -> [a]
 112 indices           = range . bounds
 113
 114 elems             :: Ix a => Array a b -> [b]
 115 elems a           =  [a!i | i <- indices a]
 116
 117 assocs            :: Ix a => Array a b -> [(a,b)]
 118 assocs a          =  [(i, a!i) | i <- indices a]
 119
 120 (//)              :: Ix a => Array a b -> [(a,b)] -> Array a b
 121 a // us           =  array (bounds a)
 122                         ([(i,a!i) | i <- indices a \\ [i | (i,_) <- us]]
 123                          ++ us)
 124
 125 accum             :: Ix a => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
 126 accum f           =  foldl (\a (i,v) -> a // [(i,f (a!i) v)])
 127
 128 accumArray        :: Ix a => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
 129 accumArray f z b  =  accum f (array b [(i,z) | i <- range b])
 130
 131 ixmap             :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c
 132 ixmap b f a       =  array b [(i, a ! f i) | i <- range b]
 133
 134
 135 instance (Ix a) => Functor (Array a) where
 136     fmap f a = array (bounds a) [(i, f(a!i)) | i <- indices a]
 137
 138 instance (Ix a, Eq b) => Eq (Array a b) where
 139     a == a'   =   assocs a == assocs a'
 140
 141 instance (Ix a, Ord b) => Ord (Array a b) where
 142     a <= a'   =   assocs a <= assocs a'
 143
 144
 145 instance  (Ix a, Show a, Show b) => Show (Array a b)  where
 146     showsPrec p a = showParen (p > 9) (
 147                     showString "array " .
 148                     shows (bounds a) . showChar ' ' .
 149                     shows (assocs a)                  )
 150
 151 instance  (Ix a, Read a, Read b) => Read (Array a b)  where
 152     readsPrec p = readParen (p > 9)
 153              (\r -> [(array b as, u) | ("array",s) <- lex r,
 154                                        (b,t)       <- reads s,
 155                                        (as,u)      <- reads t   ])
 156
 157 \end{code}
 158 #endif