{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}

{-# OPTIONS_GHC -O2 -Wall #-}
module Data.Map.Unboxed.Unboxed
  ( Map
  , empty
  , singleton
  , lookup
  , size
    -- * Transform
  , map
  , mapMaybe
  , mapMaybeWithKey
  , adjustMany
  , adjustManyInline
    -- * Folds
  , foldlWithKey'
  , foldrWithKey'
  , foldMapWithKey'
    -- * Monadic Folds
  , foldlWithKeyM'
  , foldrWithKeyM'
  , foldlMapWithKeyM'
  , foldrMapWithKeyM'
    -- * Traversals
  , traverse
  , traverseWithKey
  , traverseWithKey_
    -- * List Conversion
  , toList
  , fromList
  , fromListAppend
  , fromListN
  , fromListAppendN
  , fromSet
  , fromSetP
    -- * Array Conversion
  , unsafeFreezeZip
  ) where

import Prelude hiding (lookup,map,traverse)

import Control.Monad.Primitive (PrimMonad)
import Control.Monad.ST (ST)
import Data.Primitive.PrimArray (PrimArray,MutablePrimArray)
import Data.Primitive.Types (Prim)
import Data.Semigroup (Semigroup)
import Data.Set.Unboxed.Internal (Set(..))

import qualified Data.Map.Internal as I
import qualified Data.Semigroup as SG
import qualified GHC.Exts as E

-- | A map from keys @k@ to values @v@. The key type and the value
--   type must both have 'Prim' instances.
newtype Map k v = Map (I.Map PrimArray PrimArray k v)

instance (Prim k, Ord k, Prim v, Semigroup v) => Semigroup (Map k v) where
  Map Map PrimArray PrimArray k v
x <> :: Map k v -> Map k v -> Map k v
<> Map Map PrimArray PrimArray k v
y = forall k v. Map PrimArray PrimArray k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k, Semigroup v) =>
Map karr varr k v -> Map karr varr k v -> Map karr varr k v
I.append Map PrimArray PrimArray k v
x Map PrimArray PrimArray k v
y)

instance (Prim k, Ord k, Prim v, Semigroup v) => Monoid (Map k v) where
  mempty :: Map k v
mempty = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
I.empty
  mappend :: Map k v -> Map k v -> Map k v
mappend = forall a. Semigroup a => a -> a -> a
(SG.<>)
  mconcat :: [Map k v] -> Map k v
mconcat = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
[Map karr varr k v] -> Map karr varr k v
I.concat forall b c a. (b -> c) -> (a -> b) -> a -> c
. coerce :: forall a b. Coercible a b => a -> b
E.coerce

instance (Prim k, Eq k, Prim v, Eq v) => Eq (Map k v) where
  Map Map PrimArray PrimArray k v
x == :: Map k v -> Map k v -> Bool
== Map Map PrimArray PrimArray k v
y = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Eq k, ContiguousU varr,
 Element varr v, Eq v) =>
Map karr varr k v -> Map karr varr k v -> Bool
I.equals Map PrimArray PrimArray k v
x Map PrimArray PrimArray k v
y

instance (Prim k, Ord k, Prim v, Ord v) => Ord (Map k v) where
  compare :: Map k v -> Map k v -> Ordering
compare (Map Map PrimArray PrimArray k v
x) (Map Map PrimArray PrimArray k v
y) = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Ord v) =>
Map karr varr k v -> Map karr varr k v -> Ordering
I.compare Map PrimArray PrimArray k v
x Map PrimArray PrimArray k v
y

instance (Prim k, Ord k, Prim v) => E.IsList (Map k v) where
  type Item (Map k v) = (k,v)
  fromListN :: Int -> [Item (Map k v)] -> Map k v
fromListN Int
n = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Int -> [(k, v)] -> Map karr varr k v
I.fromListN Int
n
  fromList :: [Item (Map k v)] -> Map k v
fromList = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
[(k, v)] -> Map karr varr k v
I.fromList
  toList :: Map k v -> [Item (Map k v)]
