[project @ 2001-06-28 14:15:04 by simonmar]
[haskell-directory.git] / 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__ */