-- File created: 2008-11-07 17:30:16

{-# LANGUAGE CPP, MultiParamTypeClasses, FlexibleInstances #-}

module Data.ListTrie.Base.Map
   ( Map(..), OrdMap(..)
   , AList, WrappedIntMap
   ) where

import Control.Arrow       ((***), first, second)
import Control.Monad       (liftM, liftM2)
import Data.Foldable       (Foldable(..))
import Data.Function       (on)
import Data.List           (foldl1', mapAccumL, nubBy, partition, sort, sortBy)
import Data.Ord            (comparing)
import Data.Traversable    (Traversable(..), mapAccumR)
import qualified Data.IntMap     as IM
import qualified Data.Map        as M
#if MIN_VERSION_containers(0,5,0)
import qualified Data.Map.Strict as M.Strict
#endif
import Prelude hiding ( filter, foldl, foldl1, foldr, foldr1, lookup, null
                      , mapM, sequence
                      )
import qualified Prelude

import Data.ListTrie.Util (both, (.:))

-- | Minimal complete implementation:
--
-- * 'eqCmp'
--
-- * 'null'
--
-- * 'lookup'
--
-- * 'alter'
--
-- * 'unionWithKey', 'differenceWithKey', 'intersectionWithKey'
--
-- * 'toListKV'
--
-- * 'empty' or 'fromList' or 'fromListWith'
--
-- * 'isSubmapOfBy'
--
-- For decent performance, supplying at least 'mapAccumWithKey' and 'filter' as
-- well is probably a good idea.
class Foldable (m k) => Map m k where
   -- | Like an 'Eq' instance over k, but should compare on the same type as
   -- @m@ does. In most cases this can be defined just as @const (==)@.
   eqCmp :: m k a -> k -> k -> Bool

   empty     ::                     m k a
   singleton ::           k -> a -> m k a
   -- | Precondition: the two keys differ
   doubleton :: k -> a -> k -> a -> m k a

   null   ::      m k a -> Bool
   lookup :: k -> m k a -> Maybe a

   -- | Strictness can be whatever is more optimal for the map type, shouldn't
   -- matter
   insertWith :: (a -> a -> a) -> k -> a -> m k a -> m k a
   insert     ::                  k -> a -> m k a -> m k a

   update :: (a -> Maybe a) -> k -> m k a -> m k a
   adjust :: (a -> a)       -> k -> m k a -> m k a
   delete ::                   k -> m k a -> m k a

   alter :: (Maybe a -> Maybe a) -> k -> m k a -> m k a

   unionWith           ::      (a -> a -> a)       -> m k a -> m k a -> m k a
   differenceWith      ::      (a -> b -> Maybe a) -> m k a -> m k b -> m k a
   intersectionWith    ::      (a -> b -> c)       -> m k a -> m k b -> m k c
   unionWithKey        :: (k -> a -> a -> a)       -> m k a -> m k a -> m k a
   differenceWithKey   :: (k -> a -> b -> Maybe a) -> m k a -> m k b -> m k a
   intersectionWithKey :: (k -> a -> b -> c)       -> m k a -> m k b -> m k c

   map             ::      (a -> b) -> m k a -> m k b
   mapWithKey      :: (k -> a -> b) -> m k a -> m k b
   mapAccum        :: (a ->      b -> (a,c)) -> a -> m k b -> (a, m k c)
   mapAccumWithKey :: (a -> k -> b -> (a,c)) -> a -> m k b -> (a, m k c)

   filter :: (a -> Bool) -> m k a -> m k a

   toListKV       :: m k a -> [(k,a)]
   fromListKV     ::                  [(k,a)] -> m k a
   fromListKVWith :: (a -> a -> a) -> [(k,a)] -> m k a

   serializeToList     :: m k a -> [(k,a)]
   deserializeFromList :: [(k,a)] -> m k a

   isSubmapOfBy :: (a -> b -> Bool) -> m k a -> m k b -> Bool

   singletonView :: m k a -> Maybe (k,a)

   empty         = [(k, a)] -> m k a
forall a. [(k, a)] -> m k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
fromListKV []
   singleton k
k a
v = k -> a -> m k a -> m k a
forall a. k -> a -> m k a -> m k a
forall (m :: * -> * -> *) k a. Map m k => k -> a -> m k a -> m k a
insert k
k a
v m k a
forall a. m k a
forall (m :: * -> * -> *) k a. Map m k => m k a
empty
   doubleton k
k a
v = k -> a -> m k a -> m k a
forall a. k -> a -> m k a -> m k a
forall (m :: * -> * -> *) k a. Map m k => k -> a -> m k a -> m k a
insert k
k a
v (m k a -> m k a) -> (k -> a -> m k a) -> k -> a -> m k a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: k -> a -> m k a
forall a. k -> a -> m k a
forall (m :: * -> * -> *) k a. Map m k => k -> a -> m k a
singleton

   insert           = (a -> a -> a) -> k -> a -> m k a -> m k a
forall a. (a -> a -> a) -> k -> a -> m k a -> m k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> a -> a) -> k -> a -> m k a -> m k a
insertWith a -> a -> a
forall a b. a -> b -> a
const
   insertWith a -> a -> a
f k
k a
v = (Maybe a -> Maybe a) -> k -> m k a -> m k a
forall a. (Maybe a -> Maybe a) -> k -> m k a -> m k a
forall (m :: * -> * -> *) k a.
Map m k =>
(Maybe a -> Maybe a) -> k -> m k a -> m k a
alter (\Maybe a
mold -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$ case Maybe a
mold of
                                                    Maybe a
Nothing  -> a
v
                                                    Just a
old -> a -> a -> a
f a
v a
old)
                            k
k

   adjust a -> a
f = (a -> Maybe a) -> k -> m k a -> m k a
forall a. (a -> Maybe a) -> k -> m k a -> m k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> Maybe a) -> k -> m k a -> m k a
update (a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> (a -> a) -> a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
f)
   delete   = (a -> Maybe a) -> k -> m k a -> m k a
forall a. (a -> Maybe a) -> k -> m k a -> m k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> Maybe a) -> k -> m k a -> m k a
update (Maybe a -> a -> Maybe a
forall a b. a -> b -> a
const Maybe a
forall a. Maybe a
Nothing)
   update a -> Maybe a
f = (Maybe a -> Maybe a) -> k -> m k a -> m k a
forall a. (Maybe a -> Maybe a) -> k -> m k a -> m k a
forall (m :: * -> * -> *) k a.
Map m k =>
(Maybe a -> Maybe a) -> k -> m k a -> m k a
alter  (a -> Maybe a
f (a -> Maybe a) -> Maybe a -> Maybe a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<<)

   unionWith        = (k -> a -> a -> a) -> m k a -> m k a -> m k a
forall a. (k -> a -> a -> a) -> m k a -> m k a -> m k a
forall (m :: * -> * -> *) k a.
Map m k =>
(k -> a -> a -> a) -> m k a -> m k a -> m k a
unionWithKey        ((k -> a -> a -> a) -> m k a -> m k a -> m k a)
-> ((a -> a -> a) -> k -> a -> a -> a)
-> (a -> a -> a)
-> m k a
-> m k a
-> m k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> k -> a -> a -> a
forall a b. a -> b -> a
const
   differenceWith   = (k -> a -> b -> Maybe a) -> m k a -> m k b -> m k a
forall a b. (k -> a -> b -> Maybe a) -> m k a -> m k b -> m k a
forall (m :: * -> * -> *) k a b.
Map m k =>
(k -> a -> b -> Maybe a) -> m k a -> m k b -> m k a
differenceWithKey   ((k -> a -> b -> Maybe a) -> m k a -> m k b -> m k a)
-> ((a -> b -> Maybe a) -> k -> a -> b -> Maybe a)
-> (a -> b -> Maybe a)
-> m k a
-> m k b
-> m k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> Maybe a) -> k -> a -> b -> Maybe a
forall a b. a -> b -> a
const
   intersectionWith = (k -> a -> b -> c) -> m k a -> m k b -> m k c
forall a b c. (k -> a -> b -> c) -> m k a -> m k b -> m k c
forall (m :: * -> * -> *) k a b c.
Map m k =>
(k -> a -> b -> c) -> m k a -> m k b -> m k c
intersectionWithKey ((k -> a -> b -> c) -> m k a -> m k b -> m k c)
-> ((a -> b -> c) -> k -> a -> b -> c)
-> (a -> b -> c)
-> m k a
-> m k b
-> m k c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> c) -> k -> a -> b -> c
forall a b. a -> b -> a
const

   map                 = (k -> a -> b) -> m k a -> m k b
forall a b. (k -> a -> b) -> m k a -> m k b
forall (m :: * -> * -> *) k a b.
Map m k =>
(k -> a -> b) -> m k a -> m k b
mapWithKey ((k -> a -> b) -> m k a -> m k b)
-> ((a -> b) -> k -> a -> b) -> (a -> b) -> m k a -> m k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> k -> a -> b
forall a b. a -> b -> a
const
   mapWithKey      k -> a -> b
