    {-# LANGUAGE BangPatterns          #-}
    {-# LANGUAGE CPP                   #-}
    {-# LANGUAGE MagicHash             #-}
    {-# LANGUAGE Rank2Types            #-}
    {-# LANGUAGE ScopedTypeVariables   #-}
    {-# LANGUAGE TemplateHaskellQuotes #-}
    {-# LANGUAGE UnboxedTuples         #-}
    {-# OPTIONS_GHC -fno-full-laziness -funbox-strict-fields #-}
    {-# OPTIONS_HADDOCK not-home #-}

    -- | = WARNING
    --
    -- This module is considered __internal__.
    --
    -- The Package Versioning Policy __does not apply__.
    --
    -- The contents of this module may change __in any way whatsoever__
    -- and __without any warning__ between minor versions of this package.
    --
    -- Authors importing this module are expected to track development
    -- closely.
    --
    -- = Description
    --
    -- Zero based arrays.
    --
    -- Note that no bounds checking are performed.
    module Data.HashMap.Internal.Array
        ( Array(..)
        , MArray(..)

          -- * Creation
        , new
        , new_
        , singleton
        , singletonM
        , snoc
        , pair

          -- * Basic interface
        , length
        , lengthM
        , read
        , write
        , index
        , indexM
        , index#
        , update
        , updateWith'
        , unsafeUpdateM
        , insert
        , insertM
        , delete
        , sameArray1

        , unsafeFreeze
        , unsafeThaw
        , unsafeSameArray
        , run
        , copy
        , copyM
        , cloneM

          -- * Folds
        , foldl
        , foldl'
        , foldr
        , foldr'
        , foldMap
        , all

        , thaw
        , map
        , map'
        , traverse
        , traverse'
        , toList
        , fromList
        , fromList'
        , shrink
        ) where

    import Control.Applicative (liftA2)
    import Control.DeepSeq     (NFData (..), NFData1 (..))
    import Control.Monad       ((>=>))
    import Control.Monad.ST    (runST, stToIO)
    import GHC.Exts            (Int (..), SmallArray#, SmallMutableArray#,
                                cloneSmallMutableArray#, copySmallArray#,
                                copySmallMutableArray#, indexSmallArray#,
                                newSmallArray#, readSmallArray#,
                                reallyUnsafePtrEquality#, sizeofSmallArray#,
                                sizeofSmallMutableArray#, tagToEnum#,
                                thawSmallArray#, unsafeCoerce#,
                                unsafeFreezeSmallArray#, unsafeThawSmallArray#,
                                writeSmallArray#)
    import GHC.ST              (ST (..))
    import Prelude             hiding (Foldable(..), all, filter,
                                map, read, traverse)

    import qualified GHC.Exts                   as Exts
    import qualified Language.Haskell.TH.Syntax as TH
    #if defined(ASSERTS)
    import qualified Prelude
    #endif

    #if defined(ASSERTS)
    -- This fugly hack is brought by GHC's apparent reluctance to deal
    -- with MagicHash and UnboxedTuples when inferring types. Eek!
    # define CHECK_BOUNDS(_func_,_len_,_k_) \
    if (_k_) < 0 || (_k_) >= (_len_) then error ("Data.HashMap.Internal.Array." ++ (_func_) ++ ": bounds error, offset " ++ show (_k_) ++ ", length " ++ show (_len_)) else
    # define CHECK_OP(_func_,_op_,_lhs_,_rhs_) \
    if not ((_lhs_) _op_ (_rhs_)) then error ("Data.HashMap.Internal.Array." ++ (_func_) ++ ": Check failed: _lhs_ _op_ _rhs_ (" ++ show (_lhs_) ++ " vs. " ++ show (_rhs_) ++ ")") else
    # define CHECK_GT(_func_,_lhs_,_rhs_) CHECK_OP(_func_,>,_lhs_,_rhs_)
    # define CHECK_LE(_func_,_lhs_,_rhs_) CHECK_OP(_func_,<=,_lhs_,_rhs_)
    # define CHECK_EQ(_func_,_lhs_,_rhs_) CHECK_OP(_func_,==,_lhs_,_rhs_)
    #else
    # define CHECK_BOUNDS(_func_,_len_,_k_)
    # define CHECK_OP(_func_,_op_,_lhs_,_rhs_)
    # define CHECK_GT(_func_,_lhs_,_rhs_)
    # define CHECK_LE(_func_,_lhs_,_rhs_)
    # define CHECK_EQ(_func_,_lhs_,_rhs_)
    #endif

    data Array a = Array {
          forall a. Array a -> SmallArray# a
    unArray :: !(SmallArray# a)
        }

    instance Show a => Show (Array a) where
        show :: Array a -> String
    show = [a] -> String
    forall a. Show a => a -> String
    show ([a] -> String) -> (Array a -> [a]) -> Array a -> String
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Array a -> [a]
    forall a. Array a -> [a]
    toList

    -- Determines whether two arrays have the same memory address.
    -- This is more reliable than testing pointer equality on the
    -- Array wrappers, but it's still slightly bogus.
    unsafeSameArray :: Array a -> Array b -> Bool
    unsafeSameArray :: forall a b. Array a -> Array b -> Bool
    unsafeSameArray (Array SmallArray# a
    xs) (Array SmallArray# b
    ys) =
      Int# -> Bool
    forall a. Int# -> a
    tagToEnum# ((ZonkAny 0 -> ZonkAny 1 -> Int#)
    -> SmallArray# a -> SmallArray# b -> Int#
    forall a b. a -> b
    unsafeCoerce# ZonkAny 0 -> ZonkAny 1 -> Int#
    forall a b. a -> b -> Int#
    reallyUnsafePtrEquality# SmallArray# a
    xs SmallArray# b
    ys)

    sameArray1 :: (a -> b -> Bool) -> Array a -> Array b -> Bool
    sameArray1 :: forall a b. (a -> b -> Bool) -> Array a -> Array b -> Bool
    sameArray1 a -> b -> Bool
    eq !Array a
    xs0 !Array b
    ys0
      | Int
    lenxs Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    /= Int
    lenys = Bool
    False
      | Bool
    otherwise = Int -> Array a -> Array b -> Bool
    go Int
    0 Array a
    xs0 Array b
    ys0
      where
        go :: Int -> Array a -> Array b -> Bool
    go !Int
    k !Array a
    xs !Array b
    ys
          | Int
    k Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    lenxs = Bool
    True
          | (# a
    x #) <- Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    xs Int
    k
          , (# b
    y #) <- Array b -> Int -> (# b #)
    forall a. Array a -> Int -> (# a #)
    index# Array b
    ys Int
    k
          = a -> b -> Bool
    eq a
    x b
    y Bool -> Bool -> Bool
    && Int -> Array a -> Array b -> Bool
    go (Int
    k Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) Array a
    xs Array b
    ys

        !lenxs :: Int
    lenxs = Array a -> Int
    forall a. Array a -> Int
    length Array a
    xs0
        !lenys :: Int
    lenys = Array b -> Int
    forall a. Array a -> Int
    length Array b
    ys0

    length :: Array a -> Int
    length :: forall a. Array a -> Int
    length Array a
    ary = Int# -> Int
    I# (SmallArray# a -> Int#
    forall a. SmallArray# a -> Int#
    sizeofSmallArray# (Array a -> SmallArray# a
    forall a. Array a -> SmallArray# a
    unArray Array a
    ary))
    {-# INLINE length #-}

    data MArray s a = MArray {
          forall s a. MArray s a -> SmallMutableArray# s a
    unMArray :: !(SmallMutableArray# s a)
        }

    lengthM :: MArray s a -> Int
    lengthM :: forall s a. MArray s a -> Int
    lengthM MArray s a
    mary = Int# -> Int
    I# (SmallMutableArray# s a -> Int#
    forall d a. SmallMutableArray# d a -> Int#
    sizeofSmallMutableArray# (MArray s a -> SmallMutableArray# s a
    forall s a. MArray s a -> SmallMutableArray# s a
    unMArray MArray s a
    mary))
    {-# INLINE lengthM #-}

    ------------------------------------------------------------------------

    instance NFData a => NFData (Array a) where
        rnf :: Array a -> ()
    rnf = Array a -> ()
    forall a. NFData a => Array a -> ()
    rnfArray

    rnfArray :: NFData a => Array a -> ()
    rnfArray :: forall a. NFData a => Array a -> ()
    rnfArray Array a
    ary0 = Array a -> Int -> Int -> ()
    forall {a}. NFData a => Array a -> Int -> Int -> ()
    go Array a
    ary0 Int
    n0 Int
    0
      where
        n0 :: Int
    n0 = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0
        go :: Array a -> Int -> Int -> ()
    go !Array a
    ary !Int
    n !Int
    i
            | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    n = ()
            | (# a
    x #) <- Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    ary Int
    i
            = a -> ()
    forall a. NFData a => a -> ()
    rnf a
    x () -> () -> ()
    forall a b. a -> b -> b
    `seq` Array a -> Int -> Int -> ()
    go Array a
    ary Int
    n (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    1)
    -- We use index# just in case GHC can't see that the
    -- relevant rnf is strict, or in case it actually isn't.
    {-# INLINE rnfArray #-}

    -- | @since 0.2.14.0
    instance NFData1 Array where
        liftRnf :: forall a. (a -> ()) -> Array a -> ()
    liftRnf = (a -> ()) -> Array a -> ()
    forall a. (a -> ()) -> Array a -> ()
    liftRnfArray

    liftRnfArray :: (a -> ()) -> Array a -> ()
    liftRnfArray :: forall a. (a -> ()) -> Array a -> ()
    liftRnfArray a -> ()
    rnf0 Array a
    ary0 = Array a -> Int -> Int -> ()
    go Array a
    ary0 Int
    n0 Int
    0
      where
        n0 :: Int
    n0 = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0
        go :: Array a -> Int -> Int -> ()
    go !Array a
    ary !Int
    n !Int
    i
            | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    n = ()
            | (# a
    x #) <- Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    ary Int
    i
            = a -> ()
    rnf0 a
    x () -> () -> ()
    forall a b. a -> b -> b
    `seq` Array a -> Int -> Int -> ()
    go Array a
    ary Int
    n (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    1)
    {-# INLINE liftRnfArray #-}

    -- | Create a new mutable array of specified size, in the specified
    -- state thread, with each element containing the specified initial
    -- value.
    new :: Int -> a -> ST s (MArray s a)
    new :: forall a s. Int -> a -> ST s (MArray s a)
    new _n :: Int
    _n@(I# Int#
    n#) a
    b =
        CHECK_GT("new",_n,(0 :: Int))
        STRep s (MArray s a) -> ST s (MArray s a)
    forall s a. STRep s a -> ST s a
    ST (STRep s (MArray s a) -> ST s (MArray s a))
    -> STRep s (MArray s a) -> ST s (MArray s a)
    forall a b. (a -> b) -> a -> b
    $ \State# s
    s ->
            case Int# -> a -> State# s -> (# State# s, SmallMutableArray# s a #)
    forall a d.
    Int# -> a -> State# d -> (# State# d, SmallMutableArray# d a #)
    newSmallArray# Int#
    n# a
    b State# s
    s of
                (# State# s
    s', SmallMutableArray# s a
    ary #) -> (# State# s
    s', SmallMutableArray# s a -> MArray s a
    forall s a. SmallMutableArray# s a -> MArray s a
    MArray SmallMutableArray# s a
    ary #)
    {-# INLINE new #-}

    new_ :: Int -> ST s (MArray s a)
    new_ :: forall s a. Int -> ST s (MArray s a)
    new_ Int
    n = Int -> a -> ST s (MArray s a)
    forall a s. Int -> a -> ST s (MArray s a)
    new Int
    n a
    forall a. a
    undefinedElem

    -- | When 'Exts.shrinkSmallMutableArray#' is available, the returned array is the same as the array given, as it is shrunk in place.
    -- Otherwise a copy is made.
    shrink :: MArray s a -> Int -> ST s (MArray s a)
    #if __GLASGOW_HASKELL__ >= 810
    shrink :: forall s a. MArray s a -> Int -> ST s (MArray s a)
    shrink MArray s a
    mary _n :: Int
    _n@(I# Int#
    n#) =
      CHECK_GT("shrink", _n, (0 :: Int))
      CHECK_LE("shrink", _n, (lengthM mary))
      STRep s (MArray s a) -> ST s (MArray s a)
    forall s a. STRep s a -> ST s a
    ST (STRep s (MArray s a) -> ST s (MArray s a))
    -> STRep s (MArray s a) -> ST s (MArray s a)
    forall a b. (a -> b) -> a -> b
    $ \State# s
    s -> case SmallMutableArray# s a -> Int# -> State# s -> State# s
    forall d a. SmallMutableArray# d a -> Int# -> State# d -> State# d
    Exts.shrinkSmallMutableArray# (MArray s a -> SmallMutableArray# s a
    forall s a. MArray s a -> SmallMutableArray# s a
    unMArray MArray s a
    mary) Int#
    n# State# s
    s of
        State# s
    s' -> (# State# s
    s', MArray s a
    mary #)
    #else
    shrink mary n = cloneM mary 0 n
    #endif
    {-# INLINE shrink #-}

    singleton :: a -> Array a
    singleton :: forall a. a -> Array a
    singleton a
    x = (forall s. ST s (Array a)) -> Array a
    forall a. (forall s. ST s a) -> a
    runST (a -> ST s (Array a)
    forall a s. a -> ST s (Array a)
    singletonM a
    x)
    {-# INLINE singleton #-}

    singletonM :: a -> ST s (Array a)
    singletonM :: forall a s. a -> ST s (Array a)
    singletonM a
    x = Int -> a -> ST s (MArray s a)
    forall a s. Int -> a -> ST s (MArray s a)
    new Int
    1 a
    x ST s (MArray s a)
    -> (MArray s a -> ST s (Array a)) -> ST s (Array a)
    forall a b. ST s a -> (a -> ST s b) -> ST s b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= MArray s a -> ST s (Array a)
    forall s a. MArray s a -> ST s (Array a)
    unsafeFreeze
    {-# INLINE singletonM #-}

    snoc :: Array a -> a -> Array a
    snoc :: forall a. Array a -> a -> Array a
    snoc Array a
    ary a
    x = (forall s. ST s (MArray s a)) -> Array a
    forall e. (forall s. ST s (MArray s e)) -> Array e
    run ((forall s. ST s (MArray s a)) -> Array a)
    -> (forall s. ST s (MArray s a)) -> Array a
    forall a b. (a -> b) -> a -> b
    $ do
      mary <- Int -> a -> ST s (MArray s a)
    forall a s. Int -> a -> ST s (MArray s a)
    new (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) a
    x
      copy ary 0 mary 0 n
      pure mary
      where
        n :: Int
    n = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary
    {-# INLINE snoc #-}

    pair :: a -> a -> Array a
    pair :: forall a. a -> a -> Array a
    pair a
    x a
    y = (forall s. ST s (MArray s a)) -> Array a
    forall e. (forall s. ST s (MArray s e)) -> Array e
    run ((forall s. ST s (MArray s a)) -> Array a)
    -> (forall s. ST s (MArray s a)) -> Array a
    forall a b. (a -> b) -> a -> b
    $ do
        ary <- Int -> a -> ST s (MArray s a)
    forall a s. Int -> a -> ST s (MArray s a)
    new Int
    2 a
    x
        write ary 1 y
        return ary
    {-# INLINE pair #-}

    read :: MArray s a -> Int -> ST s a
    read :: forall s a. MArray s a -> Int -> ST s a
    read MArray s a
    ary _i :: Int
    _i@(I# Int#
    i#) = STRep s a -> ST s a
    forall s a. STRep s a -> ST s a
    ST (STRep s a -> ST s a) -> STRep s a -> ST s a
    forall a b. (a -> b) -> a -> b
    $ \ State# s
    s ->
        CHECK_BOUNDS("read", lengthM ary, _i)
            SmallMutableArray# s a -> Int# -> STRep s a
    forall d a.
    SmallMutableArray# d a -> Int# -> State# d -> (# State# d, a #)
    readSmallArray# (MArray s a -> SmallMutableArray# s a
    forall s a. MArray s a -> SmallMutableArray# s a
    unMArray MArray s a
    ary) Int#
    i# State# s
    s
    {-# INLINE read #-}

    write :: MArray s a -> Int -> a -> ST s ()
    write :: forall s a. MArray s a -> Int -> a -> ST s ()
    write MArray s a
    ary _i :: Int
    _i@(I# Int#
    i#) a
    b = STRep s () -> ST s ()
    forall s a. STRep s a -> ST s a
    ST (STRep s () -> ST s ()) -> STRep s () -> ST s ()
    forall a b. (a -> b) -> a -> b
    $ \ State# s
    s ->
        CHECK_BOUNDS("write", lengthM ary, _i)
            case SmallMutableArray# s a -> Int# -> a -> State# s -> State# s
    forall d a.
    SmallMutableArray# d a -> Int# -> a -> State# d -> State# d
    writeSmallArray# (MArray s a -> SmallMutableArray# s a
    forall s a. MArray s a -> SmallMutableArray# s a
    unMArray MArray s a
    ary) Int#
    i# a
    b State# s
    s of
                State# s
    s' -> (# State# s
    s' , () #)
    {-# INLINE write #-}

    index :: Array a -> Int -> a
    index :: forall a. Array a -> Int -> a
    index Array a
    ary _i :: Int
    _i@(I# Int#
    i#) =
        CHECK_BOUNDS("index", length ary, _i)
            case SmallArray# a -> Int# -> (# a #)
    forall a. SmallArray# a -> Int# -> (# a #)
    indexSmallArray# (Array a -> SmallArray# a
    forall a. Array a -> SmallArray# a
    unArray Array a
    ary) Int#
    i# of (# a
    b #) -> a
    b
    {-# INLINE index #-}

    index# :: Array a -> Int -> (# a #)
    index# :: forall a. Array a -> Int -> (# a #)
    index# Array a
    ary _i :: Int
    _i@(I# Int#
    i#) =
        CHECK_BOUNDS("index#", length ary, _i)
            SmallArray# a -> Int# -> (# a #)
    forall a. SmallArray# a -> Int# -> (# a #)
    indexSmallArray# (Array a -> SmallArray# a
    forall a. Array a -> SmallArray# a
    unArray Array a
    ary) Int#
    i#
    {-# INLINE index# #-}

    indexM :: Array a -> Int -> ST s a
    indexM :: forall a s. Array a -> Int -> ST s a
    indexM Array a
    ary _i :: Int
    _i@(I# Int#
    i#) =
        CHECK_BOUNDS("indexM", length ary, _i)
            case SmallArray# a -> Int# -> (# a #)
    forall a. SmallArray# a -> Int# -> (# a #)
    indexSmallArray# (Array a -> SmallArray# a
    forall a. Array a -> SmallArray# a
    unArray Array a
    ary) Int#
    i# of (# a
    b #) -> a -> ST s a
    forall a. a -> ST s a
    forall (m :: * -> *) a. Monad m => a -> m a
    return a
    b
    {-# INLINE indexM #-}

    unsafeFreeze :: MArray s a -> ST s (Array a)
    unsafeFreeze :: forall s a. MArray s a -> ST s (Array a)
    unsafeFreeze MArray s a
    mary
        = STRep s (Array a) -> ST s (Array a)
    forall s a. STRep s a -> ST s a
    ST (STRep s (Array a) -> ST s (Array a))
    -> STRep s (Array a) -> ST s (Array a)
    forall a b. (a -> b) -> a -> b
    $ \State# s
    s -> case SmallMutableArray# s a -> State# s -> (# State# s, SmallArray# a #)
    forall d a.
    SmallMutableArray# d a -> State# d -> (# State# d, SmallArray# a #)
    unsafeFreezeSmallArray# (MArray s a -> SmallMutableArray# s a
    forall s a. MArray s a -> SmallMutableArray# s a
    unMArray MArray s a
    mary) State# s
    s of
                       (# State# s
    s', SmallArray# a
    ary #) -> (# State# s
    s', SmallArray# a -> Array a
    forall a. SmallArray# a -> Array a
    Array SmallArray# a
    ary #)
    {-# INLINE unsafeFreeze #-}

    unsafeThaw :: Array a -> ST s (MArray s a)
    unsafeThaw :: forall a s. Array a -> ST s (MArray s a)
    unsafeThaw Array a
    ary
        = STRep s (MArray s a) -> ST s (MArray s a)
    forall s a. STRep s a -> ST s a
    ST (STRep s (MArray s a) -> ST s (MArray s a))
    -> STRep s (MArray s a) -> ST s (MArray s a)
    forall a b. (a -> b) -> a -> b
    $ \State# s
    s -> case SmallArray# a -> State# s -> (# State# s, SmallMutableArray# s a #)
    forall a d.
    SmallArray# a -> State# d -> (# State# d, SmallMutableArray# d a #)
    unsafeThawSmallArray# (Array a -> SmallArray# a
    forall a. Array a -> SmallArray# a
    unArray Array a
    ary) State# s
    s of
                       (# State# s
    s', SmallMutableArray# s a
    mary #) -> (# State# s
    s', SmallMutableArray# s a -> MArray s a
    forall s a. SmallMutableArray# s a -> MArray s a
    MArray SmallMutableArray# s a
    mary #)
    {-# INLINE unsafeThaw #-}

    run :: (forall s . ST s (MArray s e)) -> Array e
    run :: forall e. (forall s. ST s (MArray s e)) -> Array e
    run forall s. ST s (MArray s e)
    act = (forall s. ST s (Array e)) -> Array e
    forall a. (forall s. ST s a) -> a
    runST ((forall s. ST s (Array e)) -> Array e)
    -> (forall s. ST s (Array e)) -> Array e
    forall a b. (a -> b) -> a -> b
    $ ST s (MArray s e)
    forall s. ST s (MArray s e)
    act ST s (MArray s e)
    -> (MArray s e -> ST s (Array e)) -> ST s (Array e)
    forall a b. ST s a -> (a -> ST s b) -> ST s b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= MArray s e -> ST s (Array e)
    forall s a. MArray s a -> ST s (Array a)
    unsafeFreeze
    {-# INLINE run #-}

    -- | Unsafely copy the elements of an array. Array bounds are not checked.
    copy :: Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
    copy :: forall e s. Array e -> Int -> MArray s e -> Int -> Int -> ST s ()
    copy !Array e
    src !_sidx :: Int
    _sidx@(I# Int#
    sidx#) !MArray s e
    dst !_didx :: Int
    _didx@(I# Int#
    didx#) _n :: Int
    _n@(I# Int#
    n#) =
        CHECK_LE("copy", _sidx + _n, length src)
        CHECK_LE("copy", _didx + _n, lengthM dst)
            STRep s () -> ST s ()
    forall s a. STRep s a -> ST s a
    ST (STRep s () -> ST s ()) -> STRep s () -> ST s ()
    forall a b. (a -> b) -> a -> b
    $ \ State# s
    s# ->
            case SmallArray# e
    -> Int#
    -> SmallMutableArray# s e
    -> Int#
    -> Int#
    -> State# s
    -> State# s
    forall a d.
    SmallArray# a
    -> Int#
    -> SmallMutableArray# d a
    -> Int#
    -> Int#
    -> State# d
    -> State# d
    copySmallArray# (Array e -> SmallArray# e
    forall a. Array a -> SmallArray# a
    unArray Array e
    src) Int#
    sidx# (MArray s e -> SmallMutableArray# s e
    forall s a. MArray s a -> SmallMutableArray# s a
    unMArray MArray s e
    dst) Int#
    didx# Int#
    n# State# s
    s# of
                State# s
    s2 -> (# State# s
    s2, () #)

    -- | Unsafely copy the elements of an array. Array bounds are not checked.
    copyM :: MArray s e -> Int -> MArray s e -> Int -> Int -> ST s ()
    copyM :: forall s e.
    MArray s e -> Int -> MArray s e -> Int -> Int -> ST s ()
    copyM !MArray s e
    src !_sidx :: Int
    _sidx@(I# Int#
    sidx#) !MArray s e
    dst !_didx :: Int
    _didx@(I# Int#
    didx#) _n :: Int
    _n@(I# Int#
    n#) =
        CHECK_BOUNDS("copyM: src", lengthM src, _sidx + _n - 1)
        CHECK_BOUNDS("copyM: dst", lengthM dst, _didx + _n - 1)
        STRep s () -> ST s ()
    forall s a. STRep s a -> ST s a
    ST (STRep s () -> ST s ()) -> STRep s () -> ST s ()
    forall a b. (a -> b) -> a -> b
    $ \ State# s
    s# ->
        case SmallMutableArray# s e
    -> Int#
    -> SmallMutableArray# s e
    -> Int#
    -> Int#
    -> State# s
    -> State# s
    forall d a.
    SmallMutableArray# d a
    -> Int#
    -> SmallMutableArray# d a
    -> Int#
    -> Int#
    -> State# d
    -> State# d
    copySmallMutableArray# (MArray s e -> SmallMutableArray# s e
    forall s a. MArray s a -> SmallMutableArray# s a
    unMArray MArray s e
    src) Int#
    sidx# (MArray s e -> SmallMutableArray# s e
    forall s a. MArray s a -> SmallMutableArray# s a
    unMArray MArray s e
    dst) Int#
    didx# Int#
    n# State# s
    s# of
            State# s
    s2 -> (# State# s
    s2, () #)

    cloneM :: MArray s a -> Int -> Int -> ST s (MArray s a)
    cloneM :: forall s a. MArray s a -> Int -> Int -> ST s (MArray s a)
    cloneM _mary :: MArray s a
    _mary@(MArray SmallMutableArray# s a
    mary#) _off :: Int
    _off@(I# Int#
    off#) _len :: Int
    _len@(I# Int#
    len#) =
        CHECK_BOUNDS("cloneM_off", lengthM _mary, _off)
        CHECK_BOUNDS("cloneM_end", lengthM _mary, _off + _len - 1)
        STRep s (MArray s a) -> ST s (MArray s a)
    forall s a. STRep s a -> ST s a
    ST (STRep s (MArray s a) -> ST s (MArray s a))
    -> STRep s (MArray s a) -> ST s (MArray s a)
    forall a b. (a -> b) -> a -> b
    $ \ State# s
    s ->
        case SmallMutableArray# s a
    -> Int#
    -> Int#
    -> State# s
    -> (# State# s, SmallMutableArray# s a #)
    forall d a.
    SmallMutableArray# d a
    -> Int#
    -> Int#
    -> State# d
    -> (# State# d, SmallMutableArray# d a #)
    cloneSmallMutableArray# SmallMutableArray# s a
    mary# Int#
    off# Int#
    len# State# s
    s of
          (# State# s
    s', SmallMutableArray# s a
    mary'# #) -> (# State# s
    s', SmallMutableArray# s a -> MArray s a
    forall s a. SmallMutableArray# s a -> MArray s a
    MArray SmallMutableArray# s a
    mary'# #)

    -- | \(O(n)\) Insert an element at the given position in this array,
    -- increasing its size by one.
    insert :: Array e -> Int -> e -> Array e
    insert :: forall e. Array e -> Int -> e -> Array e
    insert Array e
    ary Int
    idx e
    b = (forall s. ST s (Array e)) -> Array e
    forall a. (forall s. ST s a) -> a
    runST (Array e -> Int -> e -> ST s (Array e)
    forall e s. Array e -> Int -> e -> ST s (Array e)
    insertM Array e
    ary Int
    idx e
    b)
    {-# INLINE insert #-}

    -- | \(O(n)\) Insert an element at the given position in this array,
    -- increasing its size by one.
    insertM :: Array e -> Int -> e -> ST s (Array e)
    insertM :: forall e s. Array e -> Int -> e -> ST s (Array e)
    insertM Array e
    ary Int
    idx e
    b =
        CHECK_BOUNDS("insertM", count + 1, idx)
            do mary <- Int -> e -> ST s (MArray s e)
    forall a s. Int -> a -> ST s (MArray s a)
    new (Int
    countInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    1) e
    b
               copy ary 0 mary 0 idx
               copy ary idx mary (idx+1) (count-idx)
               unsafeFreeze mary
      where !count :: Int
    count = Array e -> Int
    forall a. Array a -> Int
    length Array e
    ary
    {-# INLINE insertM #-}

    -- | \(O(n)\) Update the element at the given position in this array.
    update :: Array e -> Int -> e -> Array e
    update :: forall e. Array e -> Int -> e -> Array e
    update Array e
    ary Int
    idx e
    b = (forall s. ST s (Array e)) -> Array e
    forall a. (forall s. ST s a) -> a
    runST (Array e -> Int -> e -> ST s (Array e)
    forall e s. Array e -> Int -> e -> ST s (Array e)
    updateM Array e
    ary Int
    idx e
    b)
    {-# INLINE update #-}

    -- | \(O(n)\) Update the element at the given position in this array.
    updateM :: Array e -> Int -> e -> ST s (Array e)
    updateM :: forall e s. Array e -> Int -> e -> ST s (Array e)
    updateM Array e
    ary Int
    idx e
    b =
        CHECK_BOUNDS("updateM", count, idx)
            do mary <- Array e -> Int -> Int -> ST s (MArray s e)
    forall e s. Array e -> Int -> Int -> ST s (MArray s e)
    thaw Array e
    ary Int
    0 Int
    count
               write mary idx b
               unsafeFreeze mary
      where !count :: Int
    count = Array e -> Int
    forall a. Array a -> Int
    length Array e
    ary
    {-# INLINE updateM #-}

    -- | \(O(n)\) Update the element at the given position in this array, by
    -- applying a function to it.  Evaluates the element to WHNF before
    -- inserting it into the array.
    updateWith' :: Array e -> Int -> (e -> e) -> Array e
    updateWith' :: forall e. Array e -> Int -> (e -> e) -> Array e
    updateWith' Array e
    ary Int
    idx e -> e
    f
      | (# e
    x #) <- Array e -> Int -> (# e #)
    forall a. Array a -> Int -> (# a #)
    index# Array e
    ary Int
    idx
      = Array e -> Int -> e -> Array e
    forall e. Array e -> Int -> e -> Array e
    update Array e
    ary Int
    idx (e -> Array e) -> e -> Array e
    forall a b. (a -> b) -> a -> b
    $! e -> e
    f e
    x
    {-# INLINE updateWith' #-}

    -- | \(O(1)\) Update the element at the given position in this array,
    -- without copying.
    unsafeUpdateM :: Array e -> Int -> e -> ST s ()
    unsafeUpdateM :: forall e s. Array e -> Int -> e -> ST s ()
    unsafeUpdateM Array e
    ary Int
    idx e
    b =
        CHECK_BOUNDS("unsafeUpdateM", length ary, idx)
            do mary <- Array e -> ST s (MArray s e)
    forall a s. Array a -> ST s (MArray s a)
    unsafeThaw Array e
    ary
               write mary idx b
               _ <- unsafeFreeze mary
               return ()
    {-# INLINE unsafeUpdateM #-}

    foldl' :: (b -> a -> b) -> b -> Array a -> b
    foldl' :: forall b a. (b -> a -> b) -> b -> Array a -> b
    foldl' b -> a -> b
    f = \ b
    z0 Array a
    ary0 -> Array a -> Int -> Int -> b -> b
    go Array a
    ary0 (Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0) Int
    0 b
    z0
      where
        go :: Array a -> Int -> Int -> b -> b
    go Array a
    ary Int
    n Int
    i !b
    z
            | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    n = b
    z
            | Bool
    otherwise
            = case Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    ary Int
    i of
                (# a
    x #) -> Array a -> Int -> Int -> b -> b
    go Array a
    ary Int
    n (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    1) (b -> a -> b
    f b
    z a
    x)
    {-# INLINE foldl' #-}

    foldr' :: (a -> b -> b) -> b -> Array a -> b
    foldr' :: forall a b. (a -> b -> b) -> b -> Array a -> b
    foldr' a -> b -> b
    f = \ b
    z0 Array a
    ary0 -> Array a -> Int -> b -> b
    go Array a
    ary0 (Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0 Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) b
    z0
      where
        go :: Array a -> Int -> b -> b
    go !Array a
    _ary (-1) b
    z = b
    z
        go !Array a
    ary Int
    i !b
    z
          | (# a
    x #) <- Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    ary Int
    i
          = Array a -> Int -> b -> b
    go Array a
    ary (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) (a -> b -> b
    f a
    x b
    z)
    {-# INLINE foldr' #-}

    foldr :: (a -> b -> b) -> b -> Array a -> b
    foldr :: forall a b. (a -> b -> b) -> b -> Array a -> b
    foldr a -> b -> b
    f = \ b
    z0 Array a
    ary0 -> Array a -> Int -> Int -> b -> b
    go Array a
    ary0 (Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0) Int
    0 b
    z0
      where
        go :: Array a -> Int -> Int -> b -> b
    go Array a
    ary Int
    n Int
    i b
    z
            | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    n = b
    z
            | Bool
    otherwise
            = case Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    ary Int
    i of
                (# a
    x #) -> a -> b -> b
    f a
    x (Array a -> Int -> Int -> b -> b
    go Array a
    ary Int
    n (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    1) b
    z)
    {-# INLINE foldr #-}

    foldl :: (b -> a -> b) -> b -> Array a -> b
    foldl :: forall b a. (b -> a -> b) -> b -> Array a -> b
    foldl b -> a -> b
    f = \ b
    z0 Array a
    ary0 -> Array a -> Int -> b -> b
    go Array a
    ary0 (Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0 Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) b
    z0
      where
        go :: Array a -> Int -> b -> b
    go Array a
    _ary (-1) b
    z = b
    z
        go Array a
    ary Int
    i b
    z
          | (# a
    x #) <- Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    ary Int
    i
          = b -> a -> b
    f (Array a -> Int -> b -> b
    go Array a
    ary (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) b
    z) a
    x
    {-# INLINE foldl #-}

    -- We go to a bit of trouble here to avoid appending an extra mempty.
    -- The below implementation is by Mateusz Kowalczyk, who indicates that
    -- benchmarks show it to be faster than one that avoids lifting out
    -- lst.
    foldMap :: Monoid m => (a -> m) -> Array a -> m
    foldMap :: forall m a. Monoid m => (a -> m) -> Array a -> m
    foldMap a -> m
    f = \Array a
    ary0 -> case Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0 of
      Int
    0 -> m
    forall a. Monoid a => a
    mempty
      Int
    len ->
        let !lst :: Int
    lst = Int
    len Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1
            go :: Int -> m
    go Int
    i | (# a
    x #) <- Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    ary0 Int
    i, let fx :: m
    fx = a -> m
    f a
    x =
              if Int
    i Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    lst then m
    fx else m
    fx m -> m -> m
    forall a. Monoid a => a -> a -> a
    `mappend` Int -> m
    go (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1)
        in Int -> m
    go Int
    0
    {-# INLINE foldMap #-}

    -- | Verifies that a predicate holds for all elements of an array.
    all :: (a -> Bool) -> Array a -> Bool
    all :: forall a. (a -> Bool) -> Array a -> Bool
    all a -> Bool
    p = (a -> Bool -> Bool) -> Bool -> Array a -> Bool
    forall a b. (a -> b -> b) -> b -> Array a -> b
    foldr (\a
    a Bool
    acc -> a -> Bool
    p a
    a Bool -> Bool -> Bool
    && Bool
    acc) Bool
    True
    {-# INLINE all #-}

    undefinedElem :: a
    undefinedElem :: forall a. a
    undefinedElem = String -> a
    forall a. HasCallStack => String -> a
    error String
    "Data.HashMap.Internal.Array: Undefined element"
    {-# NOINLINE undefinedElem #-}

    thaw :: Array e -> Int -> Int -> ST s (MArray s e)
    thaw :: forall e s. Array e -> Int -> Int -> ST s (MArray s e)
    thaw !Array e
    ary !_o :: Int
    _o@(I# Int#
    o#) _n :: Int
    _n@(I# Int#
    n#) =
        CHECK_LE("thaw", _o + _n, length ary)
            STRep s (MArray s e) -> ST s (MArray s e)
    forall s a. STRep s a -> ST s a
    ST (STRep s (MArray s e) -> ST s (MArray s e))
    -> STRep s (MArray s e) -> ST s (MArray s e)
    forall a b. (a -> b) -> a -> b
    $ \ State# s
    s -> case SmallArray# e
    -> Int#
    -> Int#
    -> State# s
    -> (# State# s, SmallMutableArray# s e #)
    forall a d.
    SmallArray# a
    -> Int#
    -> Int#
    -> State# d
    -> (# State# d, SmallMutableArray# d a #)
    thawSmallArray# (Array e -> SmallArray# e
    forall a. Array a -> SmallArray# a
    unArray Array e
    ary) Int#
    o# Int#
    n# State# s
    s of
                (# State# s
    s2, SmallMutableArray# s e
    mary# #) -> (# State# s
    s2, SmallMutableArray# s e -> MArray s e
    forall s a. SmallMutableArray# s a -> MArray s a
    MArray SmallMutableArray# s e
    mary# #)
    {-# INLINE thaw #-}

    -- | \(O(n)\) Delete an element at the given position in this array,
    -- decreasing its size by one.
    delete :: Array e -> Int -> Array e
    delete :: forall e. Array e -> Int -> Array e
    delete Array e
    ary Int
    idx = (forall s. ST s (Array e)) -> Array e
    forall a. (forall s. ST s a) -> a
    runST (Array e -> Int -> ST s (Array e)
    forall e s. Array e -> Int -> ST s (Array e)
    deleteM Array e
    ary Int
    idx)
    {-# INLINE delete #-}

    -- | \(O(n)\) Delete an element at the given position in this array,
    -- decreasing its size by one.
    deleteM :: Array e -> Int -> ST s (Array e)
    deleteM :: forall e s. Array e -> Int -> ST s (Array e)
    deleteM Array e
    ary Int
    idx = do
        CHECK_BOUNDS("deleteM", count, idx)
            do mary <- Int -> ST s (MArray s e)
    forall s a. Int -> ST s (MArray s a)
    new_ (Int
    countInt -> Int -> Int
    forall a. Num a => a -> a -> a
    -Int
    1)
               copy ary 0 mary 0 idx
               copy ary (idx+1) mary idx (count-(idx+1))
               unsafeFreeze mary
      where !count :: Int
    count = Array e -> Int
    forall a. Array a -> Int
    length Array e
    ary
    {-# INLINE deleteM #-}

    map :: (a -> b) -> Array a -> Array b
    map :: forall a b. (a -> b) -> Array a -> Array b
    map a -> b
    f = \ Array a
    ary ->
        let !n :: Int
    n = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary
        in (forall s. ST s (MArray s b)) -> Array b
    forall e. (forall s. ST s (MArray s e)) -> Array e
    run ((forall s. ST s (MArray s b)) -> Array b)
    -> (forall s. ST s (MArray s b)) -> Array b
    forall a b. (a -> b) -> a -> b
    $ do
            mary <- Int -> ST s (MArray s b)
    forall s a. Int -> ST s (MArray s a)
    new_ Int
    n
            go ary mary 0 n
            return mary
      where
        go :: Array a -> MArray s b -> Int -> Int -> ST s ()
    go Array a
    ary MArray s b
    mary Int
    i Int
    n
            | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    n    = () -> ST s ()
    forall a. a -> ST s a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
            | Bool
    otherwise = do
                 x <- Array a -> Int -> ST s a
    forall a s. Array a -> Int -> ST s a
    indexM Array a
    ary Int
    i
                 write mary i $ f x
                 go ary mary (i+1) n
    {-# INLINE map #-}

    -- | Strict version of 'map'.
    map' :: (a -> b) -> Array a -> Array b
    map' :: forall a b. (a -> b) -> Array a -> Array b
    map' a -> b
    f = \ Array a
    ary ->
        let !n :: Int
    n = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary
        in (forall s. ST s (MArray s b)) -> Array b
    forall e. (forall s. ST s (MArray s e)) -> Array e
    run ((forall s. ST s (MArray s b)) -> Array b)
    -> (forall s. ST s (MArray s b)) -> Array b
    forall a b. (a -> b) -> a -> b
    $ do
            mary <- Int -> ST s (MArray s b)
    forall s a. Int -> ST s (MArray s a)
    new_ Int
    n
            go ary mary 0 n
            return mary
      where
        go :: Array a -> MArray s b -> Int -> Int -> ST s ()
    go Array a
    ary MArray s b
    mary Int
    i Int
    n
            | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    >= Int
    n    = () -> ST s ()
    forall a. a -> ST s a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
            | Bool
    otherwise = do
                 x <- Array a -> Int -> ST s a
    forall a s. Array a -> Int -> ST s a
    indexM Array a
    ary Int
    i
                 write mary i $! f x
                 go ary mary (i+1) n
    {-# INLINE map' #-}

    fromList :: Int -> [a] -> Array a
    fromList :: forall a. Int -> [a] -> Array a
    fromList Int
    n [a]
    xs0 =
        CHECK_EQ("fromList", n, Prelude.length xs0)
            (forall s. ST s (MArray s a)) -> Array a
    forall e. (forall s. ST s (MArray s e)) -> Array e
    run ((forall s. ST s (MArray s a)) -> Array a)
    -> (forall s. ST s (MArray s a)) -> Array a
    forall a b. (a -> b) -> a -> b
    $ do
                mary <- Int -> ST s (MArray s a)
    forall s a. Int -> ST s (MArray s a)
    new_ Int
    n
                go xs0 mary 0
                return mary
      where
        go :: [a] -> MArray s a -> Int -> ST s ()
    go []     !MArray s a
    _   !Int
    _ = () -> ST s ()
    forall a. a -> ST s a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
        go (a
    x:[a]
    xs) MArray s a
    mary Int
    i  = do MArray s a -> Int -> a -> ST s ()
    forall s a. MArray s a -> Int -> a -> ST s ()
    write MArray s a
    mary Int
    i a
    x
                               [a] -> MArray s a -> Int -> ST s ()
    go [a]
    xs MArray s a
    mary (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    1)

    fromList' :: Int -> [a] -> Array a
    fromList' :: forall a. Int -> [a] -> Array a
    fromList' Int
    n [a]
    xs0 =
        CHECK_EQ("fromList'", n, Prelude.length xs0)
            (forall s. ST s (MArray s a)) -> Array a
    forall e. (forall s. ST s (MArray s e)) -> Array e
    run ((forall s. ST s (MArray s a)) -> Array a)
    -> (forall s. ST s (MArray s a)) -> Array a
    forall a b. (a -> b) -> a -> b
    $ do
                mary <- Int -> ST s (MArray s a)
    forall s a. Int -> ST s (MArray s a)
    new_ Int
    n
                go xs0 mary 0
                return mary
      where
        go :: [a] -> MArray s a -> Int -> ST s ()
    go []      !MArray s a
    _   !Int
    _ = () -> ST s ()
    forall a. a -> ST s a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
        go (!a
    x:[a]
    xs) MArray s a
    mary Int
    i  = do MArray s a -> Int -> a -> ST s ()
    forall s a. MArray s a -> Int -> a -> ST s ()
    write MArray s a
    mary Int
    i a
    x
                                [a] -> MArray s a -> Int -> ST s ()
    go [a]
    xs MArray s a
    mary (Int
    iInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    1)

    -- | @since 0.2.17.0
    instance TH.Lift a => TH.Lift (Array a) where
    #if MIN_VERSION_template_haskell(2,16,0)
      liftTyped :: forall (m :: * -> *). Quote m => Array a -> Code m (Array a)
    liftTyped Array a
    ar = [|| Int -> [a] -> Array a
    forall a. Int -> [a] -> Array a
    fromList' Int
    arlen [a]
    arlist ||]
    #else
      lift ar = [| fromList' arlen arlist |]
    #endif
        where
          arlen :: Int
    arlen = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ar
          arlist :: [a]
    arlist = Array a -> [a]
    forall a. Array a -> [a]
    toList Array a
    ar

    toList :: Array a -> [a]
    toList :: forall a. Array a -> [a]
    toList = (a -> [a] -> [a]) -> [a] -> Array a -> [a]
    forall a b. (a -> b -> b) -> b -> Array a -> b
    foldr (:) []

    newtype STA a = STA {forall a.
    STA a -> forall s. SmallMutableArray# s a -> ST s (Array a)
    _runSTA :: forall s. SmallMutableArray# s a -> ST s (Array a)}

    runSTA :: Int -> STA a -> Array a
    runSTA :: forall a. Int -> STA a -> Array a
    runSTA !Int
    n (STA forall s. SmallMutableArray# s a -> ST s (Array a)
    m) = (forall s. ST s (Array a)) -> Array a
    forall a. (forall s. ST s a) -> a
    runST ((forall s. ST s (Array a)) -> Array a)
    -> (forall s. ST s (Array a)) -> Array a
    forall a b. (a -> b) -> a -> b
    $ Int -> ST s (MArray s a)
    forall s a. Int -> ST s (MArray s a)
    new_ Int
    n ST s (MArray s a)
    -> (MArray s a -> ST s (Array a)) -> ST s (Array a)
    forall a b. ST s a -> (a -> ST s b) -> ST s b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= \ (MArray SmallMutableArray# s a
    ar) -> SmallMutableArray# s a -> ST s (Array a)
    forall s. SmallMutableArray# s a -> ST s (Array a)
    m SmallMutableArray# s a
    ar

    traverse :: Applicative f => (a -> f b) -> Array a -> f (Array b)
    traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Array a -> f (Array b)
    traverse a -> f b
    f = \ !Array a
    ary ->
      let
        !len :: Int
    len = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary
        go :: Int -> f (STA b)
    go !Int
    i
          | Int
    i Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    len = STA b -> f (STA b)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (STA b -> f (STA b)) -> STA b -> f (STA b)
    forall a b. (a -> b) -> a -> b
    $ (forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b
    forall a.
    (forall s. SmallMutableArray# s a -> ST s (Array a)) -> STA a
    STA ((forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b)
    -> (forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b
    forall a b. (a -> b) -> a -> b
    $ \SmallMutableArray# s b
    mary -> MArray s b -> ST s (Array b)
    forall s a. MArray s a -> ST s (Array a)
    unsafeFreeze (SmallMutableArray# s b -> MArray s b
    forall s a. SmallMutableArray# s a -> MArray s a
    MArray SmallMutableArray# s b
    mary)
          | (# a
    x #) <- Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    ary Int
    i
          = (b -> STA b -> STA b) -> f b -> f (STA b) -> f (STA b)
    forall a b c. (a -> b -> c) -> f a -> f b -> f c
    forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> f a -> f b -> f c
    liftA2 (\b
    b (STA forall s. SmallMutableArray# s b -> ST s (Array b)
    m) -> (forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b
    forall a.
    (forall s. SmallMutableArray# s a -> ST s (Array a)) -> STA a
    STA ((forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b)
    -> (forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b
    forall a b. (a -> b) -> a -> b
    $ \SmallMutableArray# s b
    mary ->
                      MArray s b -> Int -> b -> ST s ()
    forall s a. MArray s a -> Int -> a -> ST s ()
    write (SmallMutableArray# s b -> MArray s b
    forall s a. SmallMutableArray# s a -> MArray s a
    MArray SmallMutableArray# s b
    mary) Int
    i b
    b ST s () -> ST s (Array b) -> ST s (Array b)
    forall a b. ST s a -> ST s b -> ST s b
    forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> SmallMutableArray# s b -> ST s (Array b)
    forall s. SmallMutableArray# s b -> ST s (Array b)
    m SmallMutableArray# s b
    mary)
                   (a -> f b
    f a
    x) (Int -> f (STA b)
    go (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1))
      in Int -> STA b -> Array b
    forall a. Int -> STA a -> Array a
    runSTA Int
    len (STA b -> Array b) -> f (STA b) -> f (Array b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Int -> f (STA b)
    go Int
    0
    {-# INLINE [1] traverse #-}

    -- TODO: Would it be better to just use a lazy traversal
    -- and then force the elements of the result? My guess is
    -- yes.
    traverse' :: Applicative f => (a -> f b) -> Array a -> f (Array b)
    traverse' :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Array a -> f (Array b)
    traverse' a -> f b
    f = \ !Array a
    ary ->
      let
        !len :: Int
    len = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary
        go :: Int -> f (STA b)
    go !Int
    i
          | Int
    i Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    len = STA b -> f (STA b)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (STA b -> f (STA b)) -> STA b -> f (STA b)
    forall a b. (a -> b) -> a -> b
    $ (forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b
    forall a.
    (forall s. SmallMutableArray# s a -> ST s (Array a)) -> STA a
    STA ((forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b)
    -> (forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b
    forall a b. (a -> b) -> a -> b
    $ \SmallMutableArray# s b
    mary -> MArray s b -> ST s (Array b)
    forall s a. MArray s a -> ST s (Array a)
    unsafeFreeze (SmallMutableArray# s b -> MArray s b
    forall s a. SmallMutableArray# s a -> MArray s a
    MArray SmallMutableArray# s b
    mary)
          | (# a
    x #) <- Array a -> Int -> (# a #)
    forall a. Array a -> Int -> (# a #)
    index# Array a
    ary Int
    i
          = (b -> STA b -> STA b) -> f b -> f (STA b) -> f (STA b)
    forall a b c. (a -> b -> c) -> f a -> f b -> f c
    forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> f a -> f b -> f c
    liftA2 (\ !b
    b (STA forall s. SmallMutableArray# s b -> ST s (Array b)
    m) -> (forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b
    forall a.
    (forall s. SmallMutableArray# s a -> ST s (Array a)) -> STA a
    STA ((forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b)
    -> (forall s. SmallMutableArray# s b -> ST s (Array b)) -> STA b
    forall a b. (a -> b) -> a -> b
    $ \SmallMutableArray# s b
    mary ->
                        MArray s b -> Int -> b -> ST s ()
    forall s a. MArray s a -> Int -> a -> ST s ()
    write (SmallMutableArray# s b -> MArray s b
    forall s a. SmallMutableArray# s a -> MArray s a
    MArray SmallMutableArray# s b
    mary) Int
    i b
    b ST s () -> ST s (Array b) -> ST s (Array b)
    forall a b. ST s a -> ST s b -> ST s b
    forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
    >> SmallMutableArray# s b -> ST s (Array b)
    forall s. SmallMutableArray# s b -> ST s (Array b)
    m SmallMutableArray# s b
    mary)
                   (a -> f b
    f a
    x) (Int -> f (STA b)
    go (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1))
      in Int -> STA b -> Array b
    forall a. Int -> STA a -> Array a
    runSTA Int
    len (STA b -> Array b) -> f (STA b) -> f (Array b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Int -> f (STA b)
    go Int
    0
    {-# INLINE [1] traverse' #-}

    -- Traversing in ST, we don't need to get fancy; we
    -- can just do it directly.
    traverseST :: (a -> ST s b) -> Array a -> ST s (Array b)
    traverseST :: forall a s b. (a -> ST s b) -> Array a -> ST s (Array b)
    traverseST a -> ST s b
    f = \ Array a
    ary0 ->
      let
        !len :: Int
    len = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0
        go :: Int -> MArray s b -> ST s (MArray s b)
    go Int
    k !MArray s b
    mary
          | Int
    k Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    len = MArray s b -> ST s (MArray s b)
    forall a. a -> ST s a
    forall (m :: * -> *) a. Monad m => a -> m a
    return MArray s b
    mary
          | Bool
    otherwise = do
              x <- Array a -> Int -> ST s a
    forall a s. Array a -> Int -> ST s a
    indexM Array a
    ary0 Int
    k
              y <- f x
              write mary k y
              go (k + 1) mary
      in Int -> ST s (MArray s b)
    forall s a. Int -> ST s (MArray s a)
    new_ Int
    len ST s (MArray s b)
    -> (MArray s b -> ST s (Array b)) -> ST s (Array b)
    forall a b. ST s a -> (a -> ST s b) -> ST s b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= (Int -> MArray s b -> ST s (MArray s b)
    go Int
    0 (MArray s b -> ST s (MArray s b))
    -> (MArray s b -> ST s (Array b)) -> MArray s b -> ST s (Array b)
    forall (m :: * -> *) a b c.
    Monad m =>
    (a -> m b) -> (b -> m c) -> a -> m c
    >=> MArray s b -> ST s (Array b)
    forall s a. MArray s a -> ST s (Array a)
    unsafeFreeze)
    {-# INLINE traverseST #-}

    traverseIO :: (a -> IO b) -> Array a -> IO (Array b)
    traverseIO :: forall a b. (a -> IO b) -> Array a -> IO (Array b)
    traverseIO a -> IO b
    f = \ Array a
    ary0 ->
      let
        !len :: Int
    len = Array a -> Int
    forall a. Array a -> Int
    length Array a
    ary0
        go :: Int -> MArray RealWorld b -> IO (MArray RealWorld b)
    go Int
    k !MArray RealWorld b
    mary
          | Int
    k Int -> Int -> Bool
    forall a. Eq a => a -> a -> Bool
    == Int
    len = MArray RealWorld b -> IO (MArray RealWorld b)
    forall a. a -> IO a
    forall (m :: * -> *) a. Monad m => a -> m a
    return MArray RealWorld b
    mary
          | Bool
    otherwise = do
              x <- ST RealWorld a -> IO a
    forall a. ST RealWorld a -> IO a
    stToIO (ST RealWorld a -> IO a) -> ST RealWorld a -> IO a
    forall a b. (a -> b) -> a -> b
    $ Array a -> Int -> ST RealWorld a
    forall a s. Array a -> Int -> ST s a
    indexM Array a
    ary0 Int
    k
              y <- f x
              stToIO $ write mary k y
              go (k + 1) mary
      in ST RealWorld (MArray RealWorld b) -> IO (MArray RealWorld b)
    forall a. ST RealWorld a -> IO a
    stToIO (Int -> ST RealWorld (MArray RealWorld b)
    forall s a. Int -> ST s (MArray s a)
    new_ Int
    len) IO (MArray RealWorld b)
    -> (MArray RealWorld b -> IO (Array b)) -> IO (Array b)
    forall a b. IO a -> (a -> IO b) -> IO b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= (Int -> MArray RealWorld b -> IO (MArray RealWorld b)
    go Int
    0 (MArray RealWorld b -> IO (MArray RealWorld b))
    -> (MArray RealWorld b -> IO (Array b))
    -> MArray RealWorld b
    -> IO (Array b)
    forall (m :: * -> *) a b c.
    Monad m =>
    (a -> m b) -> (b -> m c) -> a -> m c
    >=> ST RealWorld (Array b) -> IO (Array b)
    forall a. ST RealWorld a -> IO a
    stToIO (ST RealWorld (Array b) -> IO (Array b))
    -> (MArray RealWorld b -> ST RealWorld (Array b))
    -> MArray RealWorld b
    -> IO (Array b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . MArray RealWorld b -> ST RealWorld (Array b)
    forall s a. MArray s a -> ST s (Array a)
    unsafeFreeze)
    {-# INLINE traverseIO #-}

    -- Why don't we have similar RULES for traverse'? The efficient
    -- way to traverse strictly in IO or ST is to force results as
    -- they come in, which leads to different semantics. In particular,
    -- we need to ensure that
    --
    --  traverse' (\x -> print x *> pure undefined) xs
    --
    -- will actually print all the values and then return undefined.
    -- We could add a strict mapMWithIndex, operating in an arbitrary
    -- Monad, that supported such rules, but we don't have that right now.
    {-# RULES
    "traverse/ST" forall f. traverse f = traverseST f
    "traverse/IO" forall f. traverse f = traverseIO f
     #-}