toList (Map Map PrimArray PrimArray k v
s) = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
Map karr varr k v -> [(k, v)]
I.toList Map PrimArray PrimArray k v
s

instance (Prim k, Show k, Prim v, Show v) => Show (Map k v) where
  showsPrec :: Int -> Map k v -> ShowS
showsPrec Int
p (Map Map PrimArray PrimArray k v
s) = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Show k, ContiguousU varr,
 Element varr v, Show v) =>
Int -> Map karr varr k v -> ShowS
I.showsPrec Int
p Map PrimArray PrimArray k v
s

-- | /O(log n)/ Lookup the value at a key in the map.
lookup :: (Prim k, Ord k, Prim v) => k -> Map k v -> Maybe v
lookup :: forall k v. (Prim k, Ord k, Prim v) => k -> Map k v -> Maybe v
lookup k
a (Map Map PrimArray PrimArray k v
s) = forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
k -> Map karr varr k v -> Maybe v
I.lookup k
a Map PrimArray PrimArray k v
s

-- | The empty diet map.
empty :: Map k v
empty :: forall k v. Map k v
empty = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
I.empty

-- | /O(1)/ Create a map with a single element.
singleton :: (Prim k, Prim v) => k -> v -> Map k v
singleton :: forall k v. (Prim k, Prim v) => k -> v -> Map k v
singleton k
k v
v = forall k v. Map PrimArray PrimArray k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
k -> v -> Map karr varr k v
I.singleton k
k v
v)

-- | /O(n)/ A list of key-value pairs in ascending order.
toList :: (Prim k, Ord k, Prim v) => Map k v -> [(k,v)]
toList :: forall k v. (Prim k, Ord k, Prim v) => Map k v -> [(k, v)]
toList (Map Map PrimArray PrimArray k v
m) = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
Map karr varr k v -> [(k, v)]
I.toList Map PrimArray PrimArray k v
m

-- | /O(n*log n)/ Create a map from a list of key-value pairs.
-- If the list contains more than one value for the same key,
-- the last value is retained. If the keys in the argument are
-- in nondescending order, this algorithm runs in /O(n)/ time instead.
fromList :: (Prim k, Ord k, Prim v) => [(k,v)] -> Map k v
fromList :: forall k v. (Prim k, Ord k, Prim v) => [(k, v)] -> Map k v
fromList = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
[(k, v)] -> Map karr varr k v
I.fromList

-- | /O(n*log n)/ This function has the same behavior as 'fromList'
-- regardless of whether or not the expected size is accurate. Additionally,
-- negative sizes are handled correctly. The expected size is used as the
-- size of the initially allocated buffer when building the 'Map'. If the
-- keys in the argument are in nondescending order, this algorithm runs
-- in /O(n)/ time.
fromListN :: (Prim k, Ord k, Prim v)
  => Int -- ^ expected size of resulting 'Map'
  -> [(k,v)] -- ^ key-value pairs
  -> Map k v
fromListN :: forall k v. (Prim k, Ord k, Prim v) => Int -> [(k, v)] -> Map k v
fromListN Int
n = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Int -> [(k, v)] -> Map karr varr k v
I.fromListN Int
n

-- | /O(n*log n)/ This function has the same behavior as 'fromList',
-- but it combines values with the 'Semigroup' instances instead of
-- choosing the last occurrence.
fromListAppend :: (Prim k, Ord k, Prim v, Semigroup v) => [(k,v)] -> Map k v
fromListAppend :: forall k v.
(Prim k, Ord k, Prim v, Semigroup v) =>
[(k, v)] -> Map k v
fromListAppend = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
[(k, v)] -> Map karr varr k v
I.fromListAppend

-- | /O(n*log n)/ This function has the same behavior as 'fromListN',
-- but it combines values with the 'Semigroup' instances instead of
-- choosing the last occurrence.
fromListAppendN :: (Prim k, Ord k, Prim v, Semigroup v)
  => Int -- ^ expected size of resulting 'Map'
  -> [(k,v)] -- ^ key-value pairs
  -> Map k v
