module GHC.Arr (
Ix(..), Array(..), STArray(..),
indexError, hopelessIndexError,
arrEleBottom, array, listArray,
(!), safeRangeSize, negRange, safeIndex, badSafeIndex,
bounds, numElements, numElementsSTArray, indices, elems,
assocs, accumArray, adjust, (//), accum,
amap, ixmap,
eqArray, cmpArray, cmpIntArray,
newSTArray, boundsSTArray,
readSTArray, writeSTArray,
freezeSTArray, thawSTArray,
fill, done,
unsafeArray, unsafeArray',
lessSafeIndex, unsafeAt, unsafeReplace,
unsafeAccumArray, unsafeAccumArray', unsafeAccum,
unsafeReadSTArray, unsafeWriteSTArray,
unsafeFreezeSTArray, unsafeThawSTArray,
) where
import GHC.Enum
import GHC.Num
import GHC.ST
import GHC.Base
import GHC.List
import GHC.Show
infixl 9 !, //
default ()
\end{code} %********************************************************* %* * \subsection{The @Ix@ class} %* * %********************************************************* \begin{code}
class (Ord a) => Ix a where
range :: (a,a) -> [a]
index :: (a,a) -> a -> Int
unsafeIndex :: (a,a) -> a -> Int
inRange :: (a,a) -> a -> Bool
rangeSize :: (a,a) -> Int
unsafeRangeSize :: (a,a) -> Int
index b i | inRange b i = unsafeIndex b i
| otherwise = hopelessIndexError
unsafeIndex b i = index b i
rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
| otherwise = 0
unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
\end{code} Note that the following is NOT right rangeSize (l,h) | l <= h = index b h + 1 | otherwise = 0 Because it might be the case that l indexError :: Show a => ( a , a ) -> a -> String -> b indexError rng i tp = error ( showString "Ix{" . showString tp . showString "}.index: Index " . showParen True ( showsPrec 0 i ) . showString " out of range " $ showParen True ( showsPrec 0 rng ) "" ) hopelessIndexError :: Int hopelessIndexError = error "Error in array index" instance Ix Char where range ( m , n ) = [ m .. n ] unsafeIndex ( m , _n ) i = fromEnum i fromEnum m index b i | inRange b i = unsafeIndex b i | otherwise = indexError b i "Char" inRange ( m , n ) i = m <= i && i <= n instance Ix Int where range ( m , n ) = [ m .. n ] unsafeIndex ( m , _n ) i = i m index b i | inRange b i = unsafeIndex b i | otherwise = indexError b i "Int" inRange ( I # m , I # n ) ( I # i ) = m <=# i && i <=# n instance Ix Integer where range ( m , n ) = [ m .. n ] unsafeIndex ( m , _n ) i = fromInteger ( i m ) index b i | inRange b i = unsafeIndex b i | otherwise = indexError b i "Integer" inRange ( m , n ) i = m <= i && i <= n instance Ix Bool where range ( m , n ) = [ m .. n ] unsafeIndex ( l , _ ) i = fromEnum i fromEnum l index b i | inRange b i = unsafeIndex b i | otherwise = indexError b i "Bool" inRange ( l , u ) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u instance Ix Ordering where range ( m , n ) = [ m .. n ] unsafeIndex ( l , _ ) i = fromEnum i fromEnum l index b i | inRange b i = unsafeIndex b i | otherwise = indexError b i "Ordering" inRange ( l , u ) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u instance Ix () where range ( () , () ) = [ () ] unsafeIndex ( () , () ) () = 0 inRange ( () , () ) () = True index b i = unsafeIndex b i instance ( Ix a , Ix b ) => Ix ( a , b ) where range ( ( l1 , l2 ) , ( u1 , u2 ) ) = [ ( i1 , i2 ) | i1 <- range ( l1 , u1 ) , i2 <- range ( l2 , u2 ) ] unsafeIndex ( ( l1 , l2 ) , ( u1 , u2 ) ) ( i1 , i2 ) = unsafeIndex ( l1 , u1 ) i1 * unsafeRangeSize ( l2 , u2 ) + unsafeIndex ( l2 , u2 ) i2 inRange ( ( l1 , l2 ) , ( u1 , u2 ) ) ( i1 , i2 ) = inRange ( l1 , u1 ) i1 && inRange ( l2 , u2 ) i2 instance ( Ix a1 , Ix a2 , Ix a3 ) => Ix ( a1 , a2 , a3 ) where range ( ( l1 , l2 , l3 ) , ( u1 , u2 , u3 ) ) = [ ( i1 , i2 , i3 ) | i1 <- range ( l1 , u1 ) , i2 <- range ( l2 , u2 ) , i3 <- range ( l3 , u3 ) ] unsafeIndex ( ( l1 , l2 , l3 ) , ( u1 , u2 , u3 ) ) ( i1 , i2 , i3 ) = unsafeIndex ( l3 , u3 ) i3 + unsafeRangeSize ( l3 , u3 ) * ( unsafeIndex ( l2 , u2 ) i2 + unsafeRangeSize ( l2 , u2 ) * ( unsafeIndex ( l1 , u1 ) i1 ) ) inRange ( ( l1 , l2 , l3 ) , ( u1 , u2 , u3 ) ) ( i1 , i2 , i3 ) = inRange ( l1 , u1 ) i1 && inRange ( l2 , u2 ) i2 && inRange ( l3 , u3 ) i3 instance ( Ix a1 , Ix a2 , Ix a3 , Ix a4 ) => Ix ( a1 , a2 , a3 , a4 ) where range ( ( l1 , l2 , l3 , l4 ) , ( u1 , u2 , u3 , u4 ) ) = [ ( i1 , i2 , i3 , i4 ) | i1 <- range ( l1 , u1 ) , i2 <- range ( l2 , u2 ) , i3 <- range ( l3 , u3 ) , i4 <- range ( l4 , u4 ) ] unsafeIndex ( ( l1 , l2 , l3 , l4 ) , ( u1 , u2 , u3 , u4 ) ) ( i1 , i2 , i3 , i4 ) = unsafeIndex ( l4 , u4 ) i4 + unsafeRangeSize ( l4 , u4 ) * ( unsafeIndex ( l3 , u3 ) i3 + unsafeRangeSize ( l3 , u3 ) * ( unsafeIndex ( l2 , u2 ) i2 + unsafeRangeSize ( l2 , u2 ) * ( unsafeIndex ( l1 , u1 ) i1 ) ) ) inRange ( ( l1 , l2 , l3 , l4 ) , ( u1 , u2 , u3 , u4 ) ) ( i1 , i2 , i3 , i4 ) = inRange ( l1 , u1 ) i1 && inRange ( l2 , u2 ) i2 && inRange ( l3 , u3 ) i3 && inRange ( l4 , u4 ) i4 instance ( Ix a1 , Ix a2 , Ix a3 , Ix a4 , Ix a5 ) => Ix ( a1 , a2 , a3 , a4 , a5 ) where range ( ( l1 , l2 , l3 , l4 , l5 ) , ( u1 , u2 , u3 , u4 , u5 ) ) = [ ( i1 , i2 , i3 , i4 , i5 ) | i1 <- range ( l1 , u1 ) , i2 <- range ( l2 , u2 ) , i3 <- range ( l3 , u3 ) , i4 <- range ( l4 , u4 ) , i5 <- range ( l5 , u5 ) ] unsafeIndex ( ( l1 , l2 , l3 , l4 , l5 ) , ( u1 , u2 , u3 , u4 , u5 ) ) ( i1 , i2 , i3 , i4 , i5 ) = unsafeIndex ( l5 , u5 ) i5 + unsafeRangeSize ( l5 , u5 ) * ( unsafeIndex ( l4 , u4 ) i4 + unsafeRangeSize ( l4 , u4 ) * ( unsafeIndex ( l3 , u3 ) i3 + unsafeRangeSize ( l3 , u3 ) * ( unsafeIndex ( l2 , u2 ) i2 + unsafeRangeSize ( l2 , u2 ) * ( unsafeIndex ( l1 , u1 ) i1 ) ) ) ) inRange ( ( l1 , l2 , l3 , l4 , l5 ) , ( u1 , u2 , u3 , u4 , u5 ) ) ( i1 , i2 , i3 , i4 , i5 ) = inRange ( l1 , u1 ) i1 && inRange ( l2 , u2 ) i2 && inRange ( l3 , u3 ) i3 && inRange ( l4 , u4 ) i4 && inRange ( l5 , u5 ) i5 \end{code} %********************************************************* %* * \subsection{The @Array@ types} %* * %********************************************************* \begin{code}
data Array i e
= Array !i
!i
!Int
(Array# e)
data STArray s i e
= STArray !i
!i
!Int
(MutableArray# s e)
instance Eq (STArray s i e) where
STArray _ _ _ arr1# == STArray _ _ _ arr2# =
sameMutableArray# arr1# arr2#
\end{code} %********************************************************* %* * \subsection{Operations on immutable arrays} %* * %********************************************************* \begin{code}
arrEleBottom :: a
arrEleBottom = error "(Array.!): undefined array element"
array :: Ix i
=> (i,i)
-> [(i, e)]
-> Array i e
array (l,u) ies
= let n = safeRangeSize (l,u)
in unsafeArray' (l,u) n
[(safeIndex (l,u) n i, e) | (i, e) <- ies]
unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
unsafeArray b ies = unsafeArray' b (rangeSize b) ies
unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
case newArray# n# arrEleBottom s1# of
(# s2#, marr# #) ->
foldr (fill marr#) (done l u n marr#) ies s2#)
fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
fill marr# (I# i#, e) next
= \s1# -> case writeArray# marr# i# e s1# of
s2# -> next s2#
done :: Ix i => i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
done l u n marr#
= \s1# -> case unsafeFreezeArray# marr# s1# of
(# s2#, arr# #) -> (# s2#, Array l u n arr# #)
listArray :: Ix i => (i,i) -> [e] -> Array i e
listArray (l,u) es = runST (ST $ \s1# ->
case safeRangeSize (l,u) of { n@(I# n#) ->
case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) ->
let fillFromList i# xs s3# | i# ==# n# = s3#
| otherwise = case xs of
[] -> s3#
y:ys -> case writeArray# marr# i# y s3# of { s4# ->
fillFromList (i# +# 1#) ys s4# } in
case fillFromList 0# es s2# of { s3# ->
done l u n marr# s3# }}})
(!) :: Ix i => Array i e -> i -> e
arr@(Array l u n _) ! i = unsafeAt arr $ safeIndex (l,u) n i
safeRangeSize :: Ix i => (i, i) -> Int
safeRangeSize (l,u) = let r = rangeSize (l, u)
in if r < 0 then negRange
else r
negRange :: Int
negRange = error "Negative range size"
safeIndex :: Ix i => (i, i) -> Int -> i -> Int
safeIndex (l,u) n i = let i' = index (l,u) i
in if (0 <= i') && (i' < n)
then i'
else badSafeIndex i' n
lessSafeIndex :: Ix i => (i, i) -> Int -> i -> Int
lessSafeIndex (l,u) _ i = index (l,u) i
badSafeIndex :: Int -> Int -> Int
badSafeIndex i' n = error ("Error in array index; " ++ show i' ++
" not in range [0.." ++ show n ++ ")")
unsafeAt :: Ix i => Array i e -> Int -> e
unsafeAt (Array _ _ _ arr#) (I# i#) =
case indexArray# arr# i# of (# e #) -> e
bounds :: Ix i => Array i e -> (i,i)
bounds (Array l u _ _) = (l,u)
numElements :: Ix i => Array i e -> Int
numElements (Array _ _ n _) = n
indices :: Ix i => Array i e -> [i]
indices (Array l u _ _) = range (l,u)
elems :: Ix i => Array i e -> [e]
elems arr@(Array _ _ n _) =
[unsafeAt arr i | i <- [0 .. n 1]]
assocs :: Ix i => Array i e -> [(i, e)]
assocs arr@(Array l u _ _) =
[(i, arr ! i) | i <- range (l,u)]
accumArray :: Ix i
=> (e -> a -> e)
-> e
-> (i,i)
-> [(i, a)]
-> Array i e
accumArray f initial (l,u) ies =
let n = safeRangeSize (l,u)
in unsafeAccumArray' f initial (l,u) n
[(safeIndex (l,u) n i, e) | (i, e) <- ies]
unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
unsafeAccumArray f initial b ies = unsafeAccumArray' f initial b (rangeSize b) ies
unsafeAccumArray' :: Ix i => (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e
unsafeAccumArray' f initial (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
case newArray# n# initial s1# of { (# s2#, marr# #) ->
foldr (adjust f marr#) (done l u n marr#) ies s2# })
adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
adjust f marr# (I# i#, new) next
= \s1# -> case readArray# marr# i# s1# of
(# s2#, old #) ->
case writeArray# marr# i# (f old new) s2# of
s3# -> next s3#
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
arr@(Array l u n _) // ies =
unsafeReplace arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e
unsafeReplace arr ies = runST (do
STArray l u n marr# <- thawSTArray arr
ST (foldr (fill marr#) (done l u n marr#) ies))
accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
accum f arr@(Array l u n _) ies =
unsafeAccum f arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
unsafeAccum f arr ies = runST (do
STArray l u n marr# <- thawSTArray arr
ST (foldr (adjust f marr#) (done l u n marr#) ies))
amap :: Ix i => (a -> b) -> Array i a -> Array i b
amap f arr@(Array l u n _) =
unsafeArray' (l,u) n [(i, f (unsafeAt arr i)) | i <- [0 .. n 1]]
ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
ixmap (l,u) f arr =
array (l,u) [(i, arr ! f i) | i <- range (l,u)]
eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
eqArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
if n1 == 0 then n2 == 0 else
l1 == l2 && u1 == u2 &&
and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. n1 1]]
cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
cmpIntArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
if n1 == 0 then
if n2 == 0 then EQ else LT
else if n2 == 0 then GT
else case compare l1 l2 of
EQ -> foldr cmp (compare u1 u2) [0 .. (n1 `min` n2) 1]
other -> other
where
cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
EQ -> rest
other -> other
\end{code} %********************************************************* %* * \subsection{Array instances} %* * %********************************************************* \begin{code}
instance Ix i => Functor (Array i) where
fmap = amap
instance (Ix i, Eq e) => Eq (Array i e) where
(==) = eqArray
instance (Ix i, Ord e) => Ord (Array i e) where
compare = cmpArray
instance (Ix a, Show a, Show b) => Show (Array a b) where
showsPrec p a =
showParen (p > appPrec) $
showString "array " .
showsPrec appPrec1 (bounds a) .
showChar ' ' .
showsPrec appPrec1 (assocs a)
\end{code} %********************************************************* %* * \subsection{Operations on mutable arrays} %* * %********************************************************* Idle ADR question: What's the tradeoff here between flattening these datatypes into @STArray ix ix (MutableArray# s elt)@ and using it as is? As I see it, the former uses slightly less heap and provides faster access to the individual parts of the bounds while the code used has the benefit of providing a ready-made @(lo, hi)@ pair as required by many array-related functions. Which wins? Is the difference significant (probably not). Idle AJG answer: When I looked at the outputted code (though it was 2 years ago) it seems like you often needed the tuple, and we build it frequently. Now we've got the overloading specialiser things might be different, though. \begin{code}
newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
newSTArray (l,u) initial = ST $ \s1# ->
case safeRangeSize (l,u) of { n@(I# n#) ->
case newArray# n# initial s1# of { (# s2#, marr# #) ->
(# s2#, STArray l u n marr# #) }}
boundsSTArray :: STArray s i e -> (i,i)
boundsSTArray (STArray l u _ _) = (l,u)
numElementsSTArray :: STArray s i e -> Int
numElementsSTArray (STArray _ _ n _) = n
readSTArray :: Ix i => STArray s i e -> i -> ST s e
readSTArray marr@(STArray l u n _) i =
unsafeReadSTArray marr (safeIndex (l,u) n i)
unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e
unsafeReadSTArray (STArray _ _ _ marr#) (I# i#)
= ST $ \s1# -> readArray# marr# i# s1#
writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
writeSTArray marr@(STArray l u n _) i e =
unsafeWriteSTArray marr (safeIndex (l,u) n i) e
unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s ()
unsafeWriteSTArray (STArray _ _ _ marr#) (I# i#) e = ST $ \s1# ->
case writeArray# marr# i# e s1# of
s2# -> (# s2#, () #)
\end{code} %********************************************************* %* * \subsection{Moving between mutable and immutable} %* * %********************************************************* \begin{code}
freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
freezeSTArray (STArray l u n@(I# n#) marr#) = ST $ \s1# ->
case newArray# n# arrEleBottom s1# of { (# s2#, marr'# #) ->
let copy i# s3# | i# ==# n# = s3#
| otherwise =
case readArray# marr# i# s3# of { (# s4#, e #) ->
case writeArray# marr'# i# e s4# of { s5# ->
copy (i# +# 1#) s5# }} in
case copy 0# s2# of { s3# ->
case unsafeFreezeArray# marr'# s3# of { (# s4#, arr# #) ->
(# s4#, Array l u n arr# #) }}}
unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
unsafeFreezeSTArray (STArray l u n marr#) = ST $ \s1# ->
case unsafeFreezeArray# marr# s1# of { (# s2#, arr# #) ->
(# s2#, Array l u n arr# #) }
thawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
thawSTArray (Array l u n@(I# n#) arr#) = ST $ \s1# ->
case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) ->
let copy i# s3# | i# ==# n# = s3#
| otherwise =
case indexArray# arr# i# of { (# e #) ->
case writeArray# marr# i# e s3# of { s4# ->
copy (i# +# 1#) s4# }} in
case copy 0# s2# of { s3# ->
(# s3#, STArray l u n marr# #) }}
unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
unsafeThawSTArray (Array l u n arr#) = ST $ \s1# ->
case unsafeThawArray# arr# s1# of { (# s2#, marr# #) ->
(# s2#, STArray l u n marr# #) }
\end{code}
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4