Data/Array.hs

   1 {-# OPTIONS -fno-implicit-prelude #-}
   2 -----------------------------------------------------------------------------
   3 -- |
   4 -- Module      :  Data.Array
   5 -- Copyright   :  (c) The University of Glasgow 2001
   6 -- License     :  BSD-style (see the file libraries/core/LICENSE)
   7 --
   8 -- Maintainer  :  libraries@haskell.org
   9 -- Stability   :  provisional
  10 -- Portability :  portable
  11 --
  12 -- Basic non-strict arrays.
  13 --
  14 -----------------------------------------------------------------------------
  15
  16 module  Data.Array
  17
  18     (
  19       module Data.Ix            -- export all of Ix
  20     , Array                     -- Array type is abstract
  21
  22     , array         -- :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
  23     , listArray     -- :: (Ix a) => (a,a) -> [b] -> Array a b
  24     , (!)           -- :: (Ix a) => Array a b -> a -> b
  25     , bounds        -- :: (Ix a) => Array a b -> (a,a)
  26     , indices       -- :: (Ix a) => Array a b -> [a]
  27     , elems         -- :: (Ix a) => Array a b -> [b]
  28     , assocs        -- :: (Ix a) => Array a b -> [(a,b)]
  29     , accumArray    -- :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
  30     , (//)          -- :: (Ix a) => Array a b -> [(a,b)] -> Array a b
  31     , accum         -- :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
  32     , ixmap         -- :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a b
  33
  34     -- Array instances:
  35     --
  36     --   Ix a => Functor (Array a)
  37     --   (Ix a, Eq b)  => Eq   (Array a b)
  38     --   (Ix a, Ord b) => Ord  (Array a b)
  39     --   (Ix a, Show a, Show b) => Show (Array a b)
  40     --   (Ix a, Read a, Read b) => Read (Array a b)
  41     --
  42
  43     -- Implementation checked wrt. Haskell 98 lib report, 1/99.
  44
  45     ) where
  46
  47 import Data.Dynamic
  48
  49 #ifdef __GLASGOW_HASKELL__
  50 import Data.Ix
  51 import GHC.Arr          -- Most of the hard work is done here
  52 import GHC.Err          ( undefined )
  53 #endif
  54
  55 #include "Dynamic.h"
  56 INSTANCE_TYPEABLE2(Array,arrayTc,"Array")
  57
  58 #ifdef __HUGS__
  59         ------------ HUGS (rest of file) --------------------
  60 import PrelPrim ( PrimArray
  61                 , runST
  62                 , primNewArray
  63                 , primWriteArray
  64                 , primReadArray
  65                 , primUnsafeFreezeArray
  66                 , primIndexArray
  67                 )
  68 import Ix
  69 import List( (\\) )
  70
  71 infixl 9  !, //
  72
  73 -- -----------------------------------------------------------------------------
  74 -- The Array type
  75
  76 data Array ix elt = Array (ix,ix) (PrimArray elt)
  77
  78 array :: Ix a => (a,a) -> [(a,b)] -> Array a b
  79 array ixs@(ix_start, ix_end) ivs = runST (do
  80   { mut_arr <- primNewArray (rangeSize ixs) arrEleBottom
  81   ; mapM_ (\ (i,v) -> primWriteArray mut_arr (index ixs i) v) ivs
  82   ; arr <- primUnsafeFreezeArray mut_arr
  83   ; return (Array ixs arr)
  84   }
  85   )
  86  where
  87   arrEleBottom = error "(Array.!): undefined array element"
  88
  89 listArray               :: Ix a => (a,a) -> [b] -> Array a b
  90 listArray b vs          =  array b (zipWith (\ a b -> (a,b)) (range b) vs)
  91
  92 (!)                     :: Ix a => Array a b -> a -> b
  93 (Array bounds arr) ! i  = primIndexArray arr (index bounds i)
  94
  95 bounds                  :: Ix a => Array a b -> (a,a)
  96 bounds (Array b _)      =  b
  97
  98 indices           :: Ix a => Array a b -> [a]
  99 indices           = range . bounds
 100
 101 elems             :: Ix a => Array a b -> [b]
 102 elems a           =  [a!i | i <- indices a]
 103
 104 assocs            :: Ix a => Array a b -> [(a,b)]
 105 assocs a          =  [(i, a!i) | i <- indices a]
 106
 107 (//)              :: Ix a => Array a b -> [(a,b)] -> Array a b
 108 (//) a us           =  array (bounds a)
 109                         ([(i,a!i) | i <- indices a \\ [i | (i,_) <- us]]
 110                          ++ us)
 111
 112 accum             :: Ix a => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
 113 accum f           =  foldl (\a (i,v) -> a // [(i,f (a!i) v)])
 114
 115 accumArray        :: Ix a => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
 116 accumArray f z b  =  accum f (array b [(i,z) | i <- range b])
 117
 118 ixmap             :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c
 119 ixmap b f a       =  array b [(i, a ! f i) | i <- range b]
 120
 121
 122 instance (Ix a) => Functor (Array a) where
 123     fmap f a = array (bounds a) [(i, f(a!i)) | i <- indices a]
 124
 125 instance (Ix a, Eq b) => Eq (Array a b) where
 126     a == a'   =   assocs a == assocs a'
 127
 128 instance (Ix a, Ord b) => Ord (Array a b) where
 129     a <= a'   =   assocs a <= assocs a'
 130
 131
 132 instance  (Ix a, Show a, Show b) => Show (Array a b)  where
 133     showsPrec p a = showParen (p > 9) (
 134                     showString "array " .
 135                     shows (bounds a) . showChar ' ' .
 136                     shows (assocs a)                  )
 137
 138 instance  (Ix a, Read a, Read b) => Read (Array a b)  where
 139     readsPrec p = readParen (p > 9)
 140              (\r -> [(array b as, u) | ("array",s) <- lex r,
 141                                        (b,t)       <- reads s,
 142                                        (as,u)      <- reads t   ])
 143 #endif /* __HUGS__ */