fromListAppendN :: forall k v.
(Prim k, Ord k, Prim v, Semigroup v) =>
Int -> [(k, v)] -> Map k v
fromListAppendN Int
n = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
Int -> [(k, v)] -> Map karr varr k v
I.fromListAppendN Int
n

-- | /O(n)/ Build a map from a set. This function is uses the underlying
-- array that backs the set as the array for the keys. It constructs the
-- values by apply the given function to each key.
fromSet :: (Prim k, Prim v)
  => (k -> v)
  -> Set k
  -> Map k v
fromSet :: forall k v. (Prim k, Prim v) => (k -> v) -> Set k -> Map k v
fromSet k -> v
f (Set Set PrimArray k
s) = forall k v. Map PrimArray PrimArray k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v) -> Set karr k -> Map karr varr k v
I.fromSet k -> v
f Set PrimArray k
s)

-- | /O(n)/ Build a map from a set. This function is uses the underlying
-- array that backs the set as the array for the keys. It constructs the
-- values by apply the given function to each key. The function can perform
-- primitive monadic effects.
fromSetP :: (PrimMonad m, Prim k, Prim v)
  => (k -> m v)
  -> Set k
  -> m (Map k v)
fromSetP :: forall (m :: * -> *) k v.
(PrimMonad m, Prim k, Prim v) =>
(k -> m v) -> Set k -> m (Map k v)
fromSetP k -> m v
f (Set Set PrimArray k
s) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k v. Map PrimArray PrimArray k v -> Map k v
Map (forall (m :: * -> *) (karr :: * -> *) k (varr :: * -> *) v.
(PrimMonad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> m v) -> Set karr k -> m (Map karr varr k v)
I.fromSetP k -> m v
f Set PrimArray k
s)

-- | /O(1)/ The number of elements in the map.
size :: Prim v => Map k v -> Int
size :: forall v k. Prim v => Map k v -> Int
size (Map Map PrimArray PrimArray k v
m) = forall (varr :: * -> *) v (karr :: * -> *) k.
(ContiguousU varr, Element varr v) =>
Map karr varr k v -> Int
I.size Map PrimArray PrimArray k v
m

-- | /O(n)/ Map over the values in the map.
map :: (Prim k, Prim v, Prim w)
  => (v -> w)
  -> Map k v
  -> Map k w
map :: forall k v w.
(Prim k, Prim v, Prim w) =>
(v -> w) -> Map k v -> Map k w
map v -> w
f (Map Map PrimArray PrimArray k v
m) = forall k v. Map PrimArray PrimArray k v -> Map k v
Map (forall (varr :: * -> *) (warr :: * -> *) v w (karr :: * -> *) k.
(ContiguousU varr, ContiguousU warr, Element varr v,
 Element warr w) =>
(v -> w) -> Map karr varr k v -> Map karr warr k w
I.map v -> w
f Map PrimArray PrimArray k v
m)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
mapMaybe :: (Prim k, Prim v, Prim w)
  => (v -> Maybe w)
  -> Map k v
  -> Map k w
mapMaybe :: forall k v w.
(Prim k, Prim v, Prim w) =>
(v -> Maybe w) -> Map k v -> Map k w
mapMaybe v -> Maybe w
f (Map Map PrimArray PrimArray k v
m) = forall k v. Map PrimArray PrimArray k v -> Map k v
Map (forall (karr :: * -> *) (varr :: * -> *) k v w.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(v -> Maybe w) -> Map karr varr k v -> Map karr varr k w
I.mapMaybe v -> Maybe w
f Map PrimArray PrimArray k v
m)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
-- The predicate is given access to the key.
mapMaybeWithKey :: (Prim k, Prim v, Prim w)
  => (k -> v -> Maybe w)
  -> Map k v
  -> Map k w
mapMaybeWithKey :: forall k v w.
(Prim k, Prim v, Prim w) =>
(k -> v -> Maybe w) -> Map k v -> Map k w
mapMaybeWithKey k -> v -> Maybe w
f (Map Map PrimArray PrimArray k v
m) = forall k v. Map PrimArray PrimArray k v -> Map k v
Map (forall (karr :: * -> *) (varr :: * -> *) k v w.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(k -> v -> Maybe w) -> Map karr varr k v -> Map karr varr k w
I.mapMaybeWithKey k -> v -> Maybe w
f Map PrimArray PrimArray k v
m)

