[project @ 2002-05-09 13:16:29 by simonmar]
[packages/random.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/base/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__ */