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

{-# OPTIONS_GHC -O2 #-}
module Data.Map.Unboxed.Unlifted
  ( Map
  , empty
  , singleton
  , lookup
  , size
    -- * Transform
  , map
  , mapLifted
  , mapMaybe
  , mapMaybeP
  , mapMaybeWithKey
  , adjustMany
    -- * Folds
  , foldlWithKey'
  , foldrWithKey'
  , foldMapWithKey
  , foldMapWithKey'
    -- * Monadic Folds
  , foldlWithKeyM'
  , foldrWithKeyM'
  , foldlMapWithKeyM'
  , foldrMapWithKeyM'
    -- * Traversals
  , traverse
  , traverseWithKey
  , traverseWithKey_
    -- * List Conversion
  , 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,MutablePrimArray)
import Data.Primitive.Types (Prim)
import Data.Primitive.Unlifted.Array (UnliftedArray,MutableUnliftedArray)
import Data.Primitive.Unlifted.Class (PrimUnlifted)
import Data.Semigroup (Semigroup)
import Data.Set.Unboxed.Internal (Set(..))

import qualified Data.Map.Unboxed.Lifted as MUL
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 UnliftedArray k v)

instance (Prim k, Ord k, PrimUnlifted v, Semigroup v) => Semigroup (Map k v) where
  Map Map PrimArray UnliftedArray k v
x <> :: Map k v -> Map k v -> Map k v
<> Map Map PrimArray UnliftedArray k v
y = forall k v. Map PrimArray UnliftedArray 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 UnliftedArray k v
x Map PrimArray UnliftedArray k v
y)

instance (Prim k, Ord k, PrimUnlifted v, Semigroup v) => Monoid (Map k v) where
  mempty :: Map k v
mempty = forall k v. Map PrimArray UnliftedArray 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 UnliftedArray 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, PrimUnlifted v, Eq v) => Eq (Map k v) where
  Map Map PrimArray UnliftedArray k v
x == :: Map k v -> Map k v -> Bool
== Map Map PrimArray UnliftedArray 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 UnliftedArray k v
x Map PrimArray UnliftedArray k v
y

instance (Prim k, Ord k, PrimUnlifted v, Ord v) => Ord (Map k v) where
  compare :: Map k v -> Map k v -> Ordering