-- | Update the values at any number of keys. This is done
-- on in a buffer without building intermediate maps. Example use:
--
-- > adjustMany
-- >   (\adjust -> do
-- >     adjust 2 (\x -> pure (x + 1))
-- >     adjust 3 (\_ -> pure 42)
-- >   ) myMap
--
-- This increments by 1 the value associated with key 2. Then,
-- it replaces with 42 the value associated with key 3.
adjustMany :: (Prim k, Prim v, PrimMonad m, Ord k)
  => ((k -> (v -> m v) -> m ()) -> m a) -- ^ Modification-applying function
  -> Map k v -- ^ Map
  -> m (Map k v, a)
{-# INLINABLE adjustMany #-}
adjustMany :: forall k v (m :: * -> *) a.
(Prim k, Prim v, PrimMonad m, Ord k) =>
((k -> (v -> m v) -> m ()) -> m a) -> Map k v -> m (Map k v, a)
adjustMany (k -> (v -> m v) -> m ()) -> m a
f (Map Map PrimArray PrimArray k v
m) = do
  (Map PrimArray PrimArray k v
r,a
a) <- forall (karr :: * -> *) (varr :: * -> *) (m :: * -> *) k v a.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, PrimMonad m, Ord k) =>
((k -> (v -> m v) -> m ()) -> m a)
-> Map karr varr k v -> m (Map karr varr k v, a)
I.adjustMany (k -> (v -> m v) -> m ()) -> m a
f Map PrimArray PrimArray k v
m
  forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall k v. Map PrimArray PrimArray k v -> Map k v
Map Map PrimArray PrimArray k v
r, a
a)

-- | This has the same behavior as 'adjustMany'. However, it will be
--   inlined rather than specialized. The can prevent needless boxing
--   in the callback. Use @-ddump-simpl@ and standard profiling techniques
--   to figure out if this function actually helps you.
adjustManyInline :: (Prim k, Prim v, PrimMonad m, Ord k)
  => ((k -> (v -> m v) -> m ()) -> m a) -- ^ Modification-applying function
  -> Map k v -- ^ Map
  -> m (Map k v, a)
{-# INLINE adjustManyInline #-}
adjustManyInline :: forall k v (m :: * -> *) a.
(Prim k, Prim v, PrimMonad m, Ord k) =>
((k -> (v -> m v) -> m ()) -> m a) -> Map k v -> m (Map k v, a)
adjustManyInline (k -> (v -> m v) -> m ()) -> m a
f (Map Map PrimArray PrimArray k v
m) = do
  (Map PrimArray PrimArray k v
r,a
a) <- forall (karr :: * -> *) (varr :: * -> *) (m :: * -> *) k v a.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, PrimMonad m, Ord k) =>
((k -> (v -> m v) -> m ()) -> m a)
-> Map karr varr k v -> m (Map karr varr k v, a)
I.adjustManyInline (k -> (v -> m v) -> m ()) -> m a
f Map PrimArray PrimArray k v
m
  forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall k v. Map PrimArray PrimArray k v -> Map k v
Map Map PrimArray PrimArray k v
r, a
a)

-- | /O(n)/ Left monadic fold over the keys and values of the map. This fold
-- is strict in the accumulator.
foldlWithKeyM' :: (Monad m, Prim k, Prim v)
  => (b -> k -> v -> m b) -- ^ reduction
  -> b -- ^ initial accumulator
  -> Map k v -- ^ map
  -> m b
