X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=Data%2FArray.hs;h=263f9707c669dafb9cf62060e7dfb8650db68d65;hb=e9e2a5412bb7cda8d13a063ac403d9f18ac97380;hp=aadfdfb8a0d874ee2027a80393ec54900a108ce3;hpb=9fa9bc17072a58c0bae2cce4764d38677e96ac29;p=ghc-base.git diff --git a/Data/Array.hs b/Data/Array.hs index aadfdfb..263f970 100644 --- a/Data/Array.hs +++ b/Data/Array.hs @@ -1,36 +1,45 @@ -{-# 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 -- Portability : portable -- --- $Id: Array.hs,v 1.2 2002/04/24 16:31:39 simonmar Exp $ --- -- 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: @@ -46,100 +55,50 @@ module Data.Array ) 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". +-}