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