foldlWithKeyM' :: forall (m :: * -> *) k v b.
(Monad m, Prim k, Prim v) =>
(b -> k -> v -> m b) -> b -> Map k v -> m b
foldlWithKeyM' b -> k -> v -> m b
f b
b0 (Map Map PrimArray PrimArray k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(b -> k -> v -> m b) -> b -> Map karr varr k v -> m b
I.foldlWithKeyM' b -> k -> v -> m b
f b
b0 Map PrimArray PrimArray k v
m

-- | /O(n)/ Right monadic fold over the keys and values of the map. This fold
-- is strict in the accumulator.
foldrWithKeyM' :: (Monad m, Prim k, Prim v)
  => (k -> v -> b -> m b) -- ^ reduction
  -> b -- ^ initial accumulator
  -> Map k v -- ^ map
  -> m b
foldrWithKeyM' :: forall (m :: * -> *) k v b.
(Monad m, Prim k, Prim v) =>
(k -> v -> b -> m b) -> b -> Map k v -> m b
foldrWithKeyM' k -> v -> b -> m b
f b
b0 (Map Map PrimArray PrimArray k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> b -> m b) -> b -> Map karr varr k v -> m b
I.foldrWithKeyM' k -> v -> b -> m b
f b
b0 Map PrimArray PrimArray k v
m

-- | /O(n)/ Monadic left fold over the keys and values of the map with a strict
-- monoidal accumulator. The monoidal accumulator is appended to the left
-- after each reduction.
foldlMapWithKeyM' :: (Monad m, Monoid b, Prim k, Prim v)
  => (k -> v -> m b) -- ^ reduction
  -> Map k v -- ^ map
  -> m b
foldlMapWithKeyM' :: forall (m :: * -> *) b k v.
(Monad m, Monoid b, Prim k, Prim v) =>
(k -> v -> m b) -> Map k v -> m b
foldlMapWithKeyM' k -> v -> m b
f (Map Map PrimArray PrimArray k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid b) =>
(k -> v -> m b) -> Map karr varr k v -> m b
I.foldlMapWithKeyM' k -> v -> m b
f Map PrimArray PrimArray k v
m

-- | /O(n)/ Monadic right fold over the keys and values of the map with a strict
-- monoidal accumulator. The monoidal accumulator is appended to the right
-- after each reduction.
foldrMapWithKeyM' :: (Monad m, Monoid b, Prim k, Prim v)
  => (k -> v -> m b) -- ^ reduction
  -> Map k v -- ^ map
  -> m b
foldrMapWithKeyM' :: forall (m :: * -> *) b k v.
(Monad m, Monoid b, Prim k, Prim v) =>
(k -> v -> m b) -> Map k v -> m b
foldrMapWithKeyM' k -> v -> m b
f (Map Map PrimArray PrimArray k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid b) =>
(k -> v -> m b) -> Map karr varr k v -> m b
I.foldrMapWithKeyM' k -> v -> m b
f Map PrimArray PrimArray k v
m

-- | /O(n)/ traversal over the values in the map.
traverse :: (Applicative f, Prim k, Prim v, Prim b)
  => (v -> f b)
  -> Map k v
  -> f (Map k b)
traverse :: forall (f :: * -> *) k v b.
(Applicative f, Prim k, Prim v, Prim b) =>
(v -> f b) -> Map k v -> f (Map k b)
traverse v -> f b
f (Map Map PrimArray PrimArray k v
m) = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (m :: * -> *) (karr :: * -> *) k (varr :: * -> *) v w.
(Applicative m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(v -> m w) -> Map karr varr k v -> m (Map karr varr k w)
I.traverse v -> f b
f Map PrimArray PrimArray k v
m

-- | /O(n)/ traversal over the values in the map, using the keys.
traverseWithKey :: (Applicative f, Prim k, Prim v, Prim b)
  => (k -> v -> f b)
  -> Map k v
  -> f (Map k b)
traverseWithKey :: forall (f :: * -> *) k v b.
(Applicative f, Prim k, Prim v, Prim b) =>
(k -> v -> f b) -> Map k v -> f (Map k b)
traverseWithKey k -> v -> f b
f (Map Map PrimArray PrimArray k v
m) = forall k v. Map PrimArray PrimArray k v -> Map k v
Map forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (karr :: * -> *) k (varr :: * -> *) v v' (f :: * -> *).
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr v', Applicative f) =>
(k -> v -> f v') -> Map karr varr k v -> f (Map karr varr k v')
I.traverseWithKey k -> v -> f b
f Map PrimArray PrimArray k v
m

-- | /O(n)/ Traverse the keys and values of the map from left to right.
traverseWithKey_ :: (Monad m, Prim k, Prim v)
  => (k -> v -> m b) -- ^ reduction
  -> Map k v -- ^ map
  -> m ()
traverseWithKey_ :: forall (m :: * -> *) k v b.
(Monad m, Prim k, Prim v) =>
(k -> v -> m b) -> Map k v -> m ()
traverseWithKey_ k -> v -> m b
f (Map Map PrimArray PrimArray k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Applicative m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> m b) -> Map karr varr k v -> m ()
I.traverseWithKey_ k -> v -> m b
f Map PrimArray PrimArray k v
m

-- | /O(n)/ Fold over the keys and values of the map with a strict monoidal
-- accumulator. This function does not have left and right variants since
-- the associativity required by a monoid instance means that both variants
-- would always produce the same result.
foldMapWithKey' :: (Monoid b, Prim k, Prim v)
  => (k -> v -> b) -- ^ reduction 
  -> Map k v -- ^ map
  -> b
foldMapWithKey' :: forall b k v.
(Monoid b, Prim k, Prim v) =>
(k -> v -> b) -> Map k v -> b
foldMapWithKey' k -> v -> b
f (Map Map PrimArray PrimArray k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v m.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid m) =>
(k -> v -> m) -> Map karr varr k v -> m
I.foldMapWithKey' k -> v -> b
f Map PrimArray PrimArray k v
m

-- | /O(n)/ Left fold over the keys and values with a strict accumulator.
foldlWithKey' :: (Prim k, Prim v)
  => (b -> k -> v -> b) -- ^ reduction
  -> b -- ^ initial accumulator
  -> Map k v -- ^ map
  -> b
foldlWithKey' :: forall k v b.
(Prim k, Prim v) =>
(b -> k -> v -> b) -> b -> Map k v -> b
foldlWithKey' b -> k -> v -> b
f b
b0 (Map Map PrimArray PrimArray k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(b -> k -> v -> b) -> b -> Map karr varr k v -> b
I.foldlWithKey' b -> k -> v -> b
f b
b0 Map PrimArray PrimArray k v
m

-- | /O(n)/ Right fold over the keys and values with a strict accumulator.
foldrWithKey' :: (Prim k, Prim v)
  => (k -> v -> b -> b) -- ^ reduction
  -> b -- ^ initial accumulator
  -> Map k v -- ^ map
  -> b
foldrWithKey' :: forall k v b.
(Prim k, Prim v) =>
(k -> v -> b -> b) -> b -> Map k v -> b
foldrWithKey' k -> v -> b -> b
f b
b0 (Map Map PrimArray PrimArray k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> b -> b) -> b -> Map karr varr k v -> b
I.foldrWithKey' k -> v -> b -> b
f b
b0 Map PrimArray PrimArray k v
m

-- | /O(n*log n)/ Zip an array of keys with an array of values. If they are
-- not the same length, the longer one will be truncated to match the shorter
-- one. This function sorts and deduplicates the array of keys, preserving the
-- last value associated with each key. The argument arrays may not be
-- reused after being passed to this function.
--
-- This is by far the fastest way to create a map, since the functions backing it
-- are aggressively specialized. It internally uses a hybrid of mergesort and
-- insertion sort provided by the @primitive-sort@ package. It generates much
-- less garbage than any of the @fromList@ variants. 
unsafeFreezeZip :: (Ord k, Prim k, Prim v)
  => MutablePrimArray s k
  -> MutablePrimArray s v
  -> ST s (Map k v)
unsafeFreezeZip :: forall k v s.
(Ord k, Prim k, Prim v) =>
MutablePrimArray s k -> MutablePrimArray s v -> ST s (Map k v)
unsafeFreezeZip MutablePrimArray s k
keys MutablePrimArray s v
vals = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k v. Map PrimArray PrimArray k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v s.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Mutable karr s k -> Mutable varr s v -> ST s (Map karr varr k v)
I.unsafeFreezeZip MutablePrimArray s k
keys MutablePrimArray s v
vals)