compare (Map Map PrimArray UnliftedArray k v
x) (Map Map PrimArray UnliftedArray 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 UnliftedArray k v
x Map PrimArray UnliftedArray k v
y

instance (Prim k, Ord k, PrimUnlifted 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 UnliftedArray 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 UnliftedArray 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 UnliftedArray 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 UnliftedArray k v
s

instance (Prim k, Show k, PrimUnlifted v, Show v) => Show (Map k v) where
  showsPrec :: Int -> Map k v -> ShowS
showsPrec Int
p (Map Map PrimArray UnliftedArray 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 UnliftedArray k v
s

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

-- | /O(log n)/ Lookup the value at a key in the map.
lookup :: (Prim k, Ord k, PrimUnlifted v) => k -> Map k v -> Maybe v
lookup :: forall k v.
(Prim k, Ord k, PrimUnlifted v) =>
k -> Map k v -> Maybe v
lookup k
a (Map Map PrimArray UnliftedArray 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 UnliftedArray k v
s

-- | /O(1)/ Create a map with a single element.
singleton :: (Prim k, PrimUnlifted v) => k -> v -> Map k v
singleton :: forall k v. (Prim k, PrimUnlifted v) => k -> v -> Map k v
singleton k
k v
v = forall k v. Map PrimArray UnliftedArray 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*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, PrimUnlifted v) => [(k,v)] -> Map k v
fromList :: forall k v. (Prim k, Ord k, PrimUnlifted v) => [(k, v)] -> Map k v
fromList = forall k v. Map PrimArray UnliftedArray 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, PrimUnlifted v)
  => Int -- ^ expected size of resulting 'Map'
  -> [(k,v)] -- ^ key-value pairs
  -> Map k v
fromListN :: forall k v.
(Prim k, Ord k, PrimUnlifted v) =>
Int -> [(k, v)] -> Map k v
fromListN Int
n = forall k v. Map PrimArray UnliftedArray 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, PrimUnlifted v, Semigroup v) => [(k,v)] -> Map k v
fromListAppend :: forall k v.
(Prim k, Ord k, PrimUnlifted v, Semigroup v) =>
[(k, v)] -> Map k v
fromListAppend = forall k v. Map PrimArray UnliftedArray 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, PrimUnlifted 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, PrimUnlifted v, Semigroup v) =>
Int -> [(k, v)] -> Map k v
fromListAppendN Int
n = forall k v. Map PrimArray UnliftedArray 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, PrimUnlifted v)
  => (k -> v)
  -> Set k
  -> Map k v
{-# INLINE fromSet #-}
fromSet :: forall k v.
(Prim k, PrimUnlifted v) =>
(k -> v) -> Set k -> Map k v
fromSet k -> v
f (Set Set PrimArray k
s) = forall k v. Map PrimArray UnliftedArray 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, PrimUnlifted v)
  => (k -> m v)
  -> Set k
  -> m (Map k v)
{-# INLINE fromSetP #-}
fromSetP :: forall (m :: * -> *) k v.
(PrimMonad m, Prim k, PrimUnlifted 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 UnliftedArray 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 :: PrimUnlifted v => Map k v -> Int
size :: forall v k. PrimUnlifted v => Map k v -> Int
size (Map Map PrimArray UnliftedArray k v
m) = forall (varr :: * -> *) v (karr :: * -> *) k.
(ContiguousU varr, Element varr v) =>
Map karr varr k v -> Int
I.size Map PrimArray UnliftedArray k v
m

-- | /O(n)/ Map over the values in the map.
map :: (Prim k, PrimUnlifted v, PrimUnlifted w)
  => (v -> w)
  -> Map k v
  -> Map k w
map :: forall k v w.
(Prim k, PrimUnlifted v, PrimUnlifted w) =>
(v -> w) -> Map k v -> Map k w
map v -> w
f (Map Map PrimArray UnliftedArray k v
m) = forall k v. Map PrimArray UnliftedArray 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 UnliftedArray k v
m)

-- | /O(n)/ Map over the values in the map. The resulting map contains
--   lifted values.
mapLifted :: (Prim k, PrimUnlifted v)
  => (v -> w)
  -> Map k v
  -> MUL.Map k w
mapLifted :: forall k v w.
(Prim k, PrimUnlifted v) =>
(v -> w) -> Map k v -> Map k w
mapLifted v -> w
f (Map Map PrimArray UnliftedArray k v
m) = forall k v. Map PrimArray Array k v -> Map k v
MUL.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 UnliftedArray k v
m)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
mapMaybe :: (Prim k, PrimUnlifted v, PrimUnlifted w)
  => (v -> Maybe w)
  -> Map k v
  -> Map k w
{-# INLINE mapMaybe #-}
mapMaybe :: forall k v w.
(Prim k, PrimUnlifted v, PrimUnlifted w) =>
(v -> Maybe w) -> Map k v -> Map k w
mapMaybe v -> Maybe w
f (Map Map PrimArray UnliftedArray k v
m) = forall k v. Map PrimArray UnliftedArray 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 UnliftedArray k v
m)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
mapMaybeP :: (PrimMonad m, Prim k, PrimUnlifted v, PrimUnlifted w)
  => (v -> m (Maybe w))
  -> Map k v
  -> m (Map k w)
{-# INLINE mapMaybeP #-}
mapMaybeP :: forall (m :: * -> *) k v w.
(PrimMonad m, Prim k, PrimUnlifted v, PrimUnlifted w) =>
(v -> m (Maybe w)) -> Map k v -> m (Map k w)
mapMaybeP v -> m (Maybe w)
f (Map Map PrimArray UnliftedArray k v
m) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k v. Map PrimArray UnliftedArray k v -> Map k v
Map (forall (karr :: * -> *) (varr :: * -> *) (m :: * -> *) k v w.
(PrimMonad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(v -> m (Maybe w)) -> Map karr varr k v -> m (Map karr varr k w)
I.mapMaybeP v -> m (Maybe w)
f Map PrimArray UnliftedArray k v
m)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
-- The predicate is given access to the key.
mapMaybeWithKey :: (Prim k, PrimUnlifted v, PrimUnlifted w)
  => (k -> v -> Maybe w)
  -> Map k v
  -> Map k w
mapMaybeWithKey :: forall k v w.
(Prim k, PrimUnlifted v, PrimUnlifted w) =>
(k -> v -> Maybe w) -> Map k v -> Map k w
mapMaybeWithKey k -> v -> Maybe w
f (Map Map PrimArray UnliftedArray k v
m) = forall k v. Map PrimArray UnliftedArray 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 UnliftedArray 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, PrimUnlifted v, PrimMonad m, Ord k)
  => ((k -> (v -> m v) -> m ()) -> m a) -- ^ Modification-applying function
  -> Map k v -- ^ Map
  -> m (Map k v, a)
adjustMany :: forall k v (m :: * -> *) a.
(Prim k, PrimUnlifted 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 UnliftedArray k v
m) = do
  (Map PrimArray UnliftedArray 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 UnliftedArray k v
m
  forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall k v. Map PrimArray UnliftedArray k v -> Map k v
Map Map PrimArray UnliftedArray 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, PrimUnlifted 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, PrimUnlifted v) =>
(b -> k -> v -> m b) -> b -> Map k v -> m b
foldlWithKeyM' b -> k -> v -> m b
f b
b0 (Map Map PrimArray UnliftedArray 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 UnliftedArray 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, PrimUnlifted 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, PrimUnlifted v) =>
(k -> v -> b -> m b) -> b -> Map k v -> m b
foldrWithKeyM' k -> v -> b -> m b
f b
b0 (Map Map PrimArray UnliftedArray 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 UnliftedArray 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, PrimUnlifted v)
  => (k -> v -> m b) -- ^ reduction
  -> Map k v -- ^ map
  -> m b
foldlMapWithKeyM' :: forall (m :: * -> *) b k v.
(Monad m, Monoid b, Prim k, PrimUnlifted v) =>
(k -> v -> m b) -> Map k v -> m b
foldlMapWithKeyM' k -> v -> m b
f (Map Map PrimArray UnliftedArray 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 UnliftedArray 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, PrimUnlifted v)
  => (k -> v -> m b) -- ^ reduction
  -> Map k v -- ^ map
  -> m b
foldrMapWithKeyM' :: forall (m :: * -> *) b k v.
(Monad m, Monoid b, Prim k, PrimUnlifted v) =>
(k -> v -> m b) -> Map k v -> m b
foldrMapWithKeyM' k -> v -> m b
f (Map Map PrimArray UnliftedArray 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 UnliftedArray k v
m

-- | /O(n)/ Traverse the values of the map.
traverse :: (Applicative m, Prim k, PrimUnlifted v, PrimUnlifted b)
  => (v -> m b)
  -> Map k v
  -> m (Map k b)
traverse :: forall (m :: * -> *) k v b.
(Applicative m, Prim k, PrimUnlifted v, PrimUnlifted b) =>
(v -> m b) -> Map k v -> m (Map k b)
traverse v -> m b
f (Map Map PrimArray UnliftedArray k v
m) = forall k v. Map PrimArray UnliftedArray 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 -> m b
f Map PrimArray UnliftedArray k v
m)

-- | /O(n)/ traversal over the values in the map, using the keys.
traverseWithKey :: (Applicative f, Prim k, PrimUnlifted v, PrimUnlifted b)
  => (k -> v -> f b)
  -> Map k v
  -> f (Map k b)
traverseWithKey :: forall (f :: * -> *) k v b.
(Applicative f, Prim k, PrimUnlifted v, PrimUnlifted b) =>
(k -> v -> f b) -> Map k v -> f (Map k b)
traverseWithKey k -> v -> f b
f (Map Map PrimArray UnliftedArray k v
m) = forall k v. Map PrimArray UnliftedArray 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 UnliftedArray k v
m

-- | /O(n)/ Traverse the keys and values of the map from left to right.
traverseWithKey_ :: (Monad m, Prim k, PrimUnlifted v)
  => (k -> v -> m b) -- ^ reduction
  -> Map k v -- ^ map
  -> m ()
traverseWithKey_ :: forall (m :: * -> *) k v b.
(Monad m, Prim k, PrimUnlifted v) =>
(k -> v -> m b) -> Map k v -> m ()
traverseWithKey_ k -> v -> m b
f (Map Map PrimArray UnliftedArray 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 UnliftedArray k v
m


-- | /O(n)/ Fold over the keys and values of the map with a 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, PrimUnlifted v)
  => (k -> v -> b) -- ^ reduction 
  -> Map k v -- ^ map
  -> b
foldMapWithKey :: forall b k v.
(Monoid b, Prim k, PrimUnlifted v) =>
(k -> v -> b) -> Map k v -> b
foldMapWithKey k -> v -> b
f (Map Map PrimArray UnliftedArray k v
m) = forall (karr :: * -> *) k (varr :: * -> *) 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 UnliftedArray 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, PrimUnlifted v)
  => (k -> v -> b) -- ^ reduction 
  -> Map k v -- ^ map
  -> b