f   = ((), m k b) -> m k b
forall a b. (a, b) -> b
snd (((), m k b) -> m k b) -> (m k a -> ((), m k b)) -> m k a -> m k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (() -> k -> a -> ((), b)) -> () -> m k a -> ((), m k b)
forall a b c. (a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
forall (m :: * -> * -> *) k a b c.
Map m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
mapAccumWithKey (\()
_ k
k a
v -> ((), k -> a -> b
f k
k a
v)) ()
   mapAccum        a -> b -> (a, c)
f   = (a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
forall a b c. (a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
forall (m :: * -> * -> *) k a b c.
Map m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
mapAccumWithKey ((b -> (a, c)) -> k -> b -> (a, c)
forall a b. a -> b -> a
const ((b -> (a, c)) -> k -> b -> (a, c))
-> (a -> b -> (a, c)) -> a -> k -> b -> (a, c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b -> (a, c)
f)
   mapAccumWithKey a -> k -> b -> (a, c)
f a
z =
      ([(k, c)] -> m k c) -> (a, [(k, c)]) -> (a, m k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second [(k, c)] -> m k c
forall a. [(k, a)] -> m k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
fromListKV ((a, [(k, c)]) -> (a, m k c))
-> (m k b -> (a, [(k, c)])) -> m k b -> (a, m k c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
         (a -> (k, b) -> (a, (k, c))) -> a -> [(k, b)] -> (a, [(k, c)])
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL (\a
a (k
k,b
v) -> (c -> (k, c)) -> (a, c) -> (a, (k, c))
forall a b. (a -> b) -> (a, a) -> (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((,) k
k) (a -> k -> b -> (a, c)
f a
a k
k b
v)) a
z ([(k, b)] -> (a, [(k, c)]))
-> (m k b -> [(k, b)]) -> m k b -> (a, [(k, c)])
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
      m k b -> [(k, b)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
toListKV

   filter a -> Bool
p = [(k, a)] -> m k a
forall a. [(k, a)] -> m k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
fromListKV ([(k, a)] -> m k a) -> (m k a -> [(k, a)]) -> m k a -> m k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, a) -> Bool) -> [(k, a)] -> [(k, a)]
forall a. (a -> Bool) -> [a] -> [a]
Prelude.filter (a -> Bool
p (a -> Bool) -> ((k, a) -> a) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, a) -> a
forall a b. (a, b) -> b
snd) ([(k, a)] -> [(k, a)]) -> (m k a -> [(k, a)]) -> m k a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m k a -> [(k, a)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
toListKV

   -- | Should be strict in the keys
   fromListKV       = (a -> a -> a) -> [(k, a)] -> m k a
forall a. (a -> a -> a) -> [(k, a)] -> m k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> a -> a) -> [(k, a)] -> m k a
fromListKVWith a -> a -> a
forall a b. a -> b -> a
const
   fromListKVWith a -> a -> a
f = ((k, a) -> m k a -> m k a) -> m k a -> [(k, a)] -> m k a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((k -> a -> m k a -> m k a) -> (k, a) -> m k a -> m k a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((k -> a -> m k a -> m k a) -> (k, a) -> m k a -> m k a)
-> (k -> a -> m k a -> m k a) -> (k, a) -> m k a -> m k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> a) -> k -> a -> m k a -> m k a
forall a. (a -> a -> a) -> k -> a -> m k a -> m k a
forall (m :: * -> * -> *) k a.
Map m k =>
(a -> a -> a) -> k -> a -> m k a -> m k a
insertWith a -> a -> a
f) m k a
forall a. m k a
forall (m :: * -> * -> *) k a. Map m k => m k a
empty

   serializeToList     = m k a -> [(k, a)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
toListKV
   deserializeFromList = [(k, a)] -> m k a
forall a. [(k, a)] -> m k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
fromListKV

   singletonView m k a
m =
      case m k a -> [(k, a)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
toListKV m k a
m of
           [(k, a)
x] -> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k, a)
x
           [(k, a)]
_   -> Maybe (k, a)
forall a. Maybe a
Nothing

-- |  Minimal complete definition:
--
-- * 'ordCmp'
--
-- * 'toAscList' or 'toDescList'
--
-- * 'splitLookup'
--
-- For decent performance, supplying at least the following is probably a good
-- idea:
--
-- * 'minViewWithKey', 'maxViewWithKey'
--
-- * 'mapAccumAscWithKey', 'mapAccumDescWithKey'
class Map m k => OrdMap m k where
   -- | Like an Ord instance over k, but should compare on the same type as @m@
   -- does. In most cases this can be defined just as @const compare@.
   ordCmp :: m k a -> k -> k -> Ordering

   toAscList            :: m k a -> [(k,a)]
   toDescList           :: m k a -> [(k,a)]

   splitLookup :: k -> m k a -> (m k a, Maybe a, m k a)
   split       :: k -> m k a -> (m k a,          m k a)

   minViewWithKey :: m k a -> (Maybe (k,a), m k a)
   maxViewWithKey :: m k a -> (Maybe (k,a), m k a)

   findPredecessor :: k -> m k a -> Maybe (k,a)
   findSuccessor   :: k -> m k a -> Maybe (k,a)

   mapAccumAsc         :: (a ->      b -> (a,c)) -> a -> m k b -> (a, m k c)
   mapAccumAscWithKey  :: (a -> k -> b -> (a,c)) -> a -> m k b -> (a, m k c)
   mapAccumDesc        :: (a ->      b -> (a,c)) -> a -> m k b -> (a, m k c)
   mapAccumDescWithKey :: (a -> k -> b -> (a,c)) -> a -> m k b -> (a, m k c)

   toAscList  = [(k, a)] -> [(k, a)]
forall a. [a] -> [a]
reverse ([(k, a)] -> [(k, a)]) -> (m k a -> [(k, a)]) -> m k a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m k a -> [(k, a)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. OrdMap m k => m k a -> [(k, a)]
toDescList
   toDescList = [(k, a)] -> [(k, a)]
forall a. [a] -> [a]
reverse ([(k, a)] -> [(k, a)]) -> (m k a -> [(k, a)]) -> m k a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m k a -> [(k, a)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. OrdMap m k => m k a -> [(k, a)]
toAscList

   split k
m m k a
k = let (m k a
a,Maybe a
_,m k a
b) = k -> m k a -> (m k a, Maybe a, m k a)
forall a. k -> m k a -> (m k a, Maybe a, m k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
k -> m k a -> (m k a, Maybe a, m k a)
splitLookup k
m m k a
k in (m k a
a,m k a
b)

   minViewWithKey m k a
m =
      case m k a -> [(k, a)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. OrdMap m k => m k a -> [(k, a)]
toAscList m k a
m of
           []     -> (Maybe (k, a)
forall a. Maybe a
Nothing, m k a
m)
           ((k, a)
x:[(k, a)]
xs) -> ((k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k, a)
x, [(k, a)] -> m k a
forall a. [(k, a)] -> m k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
fromListKV [(k, a)]
xs)

   maxViewWithKey m k a
m =
      case m k a -> [(k, a)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. OrdMap m k => m k a -> [(k, a)]
toDescList m k a
m of
           []     -> (Maybe (k, a)
forall a. Maybe a
Nothing, m k a
m)
           ((k, a)
x:[(k, a)]
xs) -> ((k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k, a)
x, [(k, a)] -> m k a
forall a. [(k, a)] -> m k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
fromListKV [(k, a)]
xs)

   findPredecessor k
m = (Maybe (k, a), m k a) -> Maybe (k, a)
forall a b. (a, b) -> a
fst ((Maybe (k, a), m k a) -> Maybe (k, a))
-> (m k a -> (Maybe (k, a), m k a)) -> m k a -> Maybe (k, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m k a -> (Maybe (k, a), m k a)
forall a. m k a -> (Maybe (k, a), m k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
m k a -> (Maybe (k, a), m k a)
maxViewWithKey (m k a -> (Maybe (k, a), m k a))
-> (m k a -> m k a) -> m k a -> (Maybe (k, a), m k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (m k a, m k a) -> m k a
forall a b. (a, b) -> a
fst ((m k a, m k a) -> m k a)
-> (m k a -> (m k a, m k a)) -> m k a -> m k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> m k a -> (m k a, m k a)
forall a. k -> m k a -> (m k a, m k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
k -> m k a -> (m k a, m k a)
split k
m
   findSuccessor   k
m = (Maybe (k, a), m k a) -> Maybe (k, a)
forall a b. (a, b) -> a
fst ((Maybe (k, a), m k a) -> Maybe (k, a))
-> (m k a -> (Maybe (k, a), m k a)) -> m k a -> Maybe (k, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. m k a -> (Maybe (k, a), m k a)
forall a. m k a -> (Maybe (k, a), m k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
m k a -> (Maybe (k, a), m k a)
minViewWithKey (m k a -> (Maybe (k, a), m k a))
-> (m k a -> m k a) -> m k a -> (Maybe (k, a), m k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (m k a, m k a) -> m k a
forall a b. (a, b) -> b
snd ((m k a, m k a) -> m k a)
-> (m k a -> (m k a, m k a)) -> m k a -> m k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> m k a -> (m k a, m k a)
forall a. k -> m k a -> (m k a, m k a)
forall (m :: * -> * -> *) k a.
OrdMap m k =>
k -> m k a -> (m k a, m k a)
split k
m

   mapAccumAsc  a -> b -> (a, c)
f = (a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
forall a b c. (a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
mapAccumAscWithKey  ((b -> (a, c)) -> k -> b -> (a, c)
forall a b. a -> b -> a
const ((b -> (a, c)) -> k -> b -> (a, c))
-> (a -> b -> (a, c)) -> a -> k -> b -> (a, c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b -> (a, c)
f)
   mapAccumDesc a -> b -> (a, c)
f = (a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
forall a b c. (a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
mapAccumDescWithKey ((b -> (a, c)) -> k -> b -> (a, c)
forall a b. a -> b -> a
const ((b -> (a, c)) -> k -> b -> (a, c))
-> (a -> b -> (a, c)) -> a -> k -> b -> (a, c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b -> (a, c)
f)
   mapAccumAscWithKey a -> k -> b -> (a, c)
f a
z =
      ([(k, c)] -> m k c) -> (a, [(k, c)]) -> (a, m k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second [(k, c)] -> m k c
forall a. [(k, a)] -> m k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
fromListKV ((a, [(k, c)]) -> (a, m k c))
-> (m k b -> (a, [(k, c)])) -> m k b -> (a, m k c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
         (a -> (k, b) -> (a, (k, c))) -> a -> [(k, b)] -> (a, [(k, c)])
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL (\a
a (k
k,b
v) -> (c -> (k, c)) -> (a, c) -> (a, (k, c))
forall a b. (a -> b) -> (a, a) -> (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((,) k
k) (a -> k -> b -> (a, c)
f a
a k
k b
v)) a
z ([(k, b)] -> (a, [(k, c)]))
-> (m k b -> [(k, b)]) -> m k b -> (a, [(k, c)])
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
      m k b -> [(k, b)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. OrdMap m k => m k a -> [(k, a)]
toAscList
   mapAccumDescWithKey a -> k -> b -> (a, c)
f a
z =
      ([(k, c)] -> m k c) -> (a, [(k, c)]) -> (a, m k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second [(k, c)] -> m k c
forall a. [(k, a)] -> m k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
fromListKV ((a, [(k, c)]) -> (a, m k c))
-> (m k b -> (a, [(k, c)])) -> m k b -> (a, m k c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
         (a -> (k, b) -> (a, (k, c))) -> a -> [(k, b)] -> (a, [(k, c)])
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL (\a
a (k
k,b
v) -> (c -> (k, c)) -> (a, c) -> (a, (k, c))
forall a b. (a -> b) -> (a, a) -> (a, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((,) k
k) (a -> k -> b -> (a, c)
f a
a k
k b
v)) a
z ([(k, b)] -> (a, [(k, c)]))
-> (m k b -> [(k, b)]) -> m k b -> (a, [(k, c)])
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
      m k b -> [(k, b)]
forall a. m k a -> [(k, a)]
forall (m :: * -> * -> *) k a. OrdMap m k => m k a -> [(k, a)]
toDescList

------------- Instances

newtype AList k v = AL [(k,v)]

-- AList has to be ordering-ignorant
instance (Eq k, Eq v) => Eq (AList k v) where
   AL []     == :: AList k v -> AList k v -> Bool
== AL [(k, v)]
ys = [(k, v)] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Prelude.null [(k, v)]
ys
   AL ((k, v)
x:[(k, v)]
xs) == AL [(k, v)]
ys =
      let (Maybe (k, v)
my,[(k, v)]
ys') = ((k, v) -> Bool) -> [(k, v)] -> (Maybe (k, v), [(k, v)])
forall a. (a -> Bool) -> [a] -> (Maybe a, [a])
deleteAndGetBy ((k, v) -> (k, v) -> Bool
forall a. Eq a => a -> a -> Bool
==(k, v)
x) [(k, v)]
ys
       in case Maybe (k, v)
my of
               Maybe (k, v)
Nothing -> Bool
False
               Just (k, v)
_  -> [(k, v)] -> AList k v
forall k v. [(k, v)] -> AList k v
AL [(k, v)]
xs AList k v -> AList k v -> Bool
forall a. Eq a => a -> a -> Bool
== [(k, v)] -> AList k v
forall k v. [(k, v)] -> AList k v
AL [(k, v)]
ys'

instance (Ord k, Ord v) => Ord (AList k v) where
   compare :: AList k v -> AList k v -> Ordering
compare (AL [(k, v)]
xs) (AL [(k, v)]
ys) = [(k, v)] -> [(k, v)] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ([(k, v)] -> [(k, v)]
forall a. Ord a => [a] -> [a]
sort [(k, v)]
xs) ([(k, v)] -> [(k, v)]
forall a. Ord a => [a] -> [a]
sort [(k, v)]
ys)

instance Functor (AList k)  where fmap :: forall a b. (a -> b) -> AList k a -> AList k b
fmap a -> b
f (AL [(k, a)]
xs) = [(k, b)] -> AList k b
forall k v. [(k, v)] -> AList k v
AL (((k, a) -> (k, b)) -> [(k, a)] -> [(k, b)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> (k, a) -> (k, b)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second a -> b
f) [(k, a)]
xs)
instance Foldable (AList k) where
    fold :: forall m. Monoid m => AList k m -> m
fold        (AL [(k, m)]
xs) = [m] -> m
forall m. Monoid m => [m] -> m
forall (t :: * -> *) m. (Foldable t, Monoid m) => t m -> m
fold        (((k, m) -> m) -> [(k, m)] -> [m]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (k, m) -> m
forall a b. (a, b) -> b
snd [(k, m)]
xs)
    foldMap :: forall m a. Monoid m => (a -> m) -> AList k a -> m
foldMap a -> m
f   (AL [(k, a)]
xs) = (a -> m) -> [a] -> m
forall m a. Monoid m => (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f   (((k, a) -> a) -> [(k, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (k, a) -> a
forall a b. (a, b) -> b
snd [(k, a)]
xs)
    foldl :: forall b a. (b -> a -> b) -> b -> AList k a -> b
foldl   b -> a -> b
f b
z (AL [(k, a)]
xs) = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl   b -> a -> b
f b
z (((k, a) -> a) -> [(k, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (k, a) -> a
forall a b. (a, b) -> b
snd [(k, a)]
xs)
    foldl1 :: forall a. (a -> a -> a) -> AList k a -> a
foldl1  a -> a -> a
f   (AL [(k, a)]
xs) = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldl1  a -> a -> a
f   (((k, a) -> a) -> [(k, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (k, a) -> a
forall a b. (a, b) -> b
snd [(k, a)]
xs)
    foldr :: forall a b. (a -> b -> b) -> b -> AList k a -> b
foldr   a -> b -> b
f b
z (AL [(k, a)]
xs) = (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr   a -> b -> b
f b
z (((k, a) -> a) -> [(k, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (k, a) -> a
forall a b. (a, b) -> b
snd [(k, a)]
xs)
    foldr1 :: forall a. (a -> a -> a) -> AList k a -> a
foldr1  a -> a -> a
f   (AL [(k, a)]
xs) = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1  a -> a -> a
f   (((k, a) -> a) -> [(k, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (k, a) -> a
forall a b. (a, b) -> b
snd [(k, a)]
xs)

instance Traversable (AList k) where
   traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> AList k a -> f (AList k b)
traverse a -> f b
f (AL [(k, a)]
xs) =
      ([(k, b)] -> AList k b) -> f [(k, b)] -> f (AList k b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [(k, b)] -> AList k b
forall k v. [(k, v)] -> AList k v
AL (f [(k, b)] -> f (AList k b))
-> ([(k, a)] -> f [(k, b)]) -> [(k, a)] -> f (AList k b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, a) -> f (k, b)) -> [(k, a)] -> f [(k, b)]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse (((b -> (k, b)) -> f b -> f (k, b))
-> ((k, f b) -> b -> (k, b))
-> ((k, f b) -> f b)
-> (k, f b)
-> f (k, b)
forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 (b -> (k, b)) -> f b -> f (k, b)
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((,)(k -> b -> (k, b)) -> ((k, f b) -> k) -> (k, f b) -> b -> (k, b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(k, f b) -> k
forall a b. (a, b) -> a
fst) (k, f b) -> f b
forall a b. (a, b) -> b
snd ((k, f b) -> f (k, b))
-> ((k, a) -> (k, f b)) -> (k, a) -> f (k, b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> f b) -> (k, a) -> (k, f b)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second a -> f b
f) ([(k, a)] -> f (AList k b)) -> [(k, a)] -> f (AList k b)
forall a b. (a -> b) -> a -> b
$ [(k, a)]
xs

instance Eq k => Map AList k where
   eqCmp :: forall a. AList k a -> k -> k -> Bool
eqCmp = (k -> k -> Bool) -> AList k a -> k -> k -> Bool
forall a b. a -> b -> a
const k -> k -> Bool
forall a. Eq a => a -> a -> Bool
(==)

   empty :: forall a. AList k a
empty             = [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL []
   singleton :: forall a. k -> a -> AList k a
singleton k
k a
v     = [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL [(k
k,a
v)]
   doubleton :: forall a. k -> a -> k -> a -> AList k a
doubleton k
a a
b k
p a
q = [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL [(k
a,a
b),(k
p,a
q)]

   null :: forall a. AList k a -> Bool
null     (AL [(k, a)]
xs) = [(k, a)] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Prelude.null [(k, a)]
xs
   lookup :: forall a. k -> AList k a -> Maybe a
lookup k
x (AL [(k, a)]
xs) = k -> [(k, a)] -> Maybe a
forall a b. Eq a => a -> [(a, b)] -> Maybe b
Prelude.lookup k
x [(k, a)]
xs

   alter :: forall a. (Maybe a -> Maybe a) -> k -> AList k a -> AList k a
alter Maybe a -> Maybe a
f k
k (AL [(k, a)]
xs) =
      let (Maybe (k, a)
old, [(k, a)]
ys) = ((k, a) -> Bool) -> [(k, a)] -> (Maybe (k, a), [(k, a)])
forall a. (a -> Bool) -> [a] -> (Maybe a, [a])
deleteAndGetBy ((k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k)(k -> Bool) -> ((k, a) -> k) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(k, a) -> k
forall a b. (a, b) -> a
fst) [(k, a)]
xs
       in case Maybe a -> Maybe a
f (((k, a) -> a) -> Maybe (k, a) -> Maybe a
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, a) -> a
forall a b. (a, b) -> b
snd Maybe (k, a)
old) of
               Maybe a
Nothing -> [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL [(k, a)]
ys
               Just a
v  -> [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL ([(k, a)] -> AList k a) -> [(k, a)] -> AList k a
forall a b. (a -> b) -> a -> b
$ (k
k,a
v) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
ys

   delete :: forall a. k -> AList k a -> AList k a
delete k
k (AL [(k, a)]
xs) = [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL([(k, a)] -> AList k a) -> [(k, a)] -> AList k a
forall a b. (a -> b) -> a -> b
$ (k -> (k, a) -> Bool) -> k -> [(k, a)] -> [(k, a)]
forall a b. (a -> b -> Bool) -> a -> [b] -> [b]
deleteBy (\k
a (k
b,a
_) -> k
a k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
b) k
k [(k, a)]
xs

   unionWithKey :: forall a. (k -> a -> a -> a) -> AList k a -> AList k a -> AList k a
unionWithKey k -> a -> a -> a
f (AL [(k, a)]
xs) (AL [(k, a)]
ys) =
      [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL ([(k, a)] -> AList k a)
-> (([(k, a)], [(k, a)]) -> [(k, a)])
-> ([(k, a)], [(k, a)])
-> AList k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([(k, a)] -> [(k, a)] -> [(k, a)])
-> ([(k, a)], [(k, a)]) -> [(k, a)]
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [(k, a)] -> [(k, a)] -> [(k, a)]
forall a. [a] -> [a] -> [a]
(++) (([(k, a)], [(k, a)]) -> AList k a)
-> ([(k, a)], [(k, a)]) -> AList k a
forall a b. (a -> b) -> a -> b
$ ((k, a) -> (k, a) -> Maybe (k, a))
-> ((k, a) -> (k, a) -> Bool)
-> [(k, a)]
-> [(k, a)]
-> ([(k, a)], [(k, a)])
forall a b.
(a -> b -> Maybe a) -> (a -> b -> Bool) -> [a] -> [b] -> ([a], [b])
updateFirstsBy (\(k
k,a
x) (k
_,a
y) -> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k
k, k -> a -> a -> a
f k
k a
x a
y))
                                         (k -> k -> Bool
forall a. Eq a => a -> a -> Bool
(==) (k -> k -> Bool) -> ((k, a) -> k) -> (k, a) -> (k, a) -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (k, a) -> k
forall a b. (a, b) -> a
fst)
                                         [(k, a)]
xs [(k, a)]
ys

   differenceWithKey :: forall a b.
(k -> a -> b -> Maybe a) -> AList k a -> AList k b -> AList k a
differenceWithKey k -> a -> b -> Maybe a
f (AL [(k, a)]
xs) (AL [(k, b)]
ys) =
      [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL ([(k, a)] -> AList k a)
-> (([(k, a)], [(k, b)]) -> [(k, a)])
-> ([(k, a)], [(k, b)])
-> AList k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([(k, a)], [(k, b)]) -> [(k, a)]
forall a b. (a, b) -> a
fst (([(k, a)], [(k, b)]) -> AList k a)
-> ([(k, a)], [(k, b)]) -> AList k a
forall a b. (a -> b) -> a -> b
$ ((k, a) -> (k, b) -> Maybe (k, a))
-> ((k, a) -> (k, b) -> Bool)
-> [(k, a)]
-> [(k, b)]
-> ([(k, a)], [(k, b)])
forall a b.
(a -> b -> Maybe a) -> (a -> b -> Bool) -> [a] -> [b] -> ([a], [b])
updateFirstsBy (\(k
k,a
x) (k
_,b
y) -> (a -> (k, a)) -> Maybe a -> Maybe (k, a)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((,) k
k) (k -> a -> b -> Maybe a
f k
k a
x b
y))
                                (\(k, a)
x (k, b)
y -> (k, a) -> k
forall a b. (a, b) -> a
fst (k, a)
x k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== (k, b) -> k
forall a b. (a, b) -> a
fst (k, b)
y)
                                [(k, a)]
xs [(k, b)]
ys

   intersectionWithKey :: forall a b c.
(k -> a -> b -> c) -> AList k a -> AList k b -> AList k c
intersectionWithKey k -> a -> b -> c
f_ (AL [(k, a)]
xs_) (AL [(k, b)]
ys_) = [(k, c)] -> AList k c
forall k v. [(k, v)] -> AList k v
AL([(k, c)] -> AList k c) -> [(k, c)] -> AList k c
forall a b. (a -> b) -> a -> b
$ (k -> a -> b -> c) -> [(k, a)] -> [(k, b)] -> [(k, c)]
forall {t} {t} {t} {b}.
Eq t =>
(t -> t -> t -> b) -> [(t, t)] -> [(t, t)] -> [(t, b)]
go k -> a -> b -> c
f_ [(k, a)]
xs_ [(k, b)]
ys_
    where
      go :: (t -> t -> t -> b) -> [(t, t)] -> [(t, t)] -> [(t, b)]
go t -> t -> t -> b
_ [] [(t, t)]
_ = []
      go t -> t -> t -> b
f ((t
k,t
x):[(t, t)]
xs) [(t, t)]
ys =
         let (Maybe (t, t)
my,[(t, t)]
ys') = ((t, t) -> Bool) -> [(t, t)] -> (Maybe (t, t), [(t, t)])
forall a. (a -> Bool) -> [a] -> (Maybe a, [a])
deleteAndGetBy ((t -> t -> Bool
forall a. Eq a => a -> a -> Bool
== t
k)(t -> Bool) -> ((t, t) -> t) -> (t, t) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(t, t) -> t
forall a b. (a, b) -> a
fst) [(t, t)]
ys
          in case Maybe (t, t)
my of
                  Just (t
_,t
y) -> (t
k, t -> t -> t -> b
f t
k t
x t
y) (t, b) -> [(t, b)] -> [(t, b)]
forall a. a -> [a] -> [a]
: (t -> t -> t -> b) -> [(t, t)] -> [(t, t)] -> [(t, b)]
go t -> t -> t -> b
f [(t, t)]
xs [(t, t)]
ys'
                  Maybe (t, t)
Nothing    ->                (t -> t -> t -> b) -> [(t, t)] -> [(t, t)] -> [(t, b)]
go t -> t -> t -> b
f [(t, t)]
xs [(t, t)]
ys

   mapWithKey :: forall a b. (k -> a -> b) -> AList k a -> AList k b
mapWithKey k -> a -> b
f (AL [(k, a)]
xs) = [(k, b)] -> AList k b
forall k v. [(k, v)] -> AList k v
AL ([(k, b)] -> AList k b) -> [(k, b)] -> AList k b
forall a b. (a -> b) -> a -> b
$ ((k, a) -> (k, b)) -> [(k, a)] -> [(k, b)]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (\(k
k,a
v) -> (k
k, k -> a -> b
f k
k a
v)) [(k, a)]
xs

   mapAccumWithKey :: forall a b c.
(a -> k -> b -> (a, c)) -> a -> AList k b -> (a, AList k c)
mapAccumWithKey a -> k -> b -> (a, c)
f a
z (AL [(k, b)]
xs) =
      ([(k, c)] -> AList k c) -> (a, [(k, c)]) -> (a, AList k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second [(k, c)] -> AList k c
forall k v. [(k, v)] -> AList k v
AL ((a, [(k, c)]) -> (a, AList k c))
-> (a, [(k, c)]) -> (a, AList k c)
forall a b. (a -> b) -> a -> b
$ (a -> (k, b) -> (a, (k, c))) -> a -> [(k, b)] -> (a, [(k, c)])
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL (\a
a (k
k,b
v) -> let (a
a',c
v') = a -> k -> b -> (a, c)
f a
a k
k b
v
                                          in (a
a', (k
k, c
v')))
                            a
z [(k, b)]
xs

   toListKV :: forall a. AList k a -> [(k, a)]
toListKV (AL [(k, a)]
xs) = [(k, a)]
xs
   fromListKV :: forall a. [(k, a)] -> AList k a
fromListKV       = [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL ([(k, a)] -> AList k a)
-> ([(k, a)] -> [(k, a)]) -> [(k, a)] -> AList k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, a) -> (k, a) -> Bool) -> [(k, a)] -> [(k, a)]
forall a. (a -> a -> Bool) -> [a] -> [a]
nubBy (k -> k -> Bool
forall a. Eq a => a -> a -> Bool
(==) (k -> k -> Bool) -> ((k, a) -> k) -> (k, a) -> (k, a) -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (k, a) -> k
forall a b. (a, b) -> a
fst)
   fromListKVWith :: forall a. (a -> a -> a) -> [(k, a)] -> AList k a
fromListKVWith   = [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL ([(k, a)] -> AList k a)
-> ((a -> a -> a) -> [(k, a)] -> [(k, a)])
-> (a -> a -> a)
-> [(k, a)]
-> AList k a
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: (a -> a -> a) -> [(k, a)] -> [(k, a)]
forall {a} {b}. Eq a => (b -> b -> b) -> [(a, b)] -> [(a, b)]
go
    where
      go :: (b -> b -> b) -> [(a, b)] -> [(a, b)]
go b -> b -> b
_ []     = []
      go b -> b -> b
f ((a, b)
x:[(a, b)]
xs) =
         -- We add some extra strictness here to match the other map types
         -- (strict in key even for singletons) and because we don't need the
         -- laziness (strict in value)
         let ([(a, b)]
as,[(a, b)]
bs) = ((a, b) -> Bool) -> [(a, b)] -> ([(a, b)], [(a, b)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
partition ((a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==) (a -> a -> Bool) -> ((a, b) -> a) -> (a, b) -> (a, b) -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` (a, b) -> a
forall a b. (a, b) -> a
fst) (a, b)
x) [(a, b)]
xs
             v :: b
v       = (b -> b -> b) -> [b] -> b
forall a. HasCallStack => (a -> a -> a) -> [a] -> a
foldl1' b -> b -> b
f ([b] -> b) -> ([(a, b)] -> [b]) -> [(a, b)] -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, b) -> b) -> [(a, b)] -> [b]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (a, b) -> b
forall a b. (a, b) -> b
snd ([(a, b)] -> b) -> [(a, b)] -> b
forall a b. (a -> b) -> a -> b
$ (a, b)
x(a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
:[(a, b)]
as
          in (a, b) -> a
forall a b. (a, b) -> a
fst (a, b)
x a -> [(a, b)] -> [(a, b)]
forall a b. a -> b -> b
`seq` b
v b -> [(a, b)] -> [(a, b)]
forall a b. a -> b -> b
`seq` (((a, b) -> a
forall a b. (a, b) -> a
fst (a, b)
x, b
v) (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: (b -> b -> b) -> [(a, b)] -> [(a, b)]
go b -> b -> b
f [(a, b)]
bs)

   isSubmapOfBy :: forall a b. (a -> b -> Bool) -> AList k a -> AList k b -> Bool
isSubmapOfBy a -> b -> Bool
f_ (AL [(k, a)]
xs_) (AL [(k, b)]
ys_) = (a -> b -> Bool) -> [(k, a)] -> [(k, b)] -> Bool
forall {a} {t} {t}.
Eq a =>
(t -> t -> Bool) -> [(a, t)] -> [(a, t)] -> Bool
go a -> b -> Bool
f_ [(k, a)]
xs_ [(k, b)]
ys_
    where
      go :: (t -> t -> Bool) -> [(a, t)] -> [(a, t)] -> Bool
go t -> t -> Bool
_ []         [(a, t)]
_  = Bool
True
      go t -> t -> Bool
f ((a
k,t
x):[(a, t)]
xs) [(a, t)]
ys =
         let (Maybe (a, t)
my,[(a, t)]
ys') = ((a, t) -> Bool) -> [(a, t)] -> (Maybe (a, t), [(a, t)])
forall a. (a -> Bool) -> [a] -> (Maybe a, [a])
deleteAndGetBy ((a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
k)(a -> Bool) -> ((a, t) -> a) -> (a, t) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(a, t) -> a
forall a b. (a, b) -> a
fst) [(a, t)]
ys
          in case Maybe (a, t)
my of
                  Just (a
_,t
y) -> t -> t -> Bool
f t
x t
y Bool -> Bool -> Bool
&& (t -> t -> Bool) -> [(a, t)] -> [(a, t)] -> Bool
go t -> t -> Bool
f [(a, t)]
xs [(a, t)]
ys'
                  Maybe (a, t)
Nothing    -> Bool
False

instance Ord k => OrdMap AList k where
   ordCmp :: forall a. AList k a -> k -> k -> Ordering
ordCmp = (k -> k -> Ordering) -> AList k a -> k -> k -> Ordering
forall a b. a -> b -> a
const k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare

   toAscList :: forall a. AList k a -> [(k, a)]
toAscList  = ((k, a) -> (k, a) -> Ordering) -> [(k, a)] -> [(k, a)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (       ((k, a) -> k) -> (k, a) -> (k, a) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (k, a) -> k
forall a b. (a, b) -> a
fst) ([(k, a)] -> [(k, a)])
-> (AList k a -> [(k, a)]) -> AList k a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AList k a -> [(k, a)]
forall a. AList k a -> [(k, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
toListKV
   toDescList :: forall a. AList k a -> [(k, a)]
toDescList = ((k, a) -> (k, a) -> Ordering) -> [(k, a)] -> [(k, a)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (((k, a) -> (k, a) -> Ordering) -> (k, a) -> (k, a) -> Ordering
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((k, a) -> (k, a) -> Ordering) -> (k, a) -> (k, a) -> Ordering)
-> ((k, a) -> (k, a) -> Ordering) -> (k, a) -> (k, a) -> Ordering
forall a b. (a -> b) -> a -> b
$ ((k, a) -> k) -> (k, a) -> (k, a) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (k, a) -> k
forall a b. (a, b) -> a
fst) ([(k, a)] -> [(k, a)])
-> (AList k a -> [(k, a)]) -> AList k a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. AList k a -> [(k, a)]
forall a. AList k a -> [(k, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
toListKV

   splitLookup :: forall a. k -> AList k a -> (AList k a, Maybe a, AList k a)
splitLookup k
k (AL [(k, a)]
xs) =
      let ([(k, a)]
ls,[(k, a)]
gs)  = ((k, a) -> Bool) -> [(k, a)] -> ([(k, a)], [(k, a)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
partition ((k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k)(k -> Bool) -> ((k, a) -> k) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(k, a) -> k
forall a b. (a, b) -> a
fst) [(k, a)]
xs
          (Maybe (k, a)
mx,[(k, a)]
gs') = ((k, a) -> Bool) -> [(k, a)] -> (Maybe (k, a), [(k, a)])
forall a. (a -> Bool) -> [a] -> (Maybe a, [a])
deleteAndGetBy ((k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k)(k -> Bool) -> ((k, a) -> k) -> (k, a) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(k, a) -> k
forall a b. (a, b) -> a
fst) [(k, a)]
gs
       in ([(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL [(k, a)]
ls, ((k, a) -> a) -> Maybe (k, a) -> Maybe a
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, a) -> a
forall a b. (a, b) -> b
snd Maybe (k, a)
mx, [(k, a)] -> AList k a
forall k v. [(k, v)] -> AList k v
AL [(k, a)]
gs')

deleteAndGetBy :: (a -> Bool) -> [a] -> (Maybe a, [a])
deleteAndGetBy :: forall a. (a -> Bool) -> [a] -> (Maybe a, [a])
deleteAndGetBy = [a] -> (a -> Bool) -> [a] -> (Maybe a, [a])
forall {a}. [a] -> (a -> Bool) -> [a] -> (Maybe a, [a])
go []
 where
   go :: [a] -> (a -> Bool) -> [a] -> (Maybe a, [a])
go [a]
ys a -> Bool
_ []     = (Maybe a
forall a. Maybe a
Nothing, [a]
ys)
   go [a]
ys a -> Bool
p (a
x:[a]
xs) =
      if a -> Bool
p a
x
         then (a -> Maybe a
forall a. a -> Maybe a
Just a
x, [a]
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
ys)
         else [a] -> (a -> Bool) -> [a] -> (Maybe a, [a])
go (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
ys) a -> Bool
p [a]
xs

-- This is from Data.List, just with a more general type signature...
deleteBy :: (a -> b -> Bool) -> a -> [b] -> [b]
deleteBy :: forall a b. (a -> b -> Bool) -> a -> [b] -> [b]
deleteBy a -> b -> Bool
_  a
_ []     = []
deleteBy a -> b -> Bool
eq a
x (b
y:[b]
ys) = if a
x a -> b -> Bool
`eq` b
y then [b]
ys else b
y b -> [b] -> [b]
forall a. a -> [a] -> [a]
: (a -> b -> Bool) -> a -> [b] -> [b]
forall a b. (a -> b -> Bool) -> a -> [b] -> [b]
deleteBy a -> b -> Bool
eq a
x [b]
ys

updateFirstsBy :: (a -> b -> Maybe a)
               -> (a -> b -> Bool)
               -> [a]
               -> [b]
               -> ([a],[b])
updateFirstsBy :: forall a b.
(a -> b -> Maybe a) -> (a -> b -> Bool) -> [a] -> [b] -> ([a], [b])
updateFirstsBy a -> b -> Maybe a
_ a -> b -> Bool
_  []     [b]
ys  = ([],[b]
ys)
updateFirstsBy a -> b -> Maybe a
f a -> b -> Bool
eq (a
x:[a]
xs) [b]
ys =
   let (Maybe b
my,[b]
ys') = (b -> Bool) -> [b] -> (Maybe b, [b])
forall a. (a -> Bool) -> [a] -> (Maybe a, [a])
deleteAndGetBy (a -> b -> Bool
eq a
x) [b]
ys
    in case Maybe b
my of
            Maybe b
Nothing -> ([a] -> [a]) -> ([a], [b]) -> ([a], [b])
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (([a], [b]) -> ([a], [b])) -> ([a], [b]) -> ([a], [b])
forall a b. (a -> b) -> a -> b
$ (a -> b -> Maybe a) -> (a -> b -> Bool) -> [a] -> [b] -> ([a], [b])
forall a b.
(a -> b -> Maybe a) -> (a -> b -> Bool) -> [a] -> [b] -> ([a], [b])
updateFirstsBy a -> b -> Maybe a
f a -> b -> Bool
eq [a]
xs [b]
ys
            Just b
y  ->
               case a -> b -> Maybe a
f a
x b
y of
                    Just a
z  -> ([a] -> [a]) -> ([a], [b]) -> ([a], [b])
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (a
za -> [a] -> [a]
forall a. a -> [a] -> [a]
:) (([a], [b]) -> ([a], [b])) -> ([a], [b]) -> ([a], [b])
forall a b. (a -> b) -> a -> b
$ (a -> b -> Maybe a) -> (a -> b -> Bool) -> [a] -> [b] -> ([a], [b])
forall a b.
(a -> b -> Maybe a) -> (a -> b -> Bool) -> [a] -> [b] -> ([a], [b])
updateFirstsBy a -> b -> Maybe a
f a -> b -> Bool
eq [a]
xs [b]
ys'
                    Maybe a
Nothing ->              (a -> b -> Maybe a) -> (a -> b -> Bool) -> [a] -> [b] -> ([a], [b])
forall a b.
(a -> b -> Maybe a) -> (a -> b -> Bool) -> [a] -> [b] -> ([a], [b])
updateFirstsBy a -> b -> Maybe a
f a -> b -> Bool
eq [a]
xs [b]
ys'

instance Ord k => Map M.Map k where
   eqCmp :: forall a. Map k a -> k -> k -> Bool
eqCmp = (k -> k -> Bool) -> Map k a -> k -> k -> Bool
forall a b. a -> b -> a
const k -> k -> Bool
forall a. Eq a => a -> a -> Bool
(==)

   empty :: forall a. Map k a
empty     = Map k a
forall k a. Map k a
M.empty
   singleton :: forall a. k -> a -> Map k a
singleton = k -> a -> Map k a
forall k a. k -> a -> Map k a
M.singleton

   null :: forall a. Map k a -> Bool
null   = Map k a -> Bool
forall k a. Map k a -> Bool
M.null
   lookup :: forall a. k -> Map k a -> Maybe a
lookup = k -> Map k a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup

#if MIN_VERSION_containers(0,5,0)
   insertWith :: forall a. (a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWith = (a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
M.Strict.insertWith
#else
   insertWith = M.insertWith'
#endif

   update :: forall a. (a -> Maybe a) -> k -> Map k a -> Map k a
update = (a -> Maybe a) -> k -> Map k a -> Map k a
forall k a. Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
M.update
   adjust :: forall a. (a -> a) -> k -> Map k a -> Map k a
adjust = (a -> a) -> k -> Map k a -> Map k a
forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
M.adjust
   delete :: forall a. k -> Map k a -> Map k a
delete = k -> Map k a -> Map k a
forall k a. Ord k => k -> Map k a -> Map k a
M.delete

   alter :: forall a. (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
alter  = (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
M.alter

   unionWith :: forall a. (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith           = (a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWith
   differenceWith :: forall a b. (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWith      = (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
forall k a b.
Ord k =>
(a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
M.differenceWith
   intersectionWith :: forall a b c. (a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWith    = (a -> b -> c) -> Map k a -> Map k b -> Map k c
forall k a b c.
Ord k =>
(a -> b -> c) -> Map k a -> Map k b -> Map k c
M.intersectionWith
   unionWithKey :: forall a. (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey        = (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a.
Ord k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWithKey
   differenceWithKey :: forall a b.
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWithKey   = (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
forall k a b.
Ord k =>
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
M.differenceWithKey
   intersectionWithKey :: forall a b c. (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey = (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
forall k a b c.
Ord k =>
(k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
M.intersectionWithKey

   map :: forall a b. (a -> b) -> Map k a -> Map k b
map             = (a -> b) -> Map k a -> Map k b
forall a b k. (a -> b) -> Map k a -> Map k b
M.map
   mapWithKey :: forall a b. (k -> a -> b) -> Map k a -> Map k b
mapWithKey      = (k -> a -> b) -> Map k a -> Map k b
forall k a b. (k -> a -> b) -> Map k a -> Map k b
M.mapWithKey
   mapAccum :: forall a b c. (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccum        = (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall a b c k. (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
M.mapAccum
   mapAccumWithKey :: forall a b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumWithKey = (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall a k b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
M.mapAccumWithKey

   filter :: forall a. (a -> Bool) -> Map k a -> Map k a
filter = (a -> Bool) -> Map k a -> Map k a
forall a k. (a -> Bool) -> Map k a -> Map k a
M.filter

   toListKV :: forall a. Map k a -> [(k, a)]
toListKV       = Map k a -> [(k, a)]
forall k a. Map k a -> [(k, a)]
M.toList
   fromListKV :: forall a. [(k, a)] -> Map k a
fromListKV     = [(k, a)] -> Map k a
forall k a. Ord k => [(k, a)] -> Map k a
M.fromList
   fromListKVWith :: forall a. (a -> a -> a) -> [(k, a)] -> Map k a
fromListKVWith = (a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
M.fromListWith

   serializeToList :: forall a. Map k a -> [(k, a)]
serializeToList     = Map k a -> [(k, a)]
forall k a. Map k a -> [(k, a)]
M.toAscList
   deserializeFromList :: forall a. [(k, a)] -> Map k a
deserializeFromList = [(k, a)] -> Map k a
forall k a. [(k, a)] -> Map k a
M.fromDistinctAscList

   isSubmapOfBy :: forall a b. (a -> b -> Bool) -> Map k a -> Map k b -> Bool
isSubmapOfBy = (a -> b -> Bool) -> Map k a -> Map k b -> Bool
forall k a b.
Ord k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
M.isSubmapOfBy

   singletonView :: forall a. Map k a -> Maybe (k, a)
singletonView Map k a
m =
      case Map k a -> Maybe ((k, a), Map k a)
forall k a. Map k a -> Maybe ((k, a), Map k a)
M.minViewWithKey Map k a
m of
           Just ((k, a)
a,Map k a
others) | Map k a -> Bool
forall k a. Map k a -> Bool
M.null Map k a
others -> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k, a)
a
           Maybe ((k, a), Map k a)
_                               -> Maybe (k, a)
forall a. Maybe a
Nothing

instance Ord k => OrdMap M.Map k where
   ordCmp :: forall a. Map k a -> k -> k -> Ordering
ordCmp = (k -> k -> Ordering) -> Map k a -> k -> k -> Ordering
forall a b. a -> b -> a
const k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare

   toAscList :: forall a. Map k a -> [(k, a)]
toAscList = Map k a -> [(k, a)]
forall k a. Map k a -> [(k, a)]
M.toAscList

   splitLookup :: forall a. k -> Map k a -> (Map k a, Maybe a, Map k a)
splitLookup = k -> Map k a -> (Map k a, Maybe a, Map k a)
forall k a. Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
M.splitLookup
   split :: forall a. k -> Map k a -> (Map k a, Map k a)
split       = k -> Map k a -> (Map k a, Map k a)
forall k a. Ord k => k -> Map k a -> (Map k a, Map k a)
M.split

   minViewWithKey :: forall a. Map k a -> (Maybe (k, a), Map k a)
minViewWithKey Map k a
m = (Maybe (k, a), Map k a)
-> (((k, a), Map k a) -> (Maybe (k, a), Map k a))
-> Maybe ((k, a), Map k a)
-> (Maybe (k, a), Map k a)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Maybe (k, a)
forall a. Maybe a
Nothing, Map k a
m) (((k, a) -> Maybe (k, a))
-> ((k, a), Map k a) -> (Maybe (k, a), Map k a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just) (Map k a -> Maybe ((k, a), Map k a)
forall k a. Map k a -> Maybe ((k, a), Map k a)
M.minViewWithKey Map k a
m)
   maxViewWithKey :: forall a. Map k a -> (Maybe (k, a), Map k a)
maxViewWithKey Map k a
m = (Maybe (k, a), Map k a)
-> (((k, a), Map k a) -> (Maybe (k, a), Map k a))
-> Maybe ((k, a), Map k a)
-> (Maybe (k, a), Map k a)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Maybe (k, a)
forall a. Maybe a
Nothing, Map k a
m) (((k, a) -> Maybe (k, a))
-> ((k, a), Map k a) -> (Maybe (k, a), Map k a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just) (Map k a -> Maybe ((k, a), Map k a)
forall k a. Map k a -> Maybe ((k, a), Map k a)
M.maxViewWithKey Map k a
m)

   mapAccumAsc :: forall a b c. (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumAsc         = (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall a b c k. (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
M.mapAccum
   mapAccumAscWithKey :: forall a b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumAscWithKey  = (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall a k b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
M.mapAccumWithKey
   mapAccumDesc :: forall a b c. (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumDesc        = (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumR
   mapAccumDescWithKey :: forall a b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumDescWithKey = (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall a k b c.
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
M.mapAccumRWithKey

newtype WrappedIntMap k v = IMap (IM.IntMap v) deriving (WrappedIntMap k v -> WrappedIntMap k v -> Bool
(WrappedIntMap k v -> WrappedIntMap k v -> Bool)
-> (WrappedIntMap k v -> WrappedIntMap k v -> Bool)
-> Eq (WrappedIntMap k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. Eq v => WrappedIntMap k v -> WrappedIntMap k v -> Bool
$c== :: forall k v. Eq v => WrappedIntMap k v -> WrappedIntMap k v -> Bool
== :: WrappedIntMap k v -> WrappedIntMap k v -> Bool
$c/= :: forall k v. Eq v => WrappedIntMap k v -> WrappedIntMap k v -> Bool
/= :: WrappedIntMap k v -> WrappedIntMap k v -> Bool
Eq,Eq (WrappedIntMap k v)
Eq (WrappedIntMap k v) =>
(WrappedIntMap k v -> WrappedIntMap k v -> Ordering)
-> (WrappedIntMap k v -> WrappedIntMap k v -> Bool)
-> (WrappedIntMap k v -> WrappedIntMap k v -> Bool)
-> (WrappedIntMap k v -> WrappedIntMap k v -> Bool)
-> (WrappedIntMap k v -> WrappedIntMap k v -> Bool)
-> (WrappedIntMap k v -> WrappedIntMap k v -> WrappedIntMap k v)
-> (WrappedIntMap k v -> WrappedIntMap k v -> WrappedIntMap k v)
-> Ord (WrappedIntMap k v)
WrappedIntMap k v -> WrappedIntMap k v -> Bool
WrappedIntMap k v -> WrappedIntMap k v -> Ordering
WrappedIntMap k v -> WrappedIntMap k v -> WrappedIntMap k v
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall k v. Ord v => Eq (WrappedIntMap k v)
forall k v. Ord v => WrappedIntMap k v -> WrappedIntMap k v -> Bool
forall k v.
Ord v =>
WrappedIntMap k v -> WrappedIntMap k v -> Ordering
forall k v.
Ord v =>
WrappedIntMap k v -> WrappedIntMap k v -> WrappedIntMap k v
$ccompare :: forall k v.
Ord v =>
WrappedIntMap k v -> WrappedIntMap k v -> Ordering
compare :: WrappedIntMap k v -> WrappedIntMap k v -> Ordering
$c< :: forall k v. Ord v => WrappedIntMap k v -> WrappedIntMap k v -> Bool
< :: WrappedIntMap k v -> WrappedIntMap k v -> Bool
$c<= :: forall k v. Ord v => WrappedIntMap k v -> WrappedIntMap k v -> Bool
<= :: WrappedIntMap k v -> WrappedIntMap k v -> Bool
$c> :: forall k v. Ord v => WrappedIntMap k v -> WrappedIntMap k v -> Bool
> :: WrappedIntMap k v -> WrappedIntMap k v -> Bool
$c>= :: forall k v. Ord v => WrappedIntMap k v -> WrappedIntMap k v -> Bool
>= :: WrappedIntMap k v -> WrappedIntMap k v -> Bool
$cmax :: forall k v.
Ord v =>
WrappedIntMap k v -> WrappedIntMap k v -> WrappedIntMap k v
max :: WrappedIntMap k v -> WrappedIntMap k v -> WrappedIntMap k v
$cmin :: forall k v.
Ord v =>
WrappedIntMap k v -> WrappedIntMap k v -> WrappedIntMap k v
min :: WrappedIntMap k v -> WrappedIntMap k v -> WrappedIntMap k v
Ord)

instance Functor (WrappedIntMap k) where fmap :: forall a b. (a -> b) -> WrappedIntMap k a -> WrappedIntMap k b
fmap a -> b
f (IMap IntMap a
m) = IntMap b -> WrappedIntMap k b
forall k v. IntMap v -> WrappedIntMap k v
IMap ((a -> b) -> IntMap a -> IntMap b
forall a b. (a -> b) -> IntMap a -> IntMap b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f IntMap a
m)
instance Foldable (WrappedIntMap k) where
    fold :: forall m. Monoid m => WrappedIntMap k m -> m
fold        (IMap IntMap m
m) = IntMap m -> m
forall m. Monoid m => IntMap m -> m
forall (t :: * -> *) m. (Foldable t, Monoid m) => t m -> m
fold        IntMap m
m
    foldMap :: forall m a. Monoid m => (a -> m) -> WrappedIntMap k a -> m
foldMap a -> m
f   (IMap IntMap a
m) = (a -> m) -> IntMap a -> m
forall m a. Monoid m => (a -> m) -> IntMap a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f   IntMap a
m
    foldl :: forall b a. (b -> a -> b) -> b -> WrappedIntMap k a -> b
foldl   b -> a -> b
f b
z (IMap IntMap a
m) = (b -> a -> b) -> b -> IntMap a -> b
forall b a. (b -> a -> b) -> b -> IntMap a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl   b -> a -> b
f b
z IntMap a
m
    foldl1 :: forall a. (a -> a -> a) -> WrappedIntMap k a -> a
foldl1  a -> a -> a
f   (IMap IntMap a
m) = (a -> a -> a) -> IntMap a -> a
forall a. (a -> a -> a) -> IntMap a -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldl1  a -> a -> a
f   IntMap a
m
    foldr :: forall a b. (a -> b -> b) -> b -> WrappedIntMap k a -> b
foldr   a -> b -> b
f b
z (IMap IntMap a
m) = (a -> b -> b) -> b -> IntMap a -> b
forall a b. (a -> b -> b) -> b -> IntMap a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr   a -> b -> b
f b
z IntMap a
m
    foldr1 :: forall a. (a -> a -> a) -> WrappedIntMap k a -> a
foldr1  a -> a -> a
f   (IMap IntMap a
m) = (a -> a -> a) -> IntMap a -> a
forall a. (a -> a -> a) -> IntMap a -> a
forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1  a -> a -> a
f   IntMap a
m

instance Traversable (WrappedIntMap k) where
   traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> WrappedIntMap k a -> f (WrappedIntMap k b)
traverse a -> f b
f (IMap IntMap a
m) = (IntMap b -> WrappedIntMap k b)
-> f (IntMap b -> WrappedIntMap k b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure IntMap b -> WrappedIntMap k b
forall k v. IntMap v -> WrappedIntMap k v
IMap f (IntMap b -> WrappedIntMap k b)
-> f (IntMap b) -> f (WrappedIntMap k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (a -> f b) -> IntMap a -> f (IntMap b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> IntMap a -> f (IntMap b)
traverse a -> f b
f IntMap a
m
   sequenceA :: forall (f :: * -> *) a.
Applicative f =>
WrappedIntMap k (f a) -> f (WrappedIntMap k a)
sequenceA (IMap IntMap (f a)
m) = (IntMap a -> WrappedIntMap k a)
-> f (IntMap a -> WrappedIntMap k a)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap f (IntMap a -> WrappedIntMap k a)
-> f (IntMap a) -> f (WrappedIntMap k a)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> IntMap (f a) -> f (IntMap a)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
forall (f :: * -> *) a.
Applicative f =>
IntMap (f a) -> f (IntMap a)
sequenceA IntMap (f a)
m
   mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> WrappedIntMap k a -> m (WrappedIntMap k b)
mapM a -> m b
f (IMap IntMap a
m) = (IntMap b -> WrappedIntMap k b)
-> m (IntMap b) -> m (WrappedIntMap k b)
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM IntMap b -> WrappedIntMap k b
forall k v. IntMap v -> WrappedIntMap k v
IMap ((a -> m b) -> IntMap a -> m (IntMap b)
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> IntMap a -> m (IntMap b)
mapM a -> m b
f IntMap a
m)
   sequence :: forall (m :: * -> *) a.
Monad m =>
WrappedIntMap k (m a) -> m (WrappedIntMap k a)
sequence (IMap IntMap (m a)
m) = (IntMap a -> WrappedIntMap k a)
-> m (IntMap a) -> m (WrappedIntMap k a)
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap (IntMap (m a) -> m (IntMap a)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
forall (m :: * -> *) a. Monad m => IntMap (m a) -> m (IntMap a)
sequence IntMap (m a)
m)

instance Enum k => Map WrappedIntMap k where
   eqCmp :: forall a. WrappedIntMap k a -> k -> k -> Bool
eqCmp = (k -> k -> Bool) -> WrappedIntMap k a -> k -> k -> Bool
forall a b. a -> b -> a
const (Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
(==) (Int -> Int -> Bool) -> (k -> Int) -> k -> k -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` k -> Int
forall a. Enum a => a -> Int
fromEnum)

   empty :: forall a. WrappedIntMap k a
empty       = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap IntMap a
forall a. IntMap a
IM.empty
   singleton :: forall a. k -> a -> WrappedIntMap k a
singleton k
k = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap (IntMap a -> WrappedIntMap k a)
-> (a -> IntMap a) -> a -> WrappedIntMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a -> IntMap a
forall a. Int -> a -> IntMap a
IM.singleton (k -> Int
forall a. Enum a => a -> Int
fromEnum k
k)

   null :: forall a. WrappedIntMap k a -> Bool
null     (IMap IntMap a
m) = IntMap a -> Bool
forall a. IntMap a -> Bool
IM.null IntMap a
m
   lookup :: forall a. k -> WrappedIntMap k a -> Maybe a
lookup k
k (IMap IntMap a
m) = Int -> IntMap a -> Maybe a
forall a. Int -> IntMap a -> Maybe a
IM.lookup (k -> Int
forall a. Enum a => a -> Int
fromEnum k
k) IntMap a
m

   insertWith :: forall a.
(a -> a -> a) -> k -> a -> WrappedIntMap k a -> WrappedIntMap k a
insertWith a -> a -> a
f k
k a
v (IMap IntMap a
m) = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
IM.insertWith a -> a -> a
f (k -> Int
forall a. Enum a => a -> Int
fromEnum k
k) a
v IntMap a
m

   update :: forall a.
(a -> Maybe a) -> k -> WrappedIntMap k a -> WrappedIntMap k a
update a -> Maybe a
f k
k (IMap IntMap a
m) = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ (a -> Maybe a) -> Int -> IntMap a -> IntMap a
forall a. (a -> Maybe a) -> Int -> IntMap a -> IntMap a
IM.update a -> Maybe a
f (k -> Int
forall a. Enum a => a -> Int
fromEnum k
k) IntMap a
m
   adjust :: forall a. (a -> a) -> k -> WrappedIntMap k a -> WrappedIntMap k a
adjust a -> a
f k
k (IMap IntMap a
m) = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ (a -> a) -> Int -> IntMap a -> IntMap a
forall a. (a -> a) -> Int -> IntMap a -> IntMap a
IM.adjust a -> a
f (k -> Int
forall a. Enum a => a -> Int
fromEnum k
k) IntMap a
m
   delete :: forall a. k -> WrappedIntMap k a -> WrappedIntMap k a
delete   k
k (IMap IntMap a
m) = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ Int -> IntMap a -> IntMap a
forall a. Int -> IntMap a -> IntMap a
IM.delete   (k -> Int
forall a. Enum a => a -> Int
fromEnum k
k) IntMap a
m

   alter :: forall a.
(Maybe a -> Maybe a) -> k -> WrappedIntMap k a -> WrappedIntMap k a
alter  Maybe a -> Maybe a
f k
k (IMap IntMap a
m) = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
IM.alter  Maybe a -> Maybe a
f (k -> Int
forall a. Enum a => a -> Int
fromEnum k
k) IntMap a
m

   unionWith :: forall a.
(a -> a -> a)
-> WrappedIntMap k a -> WrappedIntMap k a -> WrappedIntMap k a
unionWith        a -> a -> a
f (IMap IntMap a
x) (IMap IntMap a
y) = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
IM.unionWith        a -> a -> a
f IntMap a
x IntMap a
y
   differenceWith :: forall a b.
(a -> b -> Maybe a)
-> WrappedIntMap k a -> WrappedIntMap k b -> WrappedIntMap k a
differenceWith   a -> b -> Maybe a
f (IMap IntMap a
x) (IMap IntMap b
y) = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ (a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
forall a b. (a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
IM.differenceWith   a -> b -> Maybe a
f IntMap a
x IntMap b
y
   intersectionWith :: forall a b c.
(a -> b -> c)
-> WrappedIntMap k a -> WrappedIntMap k b -> WrappedIntMap k c
intersectionWith a -> b -> c
f (IMap IntMap a
x) (IMap IntMap b
y) = IntMap c -> WrappedIntMap k c
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap c -> WrappedIntMap k c) -> IntMap c -> WrappedIntMap k c
forall a b. (a -> b) -> a -> b
$ (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
forall a b c. (a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
IM.intersectionWith a -> b -> c
f IntMap a
x IntMap b
y

   unionWithKey :: forall a.
(k -> a -> a -> a)
-> WrappedIntMap k a -> WrappedIntMap k a -> WrappedIntMap k a
unionWithKey      k -> a -> a -> a
f (IMap IntMap a
x) (IMap IntMap a
y) =
      IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ (Int -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
forall a. (Int -> a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
IM.unionWithKey (k -> a -> a -> a
f (k -> a -> a -> a) -> (Int -> k) -> Int -> a -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> k
forall a. Enum a => Int -> a
toEnum) IntMap a
x IntMap a
y
   differenceWithKey :: forall a b.
(k -> a -> b -> Maybe a)
-> WrappedIntMap k a -> WrappedIntMap k b -> WrappedIntMap k a
differenceWithKey k -> a -> b -> Maybe a
f (IMap IntMap a
x) (IMap IntMap b
y) =
      IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ (Int -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
forall a b.
(Int -> a -> b -> Maybe a) -> IntMap a -> IntMap b -> IntMap a
IM.differenceWithKey (k -> a -> b -> Maybe a
f (k -> a -> b -> Maybe a) -> (Int -> k) -> Int -> a -> b -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> k
forall a. Enum a => Int -> a
toEnum) IntMap a
x IntMap b
y
   intersectionWithKey :: forall a b c.
(k -> a -> b -> c)
-> WrappedIntMap k a -> WrappedIntMap k b -> WrappedIntMap k c
intersectionWithKey k -> a -> b -> c
f (IMap IntMap a
x) (IMap IntMap b
y) =
      IntMap c -> WrappedIntMap k c
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap c -> WrappedIntMap k c) -> IntMap c -> WrappedIntMap k c
forall a b. (a -> b) -> a -> b
$ (Int -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
forall a b c.
(Int -> a -> b -> c) -> IntMap a -> IntMap b -> IntMap c
IM.intersectionWithKey (k -> a -> b -> c
f (k -> a -> b -> c) -> (Int -> k) -> Int -> a -> b -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> k
forall a. Enum a => Int -> a
toEnum) IntMap a
x IntMap b
y

   map :: forall a b. (a -> b) -> WrappedIntMap k a -> WrappedIntMap k b
map             a -> b
f   (IMap IntMap a
x) = IntMap b -> WrappedIntMap k b
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap b -> WrappedIntMap k b) -> IntMap b -> WrappedIntMap k b
forall a b. (a -> b) -> a -> b
$ (a -> b) -> IntMap a -> IntMap b
forall a b. (a -> b) -> IntMap a -> IntMap b
IM.map a -> b
f IntMap a
x
   mapWithKey :: forall a b. (k -> a -> b) -> WrappedIntMap k a -> WrappedIntMap k b
mapWithKey      k -> a -> b
f   (IMap IntMap a
x) = IntMap b -> WrappedIntMap k b
forall k v. IntMap v -> WrappedIntMap k v
IMap(IntMap b -> WrappedIntMap k b) -> IntMap b -> WrappedIntMap k b
forall a b. (a -> b) -> a -> b
$ (Int -> a -> b) -> IntMap a -> IntMap b
forall a b. (Int -> a -> b) -> IntMap a -> IntMap b
IM.mapWithKey (k -> a -> b
f (k -> a -> b) -> (Int -> k) -> Int -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> k
forall a. Enum a => Int -> a
toEnum) IntMap a
x
   mapAccum :: forall a b c.
(a -> b -> (a, c))
-> a -> WrappedIntMap k b -> (a, WrappedIntMap k c)
mapAccum        a -> b -> (a, c)
f a
z (IMap IntMap b
x) = (IntMap c -> WrappedIntMap k c)
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IntMap c -> WrappedIntMap k c
forall k v. IntMap v -> WrappedIntMap k v
IMap((a, IntMap c) -> (a, WrappedIntMap k c))
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall a b. (a -> b) -> a -> b
$ (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
forall a b c. (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
IM.mapAccum a -> b -> (a, c)
f a
z IntMap b
x
   mapAccumWithKey :: forall a b c.
(a -> k -> b -> (a, c))
-> a -> WrappedIntMap k b -> (a, WrappedIntMap k c)
mapAccumWithKey a -> k -> b -> (a, c)
f a
z (IMap IntMap b
x) =
      (IntMap c -> WrappedIntMap k c)
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IntMap c -> WrappedIntMap k c
forall k v. IntMap v -> WrappedIntMap k v
IMap((a, IntMap c) -> (a, WrappedIntMap k c))
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall a b. (a -> b) -> a -> b
$ (a -> Int -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
forall a b c.
(a -> Int -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
IM.mapAccumWithKey (\a
a -> a -> k -> b -> (a, c)
f a
a (k -> b -> (a, c)) -> (Int -> k) -> Int -> b -> (a, c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> k
forall a. Enum a => Int -> a
toEnum) a
z IntMap b
x

   filter :: forall a. (a -> Bool) -> WrappedIntMap k a -> WrappedIntMap k a
filter a -> Bool
p (IMap IntMap a
x) = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap (IntMap a -> WrappedIntMap k a) -> IntMap a -> WrappedIntMap k a
forall a b. (a -> b) -> a -> b
$ (a -> Bool) -> IntMap a -> IntMap a
forall a. (a -> Bool) -> IntMap a -> IntMap a
IM.filter a -> Bool
p IntMap a
x

   toListKV :: forall a. WrappedIntMap k a -> [(k, a)]
toListKV (IMap IntMap a
m) = ((Int, a) -> (k, a)) -> [(Int, a)] -> [(k, a)]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map ((Int -> k) -> (Int, a) -> (k, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Int -> k
forall a. Enum a => Int -> a
toEnum) ([(Int, a)] -> [(k, a)])
-> (IntMap a -> [(Int, a)]) -> IntMap a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap a -> [(Int, a)]
forall a. IntMap a -> [(Int, a)]
IM.toList (IntMap a -> [(k, a)]) -> IntMap a -> [(k, a)]
forall a b. (a -> b) -> a -> b
$ IntMap a
m
   fromListKV :: forall a. [(k, a)] -> WrappedIntMap k a
fromListKV        = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap (IntMap a -> WrappedIntMap k a)
-> ([(k, a)] -> IntMap a) -> [(k, a)] -> WrappedIntMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, a)] -> IntMap a
forall a. [(Int, a)] -> IntMap a
IM.fromList       ([(Int, a)] -> IntMap a)
-> ([(k, a)] -> [(Int, a)]) -> [(k, a)] -> IntMap a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, a) -> (Int, a)) -> [(k, a)] -> [(Int, a)]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map ((k -> Int) -> (k, a) -> (Int, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first k -> Int
forall a. Enum a => a -> Int
fromEnum)
   fromListKVWith :: forall a. (a -> a -> a) -> [(k, a)] -> WrappedIntMap k a
fromListKVWith a -> a -> a
f  = IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap (IntMap a -> WrappedIntMap k a)
-> ([(k, a)] -> IntMap a) -> [(k, a)] -> WrappedIntMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> [(Int, a)] -> IntMap a
forall a. (a -> a -> a) -> [(Int, a)] -> IntMap a
IM.fromListWith a -> a -> a
f ([(Int, a)] -> IntMap a)
-> ([(k, a)] -> [(Int, a)]) -> [(k, a)] -> IntMap a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, a) -> (Int, a)) -> [(k, a)] -> [(Int, a)]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map ((k -> Int) -> (k, a) -> (Int, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first k -> Int
forall a. Enum a => a -> Int
fromEnum)

   serializeToList :: forall a. WrappedIntMap k a -> [(k, a)]
serializeToList (IMap IntMap a
x) = ((Int, a) -> (k, a)) -> [(Int, a)] -> [(k, a)]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map ((Int -> k) -> (Int, a) -> (k, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Int -> k
forall a. Enum a => Int -> a
toEnum) ([(Int, a)] -> [(k, a)])
-> (IntMap a -> [(Int, a)]) -> IntMap a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap a -> [(Int, a)]
forall a. IntMap a -> [(Int, a)]
IM.toAscList (IntMap a -> [(k, a)]) -> IntMap a -> [(k, a)]
forall a b. (a -> b) -> a -> b
$ IntMap a
x
   deserializeFromList :: forall a. [(k, a)] -> WrappedIntMap k a
deserializeFromList      =
      IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap (IntMap a -> WrappedIntMap k a)
-> ([(k, a)] -> IntMap a) -> [(k, a)] -> WrappedIntMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(Int, a)] -> IntMap a
forall a. [(Int, a)] -> IntMap a
IM.fromDistinctAscList ([(Int, a)] -> IntMap a)
-> ([(k, a)] -> [(Int, a)]) -> [(k, a)] -> IntMap a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, a) -> (Int, a)) -> [(k, a)] -> [(Int, a)]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map ((k -> Int) -> (k, a) -> (Int, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first k -> Int
forall a. Enum a => a -> Int
fromEnum)

   isSubmapOfBy :: forall a b.
(a -> b -> Bool) -> WrappedIntMap k a -> WrappedIntMap k b -> Bool
isSubmapOfBy a -> b -> Bool
f (IMap IntMap a
x) (IMap IntMap b
y) = (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
forall a b. (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
IM.isSubmapOfBy a -> b -> Bool
f IntMap a
x IntMap b
y

   singletonView :: forall a. WrappedIntMap k a -> Maybe (k, a)
singletonView (IMap IntMap a
m) =
      case IntMap a -> Maybe ((Int, a), IntMap a)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.minViewWithKey IntMap a
m of
           Just ((Int, a)
a,IntMap a
others) | IntMap a -> Bool
forall a. IntMap a -> Bool
IM.null IntMap a
others -> (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just ((Int -> k) -> (Int, a) -> (k, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Int -> k
forall a. Enum a => Int -> a
toEnum (Int, a)
a)
           Maybe ((Int, a), IntMap a)
_                                -> Maybe (k, a)
forall a. Maybe a
Nothing

instance Enum k => OrdMap WrappedIntMap k where
   ordCmp :: forall a. WrappedIntMap k a -> k -> k -> Ordering
ordCmp = (k -> k -> Ordering) -> WrappedIntMap k a -> k -> k -> Ordering
forall a b. a -> b -> a
const (Int -> Int -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Int -> Int -> Ordering) -> (k -> Int) -> k -> k -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` k -> Int
forall a. Enum a => a -> Int
fromEnum)

   toAscList :: forall a. WrappedIntMap k a -> [(k, a)]
toAscList (IMap IntMap a
m) = ((Int, a) -> (k, a)) -> [(Int, a)] -> [(k, a)]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map ((Int -> k) -> (Int, a) -> (k, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Int -> k
forall a. Enum a => Int -> a
toEnum) ([(Int, a)] -> [(k, a)])
-> (IntMap a -> [(Int, a)]) -> IntMap a -> [(k, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntMap a -> [(Int, a)]
forall a. IntMap a -> [(Int, a)]
IM.toAscList (IntMap a -> [(k, a)]) -> IntMap a -> [(k, a)]
forall a b. (a -> b) -> a -> b
$ IntMap a
m

   splitLookup :: forall a.
k
-> WrappedIntMap k a
-> (WrappedIntMap k a, Maybe a, WrappedIntMap k a)
splitLookup k
k (IMap IntMap a
m) =
      (\(IntMap a
a,Maybe a
b,IntMap a
c) -> (IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap IntMap a
a, Maybe a
b, IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap IntMap a
c)) ((IntMap a, Maybe a, IntMap a)
 -> (WrappedIntMap k a, Maybe a, WrappedIntMap k a))
-> (IntMap a -> (IntMap a, Maybe a, IntMap a))
-> IntMap a
-> (WrappedIntMap k a, Maybe a, WrappedIntMap k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntMap a -> (IntMap a, Maybe a, IntMap a)
forall a. Int -> IntMap a -> (IntMap a, Maybe a, IntMap a)
IM.splitLookup (k -> Int
forall a. Enum a => a -> Int
fromEnum k
k) (IntMap a -> (WrappedIntMap k a, Maybe a, WrappedIntMap k a))
-> IntMap a -> (WrappedIntMap k a, Maybe a, WrappedIntMap k a)
forall a b. (a -> b) -> a -> b
$ IntMap a
m

   split :: forall a.
k -> WrappedIntMap k a -> (WrappedIntMap k a, WrappedIntMap k a)
split k
k (IMap IntMap a
m) = (IntMap a -> WrappedIntMap k a)
-> (IntMap a, IntMap a) -> (WrappedIntMap k a, WrappedIntMap k a)
forall a b. (a -> b) -> (a, a) -> (b, b)
both IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap ((IntMap a, IntMap a) -> (WrappedIntMap k a, WrappedIntMap k a))
-> (IntMap a -> (IntMap a, IntMap a))
-> IntMap a
-> (WrappedIntMap k a, WrappedIntMap k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntMap a -> (IntMap a, IntMap a)
forall a. Int -> IntMap a -> (IntMap a, IntMap a)
IM.split (k -> Int
forall a. Enum a => a -> Int
fromEnum k
k) (IntMap a -> (WrappedIntMap k a, WrappedIntMap k a))
-> IntMap a -> (WrappedIntMap k a, WrappedIntMap k a)
forall a b. (a -> b) -> a -> b
$ IntMap a
m

   minViewWithKey :: forall a. WrappedIntMap k a -> (Maybe (k, a), WrappedIntMap k a)
minViewWithKey o :: WrappedIntMap k a
o@(IMap IntMap a
m) =
      (Maybe (k, a), WrappedIntMap k a)
-> (((Int, a), IntMap a) -> (Maybe (k, a), WrappedIntMap k a))
-> Maybe ((Int, a), IntMap a)
-> (Maybe (k, a), WrappedIntMap k a)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Maybe (k, a)
forall a. Maybe a
Nothing, WrappedIntMap k a
o) ((k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just ((k, a) -> Maybe (k, a))
-> ((Int, a) -> (k, a)) -> (Int, a) -> Maybe (k, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> k) -> (Int, a) -> (k, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Int -> k
forall a. Enum a => Int -> a
toEnum ((Int, a) -> Maybe (k, a))
-> (IntMap a -> WrappedIntMap k a)
-> ((Int, a), IntMap a)
-> (Maybe (k, a), WrappedIntMap k a)
forall b c b' c'. (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap) (IntMap a -> Maybe ((Int, a), IntMap a)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.minViewWithKey IntMap a
m)
   maxViewWithKey :: forall a. WrappedIntMap k a -> (Maybe (k, a), WrappedIntMap k a)
maxViewWithKey o :: WrappedIntMap k a
o@(IMap IntMap a
m) =
      (Maybe (k, a), WrappedIntMap k a)
-> (((Int, a), IntMap a) -> (Maybe (k, a), WrappedIntMap k a))
-> Maybe ((Int, a), IntMap a)
-> (Maybe (k, a), WrappedIntMap k a)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Maybe (k, a)
forall a. Maybe a
Nothing, WrappedIntMap k a
o) ((k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just ((k, a) -> Maybe (k, a))
-> ((Int, a) -> (k, a)) -> (Int, a) -> Maybe (k, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> k) -> (Int, a) -> (k, a)
forall b c d. (b -> c) -> (b, d) -> (c, d)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first Int -> k
forall a. Enum a => Int -> a
toEnum ((Int, a) -> Maybe (k, a))
-> (IntMap a -> WrappedIntMap k a)
-> ((Int, a), IntMap a)
-> (Maybe (k, a), WrappedIntMap k a)
forall b c b' c'. (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** IntMap a -> WrappedIntMap k a
forall k v. IntMap v -> WrappedIntMap k v
IMap) (IntMap a -> Maybe ((Int, a), IntMap a)
forall a. IntMap a -> Maybe ((Int, a), IntMap a)
IM.maxViewWithKey IntMap a
m)

   mapAccumAsc :: forall a b c.
(a -> b -> (a, c))
-> a -> WrappedIntMap k b -> (a, WrappedIntMap k c)
mapAccumAsc         a -> b -> (a, c)
f a
z (IMap IntMap b
m) = (IntMap c -> WrappedIntMap k c)
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IntMap c -> WrappedIntMap k c
forall k v. IntMap v -> WrappedIntMap k v
IMap ((a, IntMap c) -> (a, WrappedIntMap k c))
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall a b. (a -> b) -> a -> b
$ (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
forall a b c. (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
IM.mapAccum a -> b -> (a, c)
f a
z IntMap b
m
   mapAccumAscWithKey :: forall a b c.
(a -> k -> b -> (a, c))
-> a -> WrappedIntMap k b -> (a, WrappedIntMap k c)
mapAccumAscWithKey  a -> k -> b -> (a, c)
f a
z (IMap IntMap b
m) =
      (IntMap c -> WrappedIntMap k c)
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IntMap c -> WrappedIntMap k c
forall k v. IntMap v -> WrappedIntMap k v
IMap ((a, IntMap c) -> (a, WrappedIntMap k c))
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall a b. (a -> b) -> a -> b
$ (a -> Int -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
forall a b c.
(a -> Int -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
IM.mapAccumWithKey (\a
a Int
k -> a -> k -> b -> (a, c)
f a
a (Int -> k
forall a. Enum a => Int -> a
toEnum Int
k)) a
z IntMap b
m

   mapAccumDesc :: forall a b c.
(a -> b -> (a, c))
-> a -> WrappedIntMap k b -> (a, WrappedIntMap k c)
mapAccumDesc        a -> b -> (a, c)
f a
z (IMap IntMap b
m) = (IntMap c -> WrappedIntMap k c)
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IntMap c -> WrappedIntMap k c
forall k v. IntMap v -> WrappedIntMap k v
IMap ((a, IntMap c) -> (a, WrappedIntMap k c))
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall a b. (a -> b) -> a -> b
$ (a -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumR a -> b -> (a, c)
f a
z IntMap b
m
   mapAccumDescWithKey :: forall a b c.
(a -> k -> b -> (a, c))
-> a -> WrappedIntMap k b -> (a, WrappedIntMap k c)
mapAccumDescWithKey a -> k -> b -> (a, c)
f a
z (IMap IntMap b
m) =
      (IntMap c -> WrappedIntMap k c)
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second IntMap c -> WrappedIntMap k c
forall k v. IntMap v -> WrappedIntMap k v
IMap ((a, IntMap c) -> (a, WrappedIntMap k c))
-> (a, IntMap c) -> (a, WrappedIntMap k c)
forall a b. (a -> b) -> a -> b
$ (a -> Int -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
forall a b c.
(a -> Int -> b -> (a, c)) -> a -> IntMap b -> (a, IntMap c)
IM.mapAccumRWithKey (\a
a Int
k -> a -> k -> b -> (a, c)
f a
a (Int -> k
forall a. Enum a => Int -> a
toEnum Int
k)) a
z IntMap b
m