1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
{-# OPTIONS -fno-implicit-prelude #-}
-----------------------------------------------------------------------------
-- |
-- Module : Data.Array
-- Copyright : (c) The University of Glasgow 2001
-- License : BSD-style (see the file libraries/base/LICENSE)
--
-- Maintainer : libraries@haskell.org
-- Stability : provisional
-- Portability : portable
--
-- Basic non-strict arrays.
--
-----------------------------------------------------------------------------
module Data.Array
(
module Data.Ix -- export all of Ix
, Array -- Array type is abstract
, array -- :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
, listArray -- :: (Ix a) => (a,a) -> [b] -> Array a b
, (!) -- :: (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
, (//) -- :: (Ix a) => Array a b -> [(a,b)] -> Array a b
, accum -- :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
, ixmap -- :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a b
-- Array instances:
--
-- Ix a => Functor (Array a)
-- (Ix a, Eq b) => Eq (Array a b)
-- (Ix a, Ord b) => Ord (Array a b)
-- (Ix a, Show a, Show b) => Show (Array a b)
-- (Ix a, Read a, Read b) => Read (Array a b)
--
-- Implementation checked wrt. Haskell 98 lib report, 1/99.
) where
import Data.Dynamic
#ifdef __GLASGOW_HASKELL__
import Data.Ix
import GHC.Arr -- Most of the hard work is done here
import GHC.Err ( undefined )
#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]
instance (Ix a) => Functor (Array a) where
fmap f a = array (bounds a) [(i, f(a!i)) | i <- indices a]
instance (Ix a, Eq b) => Eq (Array a b) where
a == a' = assocs a == assocs a'
instance (Ix a, Ord b) => Ord (Array a b) where
a <= a' = assocs a <= assocs a'
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) )
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__ */
|