foldMapWithKey' :: forall b k v.
(Monoid b, Prim k, PrimUnlifted v) =>
(k -> v -> b) -> Map k v -> b
foldMapWithKey' k -> v -> b
f (Map Map PrimArray UnliftedArray 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 UnliftedArray k v
m

-- | /O(n)/ Left fold over the keys and values with a strict accumulator.
foldlWithKey' :: (Prim k, PrimUnlifted v)
  => (b -> k -> v -> b) -- ^ reduction
  -> b -- ^ initial accumulator
  -> Map k v -- ^ map
  -> b
foldlWithKey' :: forall k v b.
(Prim k, PrimUnlifted v) =>
(b -> k -> v -> b) -> b -> Map k v -> b
foldlWithKey' b -> k -> v -> b
f b
b0 (Map Map PrimArray UnliftedArray 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 UnliftedArray k v
m

-- | /O(n)/ Right fold over the keys and values with a strict accumulator.
foldrWithKey' :: (Prim k, PrimUnlifted v)
  => (k -> v -> b -> b) -- ^ reduction
  -> b -- ^ initial accumulator
  -> Map k v -- ^ map
  -> b
foldrWithKey' :: forall k v b.
(Prim k, PrimUnlifted v) =>
(k -> v -> b -> b) -> b -> Map k v -> b
foldrWithKey' k -> v -> b -> b
f b
b0 (Map Map PrimArray UnliftedArray 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 UnliftedArray 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, PrimUnlifted v)
  => MutablePrimArray s k
  -> MutableUnliftedArray s v
  -> ST s (Map k v)
unsafeFreezeZip :: forall k v s.
(Ord k, Prim k, PrimUnlifted v) =>
MutablePrimArray s k -> MutableUnliftedArray s v -> ST s (Map k v)
unsafeFreezeZip MutablePrimArray s k
keys MutableUnliftedArray s v
vals = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k v. Map PrimArray UnliftedArray 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 MutableUnliftedArray s v
vals)