-{-# OPTIONS -fno-implicit-prelude #-}
+{-# OPTIONS_GHC -fno-implicit-prelude #-}
-----------------------------------------------------------------------------
-- |
-- Module : Data.Array
-- Copyright : (c) The University of Glasgow 2001
--- License : BSD-style (see the file libraries/core/LICENSE)
+-- License : BSD-style (see the file libraries/base/LICENSE)
--
-- Maintainer : libraries@haskell.org
-- Stability : provisional
--
-- Basic non-strict arrays.
--
+-- /Note:/ The "Data.Array.IArray" module provides more general interface
+-- to immutable arrays: it defines operations with the same names as
+-- those defined below, but with more general types, and also defines
+-- 'Array' instances of the relevant classes. To use that more general
+-- interface, import "Data.Array.IArray" but not "Data.Array".
-----------------------------------------------------------------------------
module Data.Array
(
+ -- * Immutable non-strict arrays
+ -- $intro
module Data.Ix -- export all of Ix
, Array -- Array type is abstract
+ -- * Array construction
, array -- :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
, listArray -- :: (Ix a) => (a,a) -> [b] -> Array a b
+ , accumArray -- :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
+ -- * Accessing arrays
, (!) -- :: (Ix a) => Array a b -> a -> b
, bounds -- :: (Ix a) => Array a b -> (a,a)
, indices -- :: (Ix a) => Array a b -> [a]
, elems -- :: (Ix a) => Array a b -> [b]
, assocs -- :: (Ix a) => Array a b -> [(a,b)]
- , accumArray -- :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
+ -- * Incremental array updates
, (//) -- :: (Ix a) => Array a b -> [(a,b)] -> Array a b
, accum -- :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
+ -- * Derived arrays
, ixmap -- :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a b
-- Array instances:
) where
-import Data.Dynamic
+import Data.Ix
#ifdef __GLASGOW_HASKELL__
-import Data.Ix
-import GHC.Arr -- Most of the hard work is done here
-import GHC.Err ( undefined )
+import GHC.Arr -- Most of the hard work is done here
+import Data.Generics.Basics -- To provide a Data instance
+import Data.Generics.Instances -- To provide a Data instance
+import GHC.Err ( error ) -- Needed for Data instance
#endif
-#include "Dynamic.h"
-INSTANCE_TYPEABLE2(Array,arrayTc,"Array")
-
#ifdef __HUGS__
- ------------ HUGS (rest of file) --------------------
-import PrelPrim ( PrimArray
- , runST
- , primNewArray
- , primWriteArray
- , primReadArray
- , primUnsafeFreezeArray
- , primIndexArray
- )
-import Ix
-import List( (\\) )
-
-infixl 9 !, //
-
--- -----------------------------------------------------------------------------
--- The Array type
-
-data Array ix elt = Array (ix,ix) (PrimArray elt)
-
-array :: Ix a => (a,a) -> [(a,b)] -> Array a b
-array ixs@(ix_start, ix_end) ivs = runST (do
- { mut_arr <- primNewArray (rangeSize ixs) arrEleBottom
- ; mapM_ (\ (i,v) -> primWriteArray mut_arr (index ixs i) v) ivs
- ; arr <- primUnsafeFreezeArray mut_arr
- ; return (Array ixs arr)
- }
- )
- where
- arrEleBottom = error "(Array.!): undefined array element"
-
-listArray :: Ix a => (a,a) -> [b] -> Array a b
-listArray b vs = array b (zipWith (\ a b -> (a,b)) (range b) vs)
-
-(!) :: Ix a => Array a b -> a -> b
-(Array bounds arr) ! i = primIndexArray arr (index bounds i)
-
-bounds :: Ix a => Array a b -> (a,a)
-bounds (Array b _) = b
-
-indices :: Ix a => Array a b -> [a]
-indices = range . bounds
-
-elems :: Ix a => Array a b -> [b]
-elems a = [a!i | i <- indices a]
-
-assocs :: Ix a => Array a b -> [(a,b)]
-assocs a = [(i, a!i) | i <- indices a]
-
-(//) :: Ix a => Array a b -> [(a,b)] -> Array a b
-(//) a us = array (bounds a)
- ([(i,a!i) | i <- indices a \\ [i | (i,_) <- us]]
- ++ us)
-
-accum :: Ix a => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
-accum f = foldl (\a (i,v) -> a // [(i,f (a!i) v)])
-
-accumArray :: Ix a => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
-accumArray f z b = accum f (array b [(i,z) | i <- range b])
-
-ixmap :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c
-ixmap b f a = array b [(i, a ! f i) | i <- range b]
+import Hugs.Array
+#endif
+#ifdef __NHC__
+import Array -- Haskell'98 arrays
+#endif
-instance (Ix a) => Functor (Array a) where
- fmap f a = array (bounds a) [(i, f(a!i)) | i <- indices a]
+import Data.Typeable
+#include "Typeable.h"
+INSTANCE_TYPEABLE2(Array,arrayTc,"Array")
-instance (Ix a, Eq b) => Eq (Array a b) where
- a == a' = assocs a == assocs a'
+#ifdef __GLASGOW_HASKELL__
-instance (Ix a, Ord b) => Ord (Array a b) where
- a <= a' = assocs a <= assocs a'
+-- This instance preserves data abstraction at the cost of inefficiency.
+-- We omit reflection services for the sake of data abstraction.
+instance (Typeable a, Data b, Ix a) => Data (Array a b)
+ where
+ gfoldl f z a = z (listArray (bounds a)) `f` (elems a)
+ toConstr _ = error "toConstr"
+ gunfold _ _ = error "gunfold"
+ dataTypeOf _ = mkNorepType "Data.Array.Array"
-instance (Ix a, Show a, Show b) => Show (Array a b) where
- showsPrec p a = showParen (p > 9) (
- showString "array " .
- shows (bounds a) . showChar ' ' .
- shows (assocs a) )
+#endif
-instance (Ix a, Read a, Read b) => Read (Array a b) where
- readsPrec p = readParen (p > 9)
- (\r -> [(array b as, u) | ("array",s) <- lex r,
- (b,t) <- reads s,
- (as,u) <- reads t ])
-#endif /* __HUGS__ */
+{- $intro
+Haskell provides indexable /arrays/, which may be thought of as functions
+whose domains are isomorphic to contiguous subsets of the integers.
+Functions restricted in this way can be implemented efficiently;
+in particular, a programmer may reasonably expect rapid access to
+the components. To ensure the possibility of such an implementation,
+arrays are treated as data, not as general functions.
+
+Since most array functions involve the class 'Ix', this module is exported
+from "Data.Array" so that modules need not import both "Data.Array" and
+"Data.Ix".
+-}