Movatterモバイル変換

{-# LANGUAGE Unsafe #-}{-# LANGUAGE NoImplicitPrelude, MagicHash, UnboxedTuples, RoleAnnotations #-}{-# LANGUAGE BangPatterns #-}{-# OPTIONS_HADDOCK hide #-}------------------------------------------------------------------------------- |-- Module      :  GHC.Arr-- Copyright   :  (c) The University of Glasgow, 1994-2000-- License     :  see libraries/base/LICENSE---- Maintainer  :  cvs-ghc@haskell.org-- Stability   :  internal-- Portability :  non-portable (GHC extensions)---- GHC\'s array implementation.-------------------------------------------------------------------------------moduleGHC.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,foldlElems,foldlElems',foldl1Elems,foldrElems,foldrElems',foldr1Elems,-- * Unsafe operationsfill,done,unsafeArray,unsafeArray',lessSafeIndex,unsafeAt,unsafeReplace,unsafeAccumArray,unsafeAccumArray',unsafeAccum,unsafeReadSTArray,unsafeWriteSTArray,unsafeFreezeSTArray,unsafeThawSTArray,)whereimportGHC.EnumimportGHC.NumimportGHC.STimportGHC.BaseimportGHC.ListimportGHC.Real(fromIntegral)importGHC.Showinfixl9!,//default()-- | The 'Ix' class is used to map a contiguous subrange of values in-- a type onto integers.  It is used primarily for array indexing-- (see the array package).---- The first argument @(l,u)@ of each of these operations is a pair-- specifying the lower and upper bounds of a contiguous subrange of values.---- An implementation is entitled to assume the following laws about these-- operations:---- * @'inRange' (l,u) i == 'elem' i ('range' (l,u))@ @ @---- * @'range' (l,u) '!!' 'index' (l,u) i == i@, when @'inRange' (l,u) i@---- * @'map' ('index' (l,u)) ('range' (l,u))) == [0..'rangeSize' (l,u)-1]@ @ @---- * @'rangeSize' (l,u) == 'length' ('range' (l,u))@ @ @--class(Orda)=>Ixawhere{-# MINIMALrange,(index|unsafeIndex),inRange#-}-- | The list of values in the subrange defined by a bounding pair.range::(a,a)->[a]-- | The position of a subscript in the subrange.index::(a,a)->a->Int-- | Like 'index', but without checking that the value is in range.unsafeIndex::(a,a)->a->Int-- | Returns 'True' the given subscript lies in the range defined-- the bounding pair.inRange::(a,a)->a->Bool-- | The size of the subrange defined by a bounding pair.rangeSize::(a,a)->Int-- | like 'rangeSize', but without checking that the upper bound is-- in range.unsafeRangeSize::(a,a)->Int-- Must specify one of index, unsafeIndex-- 'index' is typically over-ridden in instances, with essentially-- the same code, but using indexError instead of hopelessIndexError-- Reason: we have 'Show' at the instances{-# INLINEindex#-}-- See Note [Inlining index]indexbi|inRangebi=unsafeIndexbi|otherwise=hopelessIndexErrorunsafeIndexbi=indexbirangeSizeb@(_l,h)|inRangebh=unsafeIndexbh+1|otherwise=0-- This case is only here to-- check for an empty range-- NB: replacing (inRange b h) by (l <= h) fails for--     tuples.  E.g.  (1,2) <= (2,1) but the range is emptyunsafeRangeSizeb@(_l,h)=unsafeIndexbh+1{-Note that the following is NOT right        rangeSize (l,h) | l <= h    = index b h + 1                        | otherwise = 0Because it might be the case that l<h, but the rangeis nevertheless empty.  Consider        ((1,2),(2,1))Here l<h, but the second index ranges from 2..1 andhence is emptyNote [Inlining index]~~~~~~~~~~~~~~~~~~~~~We inline the 'index' operation, * Partly because it generates much faster code   (although bigger); see Trac #1216 * Partly because it exposes the bounds checks to the simplifier which   might help a big.If you make a per-instance index method, you may consider inlining it.Note [Double bounds-checking of index values]~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~When you index an array, a!x, there are two possible bounds checks we might make:  (A) Check that (inRange (bounds a) x) holds.      (A) is checked in the method for 'index'  (B) Check that (index (bounds a) x) lies in the range 0..n,      where n is the size of the underlying array      (B) is checked in the top-level function (!), in safeIndex.Of course it *should* be the case that (A) holds iff (B) holds, but thatis a property of the particular instances of index, bounds, and inRange,so GHC cannot guarantee it. * If you do (A) and not (B), then you might get a seg-fault,   by indexing at some bizarre location.  Trac #1610 * If you do (B) but not (A), you may get no complaint when you index   an array out of its semantic bounds.  Trac #2120At various times we have had (A) and not (B), or (B) and not (A); bothled to complaints.  So now we implement *both* checks (Trac #2669).For 1-d, 2-d, and 3-d arrays of Int we have specialised instances to avoid this.Note [Out-of-bounds error messages]~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~The default method for 'index' generates hoplelessIndexError, becauseIx doesn't have Show as a superclass.  For particular base types wecan do better, so we override the default method for index.-}-- Abstract these errors from the relevant index functions so that-- the guts of the function will be small enough to inline.{-# NOINLINEindexError#-}indexError::Showa=>(a,a)->a->String->bindexErrorrngitp=errorWithoutStackTrace(showString"Ix{".showStringtp.showString"}.index: Index ".showParenTrue(showsPrec0i).showString" out of range "$showParenTrue(showsPrec0rng)"")hopelessIndexError::Int-- Try to use 'indexError' instead!hopelessIndexError=errorWithoutStackTrace"Error in array index"------------------------------------------------------------------------ | @since 2.01instanceIxCharwhere{-# INLINErange#-}range(m,n)=[m..n]{-# INLINEunsafeIndex#-}unsafeIndex(m,_n)i=fromEnumi-fromEnumm{-# INLINEindex#-}-- See Note [Out-of-bounds error messages]-- and Note [Inlining index]indexbi|inRangebi=unsafeIndexbi|otherwise=indexErrorbi"Char"inRange(m,n)i=m<=i&&i<=n------------------------------------------------------------------------ | @since 2.01instanceIxIntwhere{-# INLINErange#-}-- The INLINE stops the build in the RHS from getting inlined,-- so that callers can fuse with the result of rangerange(m,n)=[m..n]{-# INLINEunsafeIndex#-}unsafeIndex(m,_n)i=i-m{-# INLINEindex#-}-- See Note [Out-of-bounds error messages]-- and Note [Inlining index]indexbi|inRangebi=unsafeIndexbi|otherwise=indexErrorbi"Int"{-# INLINEinRange#-}inRange(I#m,I#n)(I#i)=isTrue#(m<=#i)&&isTrue#(i<=#n)-- | @since 4.6.0.0instanceIxWordwhererange(m,n)=[m..n]unsafeIndex(m,_)i=fromIntegral(i-m)inRange(m,n)i=m<=i&&i<=n------------------------------------------------------------------------ | @since 2.01instanceIxIntegerwhere{-# INLINErange#-}range(m,n)=[m..n]{-# INLINEunsafeIndex#-}unsafeIndex(m,_n)i=fromInteger(i-m){-# INLINEindex#-}-- See Note [Out-of-bounds error messages]-- and Note [Inlining index]indexbi|inRangebi=unsafeIndexbi|otherwise=indexErrorbi"Integer"inRange(m,n)i=m<=i&&i<=n------------------------------------------------------------------------ | @since 4.8.0.0instanceIxNaturalwhererange(m,n)=[m..n]inRange(m,n)i=m<=i&&i<=nunsafeIndex(m,_)i=fromIntegral(i-m)indexbi|inRangebi=unsafeIndexbi|otherwise=indexErrorbi"Natural"------------------------------------------------------------------------ | @since 2.01instanceIxBoolwhere-- as derived{-# INLINErange#-}range(m,n)=[m..n]{-# INLINEunsafeIndex#-}unsafeIndex(l,_)i=fromEnumi-fromEnuml{-# INLINEindex#-}-- See Note [Out-of-bounds error messages]-- and Note [Inlining index]indexbi|inRangebi=unsafeIndexbi|otherwise=indexErrorbi"Bool"inRange(l,u)i=fromEnumi>=fromEnuml&&fromEnumi<=fromEnumu------------------------------------------------------------------------ | @since 2.01instanceIxOrderingwhere-- as derived{-# INLINErange#-}range(m,n)=[m..n]{-# INLINEunsafeIndex#-}unsafeIndex(l,_)i=fromEnumi-fromEnuml{-# INLINEindex#-}-- See Note [Out-of-bounds error messages]-- and Note [Inlining index]indexbi|inRangebi=unsafeIndexbi|otherwise=indexErrorbi"Ordering"inRange(l,u)i=fromEnumi>=fromEnuml&&fromEnumi<=fromEnumu------------------------------------------------------------------------ | @since 2.01instanceIx()where{-# INLINErange#-}range((),())=[()]{-# INLINEunsafeIndex#-}unsafeIndex((),())()=0{-# INLINEinRange#-}inRange((),())()=True{-# INLINEindex#-}-- See Note [Inlining index]indexbi=unsafeIndexbi------------------------------------------------------------------------ | @since 2.01instance(Ixa,Ixb)=>Ix(a,b)where-- as derived{-# SPECIALISEinstanceIx(Int,Int)#-}{-# INLINErange#-}range((l1,l2),(u1,u2))=[(i1,i2)|i1<-range(l1,u1),i2<-range(l2,u2)]{-# INLINEunsafeIndex#-}unsafeIndex((l1,l2),(u1,u2))(i1,i2)=unsafeIndex(l1,u1)i1*unsafeRangeSize(l2,u2)+unsafeIndex(l2,u2)i2{-# INLINEinRange#-}inRange((l1,l2),(u1,u2))(i1,i2)=inRange(l1,u1)i1&&inRange(l2,u2)i2-- Default method for index------------------------------------------------------------------------ | @since 2.01instance(Ixa1,Ixa2,Ixa3)=>Ix(a1,a2,a3)where{-# SPECIALISEinstanceIx(Int,Int,Int)#-}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-- Default method for index------------------------------------------------------------------------ | @since 2.01instance(Ixa1,Ixa2,Ixa3,Ixa4)=>Ix(a1,a2,a3,a4)whererange((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-- Default method for index-- | @since 2.01instance(Ixa1,Ixa2,Ixa3,Ixa4,Ixa5)=>Ix(a1,a2,a3,a4,a5)whererange((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-- Default method for index-- | The type of immutable non-strict (boxed) arrays-- with indices in @i@ and elements in @e@.dataArrayie=Array!i-- the lower bound, l!i-- the upper bound, u{-# UNPACK#-}!Int-- A cache of (rangeSize (l,u))-- used to make sure an index is-- really in range(Array#e)-- The actual elements-- | Mutable, boxed, non-strict arrays in the 'ST' monad.  The type-- arguments are as follows:----  * @s@: the state variable argument for the 'ST' type----  * @i@: the index type of the array (should be an instance of 'Ix')----  * @e@: the element type of the array.--dataSTArraysie=STArray!i-- the lower bound, l!i-- the upper bound, u{-# UNPACK#-}!Int-- A cache of (rangeSize (l,u))-- used to make sure an index is-- really in range(MutableArray#se)-- The actual elements-- No Ix context for STArray.  They are stupid,-- and force an Ix context on the equality instance.-- Index types should have nominal role, because of Ix class. See also #9220.typeroleArraynominalrepresentationaltyperoleSTArraynominalnominalrepresentational-- Just pointer equality on mutable arrays:-- | @since 2.01instanceEq(STArraysie)whereSTArray___arr1#==STArray___arr2#=isTrue#(sameMutableArray#arr1#arr2#)------------------------------------------------------------------------ Operations on immutable arrays{-# NOINLINEarrEleBottom#-}arrEleBottom::aarrEleBottom=errorWithoutStackTrace"(Array.!): undefined array element"-- | Construct an array with the specified bounds and containing values-- for given indices within these bounds.---- The array is undefined (i.e. bottom) if any index in the list is-- out of bounds.  The Haskell 2010 Report further specifies that if any-- two associations in the list have the same index, the value at that-- index is undefined (i.e. bottom).  However in GHC's implementation,-- the value at such an index is the value part of the last association-- with that index in the list.---- Because the indices must be checked for these errors, 'array' is-- strict in the bounds argument and in the indices of the association-- list, but non-strict in the values.  Thus, recurrences such as the-- following are possible:---- > a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])---- Not every index within the bounds of the array need appear in the-- association list, but the values associated with indices that do not-- appear will be undefined (i.e. bottom).---- If, in any dimension, the lower bound is greater than the upper bound,-- then the array is legal, but empty.  Indexing an empty array always-- gives an array-bounds error, but 'bounds' still yields the bounds-- with which the array was constructed.{-# INLINEarray#-}array::Ixi=>(i,i)-- ^ a pair of /bounds/, each of the index type-- of the array.  These bounds are the lowest and-- highest indices in the array, in that order.-- For example, a one-origin vector of length-- '10' has bounds '(1,10)', and a one-origin '10'-- by '10' matrix has bounds '((1,1),(10,10))'.->[(i,e)]-- ^ a list of /associations/ of the form-- (/index/, /value/).  Typically, this list will-- be expressed as a comprehension.  An-- association '(i, x)' defines the value of-- the array at index 'i' to be 'x'.->Arrayiearray(l,u)ies=letn=safeRangeSize(l,u)inunsafeArray'(l,u)n[(safeIndex(l,u)ni,e)|(i,e)<-ies]{-# INLINEunsafeArray#-}unsafeArray::Ixi=>(i,i)->[(Int,e)]->ArrayieunsafeArraybies=unsafeArray'b(rangeSizeb)ies{-# INLINEunsafeArray'#-}unsafeArray'::(i,i)->Int->[(Int,e)]->ArrayieunsafeArray'(l,u)n@(I#n#)ies=runST(ST$\s1#->casenewArray#n#arrEleBottoms1#of(#s2#,marr##)->foldr(fillmarr#)(donelunmarr#)iess2#){-# INLINEfill#-}fill::MutableArray#se->(Int,e)->STRepsa->STRepsa-- NB: put the \s after the "=" so that 'fill'--     inlines when applied to three argsfillmarr#(I#i#,e)next=\s1#->casewriteArray#marr#i#es1#ofs2#->nexts2#{-# INLINEdone#-}done::i->i->Int->MutableArray#se->STReps(Arrayie)-- See NB on 'fill'-- Make sure it is strict in 'n'donelun@(I#_)marr#=\s1#->caseunsafeFreezeArray#marr#s1#of(#s2#,arr##)->(#s2#,Arraylunarr##)-- | Construct an array from a pair of bounds and a list of values in-- index order.{-# INLINElistArray#-}listArray::Ixi=>(i,i)->[e]->ArrayielistArray(l,u)es=runST(ST$\s1#->casesafeRangeSize(l,u)of{n@(I#n#)->casenewArray#n#arrEleBottoms1#of{(#s2#,marr##)->letgoyr=\i#s3#->casewriteArray#marr#i#ys3#ofs4#->if(isTrue#(i#==#n#-#1#))thens4#elser(i#+#1#)s4#indonelunmarr#(ifn==0thens2#elsefoldrgo(\_s#->s#)es0#s2#)}})-- | The value at the given index in an array.{-# INLINE(!)#-}(!)::Ixi=>Arrayie->i->e(!)arr@(Arraylun_)i=unsafeAtarr$safeIndex(l,u)ni{-# INLINE(!#)#-}(!#)::Ixi=>Arrayie->i->(#e#)(!#)arr@(Arraylun_)i=unsafeAt#arr$safeIndex(l,u)ni{-# INLINEsafeRangeSize#-}safeRangeSize::Ixi=>(i,i)->IntsafeRangeSize(l,u)=letr=rangeSize(l,u)inifr<0thennegRangeelser-- Don't inline this error message everywhere!!negRange::Int-- Uninformative, but Ix does not provide ShownegRange=errorWithoutStackTrace"Negative range size"{-# INLINE[1]safeIndex#-}-- See Note [Double bounds-checking of index values]-- Inline *after* (!) so the rules can fire-- Make sure it is strict in nsafeIndex::Ixi=>(i,i)->Int->i->IntsafeIndex(l,u)n@(I#_)i|(0<=i')&&(i'<n)=i'|otherwise=badSafeIndexi'nwherei'=index(l,u)i-- See Note [Double bounds-checking of index values]{-# RULES"safeIndex/I"safeIndex=lessSafeIndex::(Int,Int)->Int->Int->Int"safeIndex/(I,I)"safeIndex=lessSafeIndex::((Int,Int),(Int,Int))->Int->(Int,Int)->Int"safeIndex/(I,I,I)"safeIndex=lessSafeIndex::((Int,Int,Int),(Int,Int,Int))->Int->(Int,Int,Int)->Int#-}lessSafeIndex::Ixi=>(i,i)->Int->i->Int-- See Note [Double bounds-checking of index values]-- Do only (A), the semantic checklessSafeIndex(l,u)_i=index(l,u)i-- Don't inline this long error message everywhere!!badSafeIndex::Int->Int->IntbadSafeIndexi'n=errorWithoutStackTrace("Error in array index; "++showi'++" not in range [0.."++shown++")"){-# INLINEunsafeAt#-}unsafeAt::Arrayie->Int->eunsafeAt(Array___arr#)(I#i#)=caseindexArray#arr#i#of(#e#)->e-- | Look up an element in an array without forcing itunsafeAt#::Arrayie->Int->(#e#)unsafeAt#(Array___arr#)(I#i#)=indexArray#arr#i#-- | A convenient version of unsafeAt#unsafeAtA::Applicativef=>Arrayie->Int->feunsafeAtAaryi=caseunsafeAt#aryiof(#e#)->puree-- | The bounds with which an array was constructed.{-# INLINEbounds#-}bounds::Arrayie->(i,i)bounds(Arraylu__)=(l,u)-- | The number of elements in the array.{-# INLINEnumElements#-}numElements::Arrayie->IntnumElements(Array__n_)=n-- | The list of indices of an array in ascending order.{-# INLINEindices#-}indices::Ixi=>Arrayie->[i]indices(Arraylu__)=range(l,u)-- | The list of elements of an array in index order.{-# INLINEelems#-}elems::Arrayie->[e]elemsarr@(Array__n_)=[e|i<-[0..n-1],e<-unsafeAtAarri]-- | A right fold over the elements{-# INLINABLEfoldrElems#-}foldrElems::(a->b->b)->b->Arrayia->bfoldrElemsfb0=\arr@(Array__n_)->letgoi|i==n=b0|(#e#)<-unsafeAt#arri=fe(go(i+1))ingo0-- | A left fold over the elements{-# INLINABLEfoldlElems#-}foldlElems::(b->a->b)->b->Arrayia->bfoldlElemsfb0=\arr@(Array__n_)->letgoi|i==(-1)=b0|(#e#)<-unsafeAt#arri=f(go(i-1))eingo(n-1)-- | A strict right fold over the elements{-# INLINABLEfoldrElems'#-}foldrElems'::(a->b->b)->b->Arrayia->bfoldrElems'fb0=\arr@(Array__n_)->letgoia|i==(-1)=a|(#e#)<-unsafeAt#arri=go(i-1)(fe$!a)ingo(n-1)b0-- | A strict left fold over the elements{-# INLINABLEfoldlElems'#-}foldlElems'::(b->a->b)->b->Arrayia->bfoldlElems'fb0=\arr@(Array__n_)->letgoia|i==n=a|(#e#)<-unsafeAt#arri=go(i+1)(a`seq`fae)ingo0b0-- | A left fold over the elements with no starting value{-# INLINABLEfoldl1Elems#-}foldl1Elems::(a->a->a)->Arrayia->afoldl1Elemsf=\arr@(Array__n_)->letgoi|i==0=unsafeAtarr0|(#e#)<-unsafeAt#arri=f(go(i-1))einifn==0thenerrorWithoutStackTrace"foldl1: empty Array"elsego(n-1)-- | A right fold over the elements with no starting value{-# INLINABLEfoldr1Elems#-}foldr1Elems::(a->a->a)->Arrayia->afoldr1Elemsf=\arr@(Array__n_)->letgoi|i==n-1=unsafeAtarri|(#e#)<-unsafeAt#arri=fe(go(i+1))inifn==0thenerrorWithoutStackTrace"foldr1: empty Array"elsego0-- | The list of associations of an array in index order.{-# INLINEassocs#-}assocs::Ixi=>Arrayie->[(i,e)]assocsarr@(Arraylu__)=[(i,e)|i<-range(l,u),let!(#e#)=arr!#i]-- | The 'accumArray' function deals with repeated indices in the association-- list using an /accumulating function/ which combines the values of-- associations with the same index.---- For example, given a list of values of some index type, @hist@-- produces a histogram of the number of occurrences of each index within-- a specified range:---- > hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b-- > hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]---- @accumArray@ is strict in each result of applying the accumulating-- function, although it is lazy in the initial value. Thus, unlike-- arrays built with 'array', accumulated arrays should not in general-- be recursive.{-# INLINEaccumArray#-}accumArray::Ixi=>(e->a->e)-- ^ accumulating function->e-- ^ initial value->(i,i)-- ^ bounds of the array->[(i,a)]-- ^ association list->ArrayieaccumArrayfinitial(l,u)ies=letn=safeRangeSize(l,u)inunsafeAccumArray'finitial(l,u)n[(safeIndex(l,u)ni,e)|(i,e)<-ies]{-# INLINEunsafeAccumArray#-}unsafeAccumArray::Ixi=>(e->a->e)->e->(i,i)->[(Int,a)]->ArrayieunsafeAccumArrayfinitialbies=unsafeAccumArray'finitialb(rangeSizeb)ies{-# INLINEunsafeAccumArray'#-}unsafeAccumArray'::(e->a->e)->e->(i,i)->Int->[(Int,a)]->ArrayieunsafeAccumArray'finitial(l,u)n@(I#n#)ies=runST(ST$\s1#->casenewArray#n#initials1#of{(#s2#,marr##)->foldr(adjust'fmarr#)(donelunmarr#)iess2#}){-# INLINEadjust#-}adjust::(e->a->e)->MutableArray#se->(Int,a)->STRepsb->STRepsb-- See NB on 'fill'adjustfmarr#(I#i#,new)next=\s1#->casereadArray#marr#i#s1#of(#s2#,old#)->casewriteArray#marr#i#(foldnew)s2#ofs3#->nexts3#{-# INLINEadjust'#-}adjust'::(e->a->e)->MutableArray#se->(Int,a)->STRepsb->STRepsbadjust'fmarr#(I#i#,new)next=\s1#->casereadArray#marr#i#s1#of(#s2#,old#)->let!combined=foldnewinnext(writeArray#marr#i#combineds2#)-- | Constructs an array identical to the first argument except that it has-- been updated by the associations in the right argument.-- For example, if @m@ is a 1-origin, @n@ by @n@ matrix, then---- > m//[((i,i), 0) | i <- [1..n]]---- is the same matrix, except with the diagonal zeroed.---- Repeated indices in the association list are handled as for 'array':-- Haskell 2010 specifies that the resulting array is undefined (i.e. bottom),-- but GHC's implementation uses the last association for each index.{-# INLINE(//)#-}(//)::Ixi=>Arrayie->[(i,e)]->Arrayiearr@(Arraylun_)//ies=unsafeReplacearr[(safeIndex(l,u)ni,e)|(i,e)<-ies]{-# INLINEunsafeReplace#-}unsafeReplace::Arrayie->[(Int,e)]->ArrayieunsafeReplacearries=runST(doSTArraylunmarr#<-thawSTArrayarrST(foldr(fillmarr#)(donelunmarr#)ies))-- | @'accum' f@ takes an array and an association list and accumulates-- pairs from the list into the array with the accumulating function @f@.-- Thus 'accumArray' can be defined using 'accum':---- > accumArray f z b = accum f (array b [(i, z) | i <- range b])---- @accum@ is strict in all the results of applying the accumulation.-- However, it is lazy in the initial values of the array.{-# INLINEaccum#-}accum::Ixi=>(e->a->e)->Arrayie->[(i,a)]->Arrayieaccumfarr@(Arraylun_)ies=unsafeAccumfarr[(safeIndex(l,u)ni,e)|(i,e)<-ies]{-# INLINEunsafeAccum#-}unsafeAccum::(e->a->e)->Arrayie->[(Int,a)]->ArrayieunsafeAccumfarries=runST(doSTArraylunmarr#<-thawSTArrayarrST(foldr(adjust'fmarr#)(donelunmarr#)ies)){-# INLINE[1]amap#-}-- See Note [amap]amap::(a->b)->Arrayia->Arrayibamapfarr@(Arraylun@(I#n#)_)=runST(ST$\s1#->casenewArray#n#arrEleBottoms1#of(#s2#,marr##)->letgois#|i==n=donelunmarr#s#|(#e#)<-unsafeAt#arri=fillmarr#(i,fe)(go(i+1))s#ingo0s2#){- Note [amap]~~~~~~~~~~~~~~amap was originally defined like this: amap f arr@(Array l u n _) =     unsafeArray' (l,u) n [(i, f (unsafeAt arr i)) | i <- [0 .. n - 1]]There are two problems:1. The enumFromTo implementation produces (spurious) code for the impossible   case of n<0 that ends up duplicating the array freezing code.2. This implementation relies on list fusion for efficiency. In order   to implement the "amap/coerce" rule, we need to delay inlining amap   until simplifier phase 1, which is when the eftIntList rule kicks   in and makes that impossible.  (c.f. Trac #8767)-}-- See Breitner, Eisenberg, Peyton Jones, and Weirich, "Safe Zero-cost-- Coercions for Haskell", section 6.5:--   http://research.microsoft.com/en-us/um/people/simonpj/papers/ext-f/coercible.pdf{-# RULES"amap/coerce"amapcoerce=coerce-- See Note [amap]#-}-- Second functor law:{-# RULES"amap/amap"forallfga.amapf(amapga)=amap(f.g)a#-}-- | 'ixmap' allows for transformations on array indices.-- It may be thought of as providing function composition on the right-- with the mapping that the original array embodies.---- A similar transformation of array values may be achieved using 'fmap'-- from the 'Array' instance of the 'Functor' class.{-# INLINEixmap#-}ixmap::(Ixi,Ixj)=>(i,i)->(i->j)->Arrayje->Arrayieixmap(l,u)farr=array(l,u)[(i,arr!fi)|i<-range(l,u)]{-# INLINEeqArray#-}eqArray::(Ixi,Eqe)=>Arrayie->Arrayie->BooleqArrayarr1@(Arrayl1u1n1_)arr2@(Arrayl2u2n2_)=ifn1==0thenn2==0elsel1==l2&&u1==u2&&and[unsafeAtarr1i==unsafeAtarr2i|i<-[0..n1-1]]{-# INLINE[1]cmpArray#-}cmpArray::(Ixi,Orde)=>Arrayie->Arrayie->OrderingcmpArrayarr1arr2=compare(assocsarr1)(assocsarr2){-# INLINEcmpIntArray#-}cmpIntArray::Orde=>ArrayInte->ArrayInte->OrderingcmpIntArrayarr1@(Arrayl1u1n1_)arr2@(Arrayl2u2n2_)=ifn1==0thenifn2==0thenEQelseLTelseifn2==0thenGTelsecasecomparel1l2ofEQ->foldrcmp(compareu1u2)[0..(n1`min`n2)-1]other->otherwherecmpirest=casecompare(unsafeAtarr1i)(unsafeAtarr2i)ofEQ->restother->other{-# RULES"cmpArray/Int"cmpArray=cmpIntArray#-}------------------------------------------------------------------------ Array instances-- | @since 2.01instanceFunctor(Arrayi)wherefmap=amap-- | @since 2.01instance(Ixi,Eqe)=>Eq(Arrayie)where(==)=eqArray-- | @since 2.01instance(Ixi,Orde)=>Ord(Arrayie)wherecompare=cmpArray-- | @since 2.01instance(Ixa,Showa,Showb)=>Show(Arrayab)whereshowsPrecpa=showParen(p>appPrec)$showString"array ".showsPrecappPrec1(boundsa).showChar' '.showsPrecappPrec1(assocsa)-- Precedence of 'array' is the precedence of application-- The Read instance is in GHC.Read------------------------------------------------------------------------ Operations on mutable arrays{-Idle ADR question: What's the tradeoff here between flattening thesedatatypes into @STArray ix ix (MutableArray# s elt)@ and usingit as is?  As I see it, the former uses slightly less heap andprovides faster access to the individual parts of the bounds while thecode used has the benefit of providing a ready-made @(lo, hi)@ pair asrequired by many array-related functions.  Which wins? Is thedifference significant (probably not).Idle AJG answer: When I looked at the outputted code (though it was 2years ago) it seems like you often needed the tuple, and we buildit frequently. Now we've got the overloading specialiser thingsmight be different, though.-}{-# INLINEnewSTArray#-}newSTArray::Ixi=>(i,i)->e->STs(STArraysie)newSTArray(l,u)initial=ST$\s1#->casesafeRangeSize(l,u)of{n@(I#n#)->casenewArray#n#initials1#of{(#s2#,marr##)->(#s2#,STArraylunmarr##)}}{-# INLINEboundsSTArray#-}boundsSTArray::STArraysie->(i,i)boundsSTArray(STArraylu__)=(l,u){-# INLINEnumElementsSTArray#-}numElementsSTArray::STArraysie->IntnumElementsSTArray(STArray__n_)=n{-# INLINEreadSTArray#-}readSTArray::Ixi=>STArraysie->i->STsereadSTArraymarr@(STArraylun_)i=unsafeReadSTArraymarr(safeIndex(l,u)ni){-# INLINEunsafeReadSTArray#-}unsafeReadSTArray::STArraysie->Int->STseunsafeReadSTArray(STArray___marr#)(I#i#)=ST$\s1#->readArray#marr#i#s1#{-# INLINEwriteSTArray#-}writeSTArray::Ixi=>STArraysie->i->e->STs()writeSTArraymarr@(STArraylun_)ie=unsafeWriteSTArraymarr(safeIndex(l,u)ni)e{-# INLINEunsafeWriteSTArray#-}unsafeWriteSTArray::STArraysie->Int->e->STs()unsafeWriteSTArray(STArray___marr#)(I#i#)e=ST$\s1#->casewriteArray#marr#i#es1#ofs2#->(#s2#,()#)------------------------------------------------------------------------ Moving between mutable and immutablefreezeSTArray::STArraysie->STs(Arrayie)freezeSTArray(STArraylun@(I#n#)marr#)=ST$\s1#->casenewArray#n#arrEleBottoms1#of{(#s2#,marr'##)->letcopyi#s3#|isTrue#(i#==#n#)=s3#|otherwise=casereadArray#marr#i#s3#of{(#s4#,e#)->casewriteArray#marr'#i#es4#of{s5#->copy(i#+#1#)s5#}}incasecopy0#s2#of{s3#->caseunsafeFreezeArray#marr'#s3#of{(#s4#,arr##)->(#s4#,Arraylunarr##)}}}{-# INLINEunsafeFreezeSTArray#-}unsafeFreezeSTArray::STArraysie->STs(Arrayie)unsafeFreezeSTArray(STArraylunmarr#)=ST$\s1#->caseunsafeFreezeArray#marr#s1#of{(#s2#,arr##)->(#s2#,Arraylunarr##)}thawSTArray::Arrayie->STs(STArraysie)thawSTArray(Arraylun@(I#n#)arr#)=ST$\s1#->casenewArray#n#arrEleBottoms1#of{(#s2#,marr##)->letcopyi#s3#|isTrue#(i#==#n#)=s3#|otherwise=caseindexArray#arr#i#of{(#e#)->casewriteArray#marr#i#es3#of{s4#->copy(i#+#1#)s4#}}incasecopy0#s2#of{s3#->(#s3#,STArraylunmarr##)}}{-# INLINEunsafeThawSTArray#-}unsafeThawSTArray::Arrayie->STs(STArraysie)unsafeThawSTArray(Arraylunarr#)=ST$\s1#->caseunsafeThawArray#arr#s1#of{(#s2#,marr##)->(#s2#,STArraylunmarr##)}