{-| Module  : WeakSets
Description : A `WeakMap` is a Data.Map which does not require the keys to implement the Ord typeclass.
Copyright   : Guillaume Sabbagh 2022
License     : LGPL-3.0-or-later
Maintainer  : guillaumesabbagh@protonmail.com
Stability   : experimental
Portability : portable

A `WeakMap` is a Data.Map which does not require the keys to implement the Ord typeclass. It is a weak set of pairs (key,value).

The datatype only assumes its keys are equatable, it is therefore slower to access data than the Data.Map datatype.

We use this datatype because most of the datatypes we care about are not orderable.

Almost all Data.WeakMap functions are implemented so that you can replace a Data.Map import such as 

> import Data.Map.Strict (Map)
> import qualified Data.Map.Strict as Map

by a Data.WeakMap import such as

> import Data.WeakMap (Map)
> import qualified Data.WeakMap as Map

without breaking anything in your code.

The only functions for which this would fail are the functions converting maps back into list (they require the Eq typeclass unlike in Data.Map). `size` is one of them.

If a function really requires the Ord typeclass to even make sense, then it is not defined in this package, you should use Data.Map.

Note that, just like in Data.Map, the implementation is generally left-biased. Functions that take two maps as arguments and combine them, such as union and intersection, prefer the entries in the first argument to those in the second. 

Functions with non colliding names are defined in Data.WeakMap.Safe. Inline functions are written between pipes @|@.

This module is intended to be imported qualified, to avoid name clashes with Prelude functions, except for functions in Data.WeakSet.Map, e.g.

> import Data.WeakMap (Map)
> import qualified Data.WeakMap as Map
> import Data.WeakMap.Safe

Unlike Data.Map, we defer the removing of duplicate keys to the conversion back to a list. 

Beware if the map is supposed to contain a lot of duplicate keys, you should purge them yourself by transforming the map into a list and back into a map. The time complexity is always given in function of the number of pairs in the map including the duplicate pairs.
-}

module Data.WeakMap
(
    -- * Map type

    AssociationList(..)
    , Map

    -- * Construction

    , weakMap
    , weakMapFromSet
    , empty
    , singleton
    , fromSet

    -- ** From Unordered Lists

    , fromList
    , fromListWith
    , fromListWithKey

    -- ** From Ascending Lists

    , fromAscList
    , fromAscListWith
    , fromAscListWithKey
    , fromDistinctAscList

    -- ** From Descending Lists

    , fromDescList
    , fromDescListWith
    , fromDescListWithKey
    , fromDistinctDescList

    -- * Insertion

    , insert
    , insertWith
    , insertWithKey
    , insertLookupWithKey
    , insertMaybe

    -- * Deletion\/Update

    , delete
    , adjust
    , adjustWithKey
    , update
    , updateWithKey
    , updateLookupWithKey
    , alter
    , alterF

    -- * Query

    -- ** Lookup

    , lookup
    , (!?)
    , (!)
    , (|?|), (|!|)
    , findWithDefault
    , member
    , notMember

    -- ** Size

    , size
    , null

    -- * Combine


    -- ** Union

    , union
    , unionWith
    , unionWithKey
    , unions
    , unionsWith

    -- ** Difference

    , difference
    , (\\)
    , differenceWith
    , differenceWithKey

    -- ** Intersection

    , intersection
    , intersectionWith
    , intersectionWithKey

    -- ** Disjoint

    , disjoint

    -- -- ** Compose

    , (|.|)
    , compose

    , mergeWithKey

    -- * Traversal

    -- ** Map

    , map
    , mapWithKey
    , traverseWithKey
    , traverseMaybeWithKey
    , mapAccum
    , mapAccumWithKey
    , mapAccumRWithKey
    , mapKeys
    , mapKeysWith
    , mapKeysMonotonic

    -- * Folds

    , foldr
    , foldl
    , foldrWithKey
    , foldlWithKey
    , foldMapWithKey

    -- ** Strict folds

    , foldr'
    , foldl'
    , foldrWithKey'
    , foldlWithKey'

    -- * Conversion

    , mapToList
    , mapToSet
    , elems
    , elems'
    , values
    , image
    , keys
    , keys'
    , domain
    , assocs
    , keysSet
    , elemsSet

    -- ** Lists

    , toList

    -- ** Ordered lists

    , toAscList
    , toDescList

    -- * Filter

    , filter
    , filterWithKey
    , restrictKeys
    , withoutKeys
    , partition
    , partitionWithKey

    , mapMaybe
    , mapMaybeWithKey
    , mapEither
    , mapEitherWithKey

    -- * Submap

    , isSubmapOf, isSubmapOfBy
    , isProperSubmapOf, isProperSubmapOfBy

    -- * Indexed

    , lookupIndex
    , findIndex
    , elemAt
    , updateAt
    , deleteAt
    , take
    , drop
    , splitAt

    -- * Others

    , idFromSet
    , memorizeFunction
    , inverse
    , pseudoInverse
    , enumerateMaps
) where
import           Prelude  hiding      (lookup, map, filter, drop, take, splitAt, foldr, foldl, null)
import           Data.WeakSet         (Set)
import qualified Data.WeakSet       as Set
import           Data.WeakSet.Safe
import qualified Data.List          as L
import           Data.Maybe           (fromJust)
import           Control.Applicative  (liftA3)
import qualified Data.Foldable      as Foldable

-- | An association list is a list of pairs (key,value).

type AssociationList k v = [(k,v)]

-- | A weak map is a weak set of pairs (key,value) such that their should only be one pair with a given key.

--

-- It is an abstract type, the smart constructor is `weakMap`.

data Map k v = Map {-# UNPACK #-} !(Set (k,v))

instance (Eq k, Eq v) => Eq (Map k v) where
    Map k v
m1 == :: Map k v -> Map k v -> Bool
== Map k v
m2 = (Map k v -> Set (k, v)
forall k v. Eq k => Map k v -> Set (k, v)
mapToSet Map k v
m1) Set (k, v) -> Set (k, v) -> Bool
forall a. Eq a => a -> a -> Bool
== (Map k v -> Set (k, v)
forall k v. Eq k => Map k v -> Set (k, v)
mapToSet Map k v
m2)

instance (Show k, Show v) => Show (Map k v) where
    show :: Map k v -> String
show (Map Set (k, v)
al) = String
"(weakMap "String -> ShowS
forall a. [a] -> [a] -> [a]
++ ShowS
forall a. [a] -> [a]
init String
rest String -> ShowS
forall a. [a] -> [a] -> [a]
++String
")"
        where
            (Char
'(':Char
's':Char
'e':Char
't':Char
' ':String
rest)= Set (k, v) -> String
forall a. Show a => a -> String
show Set (k, v)
al

instance Semigroup (Map k v) where
    (Map Set (k, v)
al1) <> :: Map k v -> Map k v -> Map k v
<> (Map Set (k, v)
al2) = Set (k, v) -> Map k v
forall k v. Set (k, v) -> Map k v
Map (Set (k, v) -> Map k v) -> Set (k, v) -> Map k v
forall a b. (a -> b) -> a -> b
$ Set (k, v)
al1 Set (k, v) -> Set (k, v) -> Set (k, v)
forall a. Semigroup a => a -> a -> a
<> Set (k, v)
al2

instance Monoid (Map k v) where
    mempty :: Map k v
mempty = Set (k, v) -> Map k v
forall k v. Set (k, v) -> Map k v
Map ([(k, v)] -> Set (k, v)
forall a. [a] -> Set a
set [])

instance Functor (Map k) where
    fmap :: forall a b. (a -> b) -> Map k a -> Map k b
fmap a -> b
f (Map Set (k, a)
al) = Set (k, b) -> Map k b
forall k v. Set (k, v) -> Map k v
Map (Set (k, b) -> Map k b) -> Set (k, b) -> Map k b
forall a b. (a -> b) -> a -> b
$ (\(k
k,a
v) -> (k
k,a -> b
f a
v)) ((k, a) -> (k, b)) -> Set (k, a) -> Set (k, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k, a)
al


-- Construction


-- | /O(1)/. The smart constructor of weak maps. This is the only way of instantiating a `Map`.

--

-- Takes an association list and returns a function which maps to each key the value associated.

--

-- If several pairs have the same keys, they are kept until the user wants an association list back.

weakMap :: AssociationList k v -> Map k v
weakMap :: forall k v. AssociationList k v -> Map k v
weakMap AssociationList k v
al = Set (k, v) -> Map k v
forall k v. Set (k, v) -> Map k v
Map (Set (k, v) -> Map k v) -> Set (k, v) -> Map k v
forall a b. (a -> b) -> a -> b
$ AssociationList k v -> Set (k, v)
forall a. [a] -> Set a
set (AssociationList k v -> Set (k, v))
-> AssociationList k v -> Set (k, v)
forall a b. (a -> b) -> a -> b
$ AssociationList k v
al

-- | /O(1)/. Construct a 'Map' from a 'Set' of pairs (key,value).

weakMapFromSet :: Set (k,v) -> Map k v
weakMapFromSet :: forall k v. Set (k, v) -> Map k v
weakMapFromSet Set (k, v)
s = Set (k, v) -> Map k v
forall k v. Set (k, v) -> Map k v
Map Set (k, v)
s

-- | /O(1)/. Alias of `weakMap` for backward compatibility with Data.Map.

fromList :: AssociationList k v -> Map k v
fromList :: forall k v. AssociationList k v -> Map k v
fromList = AssociationList k v -> Map k v
forall k v. AssociationList k v -> Map k v
weakMap

-- | Alias of mempty for backward compatibility with Data.Map.

empty :: Map k a
empty :: forall k v. Map k v
empty = Map k a
forall a. Monoid a => a
mempty

-- | /O(1)/. A map with a single pair (key,value).

singleton :: k -> a -> Map k a
singleton :: forall k a. k -> a -> Map k a
singleton k
k a
v = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ [(k, a)] -> Set (k, a)
forall a. [a] -> Set a
set [(k
k,a
v)]

-- | /O(n)/.  Build a map from a set of keys and a function which for each key computes its value.

fromSet :: (k -> a) -> Set k -> Map k a
fromSet :: forall k a. (k -> a) -> Set k -> Map k a
fromSet k -> a
f Set k
s = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ (\k
x -> (k
x, k -> a
f k
x)) (k -> (k, a)) -> Set k -> Set (k, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set k
s

-- | /O(n)/. Build a map from a list of key/value pairs with a combining function. 

fromListWith :: (Eq k) => (a -> a -> a) -> [(k, a)] -> Map k a 
fromListWith :: forall k a. Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
fromListWith a -> a -> a
f [(k, a)]
xs = (k -> a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey (\k
_ a
x a
y -> a -> a -> a
f a
x a
y) [(k, a)]
xs

-- | /O(n)/. Build a map from a list of key/value pairs with a combining function. 

fromListWithKey :: (Eq k) => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey :: forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey k -> a -> a -> a
c [] = Map k a
forall k v. Map k v
empty
fromListWithKey k -> a -> a -> a
c ((k
k,a
v):[(k, a)]
xs) = (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey k -> a -> a -> a
c k
k a
v ((k -> a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey k -> a -> a -> a
c [(k, a)]
xs)

-- | Alias for backward compatibility.

fromAscList :: Eq k => [(k, a)] -> Map k a 
fromAscList :: forall k a. Eq k => [(k, a)] -> Map k a
fromAscList = AssociationList k a -> Map k a
forall k v. AssociationList k v -> Map k v
fromList

-- | Alias for backward compatibility.

fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a 
fromAscListWith :: forall k a. Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
fromAscListWith = (a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
fromListWith

-- | Alias for backward compatibility.

fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a 
fromAscListWithKey :: forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromAscListWithKey = (k -> a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey 

-- | Alias for backward compatibility.

fromDistinctAscList :: [(k, a)] -> Map k a 
fromDistinctAscList :: forall k v. AssociationList k v -> Map k v
fromDistinctAscList = AssociationList k a -> Map k a
forall k v. AssociationList k v -> Map k v
fromList

-- | Alias for backward compatibility.

fromDescList :: Eq k => [(k, a)] -> Map k a
fromDescList :: forall k a. Eq k => [(k, a)] -> Map k a
fromDescList = AssociationList k a -> Map k a
forall k v. AssociationList k v -> Map k v
fromList

-- | Alias for backward compatibility.

fromDescListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a 
fromDescListWith :: forall k a. Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
fromDescListWith = (a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
fromListWith

-- | Alias for backward compatibility.

fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a 
fromDescListWithKey :: forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromDescListWithKey = (k -> a -> a -> a) -> [(k, a)] -> Map k a
forall k a. Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
fromListWithKey

-- | Alias for backward compatibility.

fromDistinctDescList :: [(k, a)] -> Map k a 
fromDistinctDescList :: forall k v. AssociationList k v -> Map k v
fromDistinctDescList = AssociationList k a -> Map k a
forall k v. AssociationList k v -> Map k v
fromList

-- Operators



-- | /O(n)/.  Lookup the value at a key in the map. If the map is not defined on the given value returns `Nothing`, otherwise returns `Just` the image.

--

-- This function is like `lookup` in Data.Map for function (beware: the order of the argument are reversed).

(|?|) :: (Eq k) => Map k v -> k -> Maybe v
|?| :: forall k v. Eq k => Map k v -> k -> Maybe v
(|?|) (Map Set (k, v)
al) k
key = (Set v -> Maybe v
forall a. Set a -> Maybe a
Set.setToMaybe)(Set v -> Maybe v)
-> (Set (Maybe v) -> Set v) -> Set (Maybe v) -> Maybe v
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Set (Maybe v) -> Set v
forall a. Set (Maybe a) -> Set a
Set.catMaybes) (Set (Maybe v) -> Maybe v) -> Set (Maybe v) -> Maybe v
forall a b. (a -> b) -> a -> b
$ (\(k
k,v
v) -> if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
key then v -> Maybe v
forall a. a -> Maybe a
Just v
v else Maybe v
forall a. Maybe a
Nothing) ((k, v) -> Maybe v) -> Set (k, v) -> Set (Maybe v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k, v)
al

-- | /O(n)/. Unsafe version of `(|?|)`.

--

-- This function is like `(!)` in Data.Map, it is renamed to avoid name collisions.

(|!|) :: (Eq k) => Map k v -> k -> v
|!| :: forall k v. Eq k => Map k v -> k -> v
(|!|) Map k v
f k
key
    | Maybe v -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe v
safeResult = String -> v
forall a. HasCallStack => String -> a
error String
"WeakMap.|!|: element not in the map"
    | Bool
otherwise = v
result
    where
        safeResult :: Maybe v
safeResult = Map k v
f Map k v -> k -> Maybe v
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
key
        Just v
result = Maybe v
safeResult
        
-- | O(n). Find the value at a key. Calls `error` when the element can not be found.

-- 

-- Alias of `(|!|)` for backward compatibility purposes. 

(!) :: (Eq k) => Map k a -> k -> a
! :: forall k v. Eq k => Map k v -> k -> v
(!) = Map k a -> k -> a
forall k v. Eq k => Map k v -> k -> v
(|!|)

-- | Alias for backward compatibility.

(!?) :: Eq k => Map k a -> k -> Maybe a
!? :: forall k v. Eq k => Map k v -> k -> Maybe v
(!?) = Map k a -> k -> Maybe a
forall k v. Eq k => Map k v -> k -> Maybe v
(|?|)


-- | See `difference`.

(\\) :: (Eq k) => Map k a -> Map k b -> Map k a
\\ :: forall k a b. Eq k => Map k a -> Map k b -> Map k a
(\\) = Map k a -> Map k b -> Map k a
forall k a b. Eq k => Map k a -> Map k b -> Map k a
difference

-- | /O(n*m)/. Difference of two maps. Return elements of the first map not existing in the second map.

difference :: (Eq k) => Map k a -> Map k b -> Map k a
difference :: forall k a b. Eq k => Map k a -> Map k b -> Map k a
difference (Map Set (k, a)
al) Map k b
m2 = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Bool) -> Set (k, a) -> Set (k, a)
forall a. (a -> Bool) -> Set a -> Set a
Set.filter (\(k
k,a
v) -> Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ k
k k -> Set k -> Bool
forall a. Eq a => a -> Set a -> Bool
`isIn` (Map k b -> Set k
forall k v. Map k v -> Set k
keys' Map k b
m2)) Set (k, a)
al


-- Query



-- | /O(n^2)/. The number of elements in the map. 

size :: (Eq k) => Map k a -> Int
size :: forall k a. Eq k => Map k a -> Int
size Map k a
m = [(k, a)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length ([(k, a)] -> Int) -> [(k, a)] -> Int
forall a b. (a -> b) -> a -> b
$ Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k a
m

-- | /O(1)/. Return wether the map is empty.

null :: Map k a -> Bool
null :: forall k a. Map k a -> Bool
null (Map Set (k, a)
al) = Set (k, a) -> Bool
forall a. Set a -> Bool
Set.null Set (k, a)
al

-- | /O(n)/. Is the key a member of the map? See also `notMember`. 

member :: (Eq k) => k -> Map k a -> Bool
member :: forall k a. Eq k => k -> Map k a -> Bool
member k
k Map k a
m = Bool -> Bool
not(Bool -> Bool) -> (Maybe a -> Bool) -> Maybe a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null) (Maybe a -> Bool) -> Maybe a -> Bool
forall a b. (a -> b) -> a -> b
$ Map k a
m Map k a -> k -> Maybe a
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
k

-- | /O(n)/. Negation of `member`. 

notMember :: (Eq k) => k -> Map k a -> Bool
notMember :: forall k a. Eq k => k -> Map k a -> Bool
notMember k
k Map k a
m = Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null (Maybe a -> Bool) -> Maybe a -> Bool
forall a b. (a -> b) -> a -> b
$ Map k a
m Map k a -> k -> Maybe a
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
k

-- | /O(n)/. Just like `(|?|)` but the order of argument is reversed. For backward compatibility with Data.Map.

lookup :: (Eq k) => k -> Map k a -> Maybe a
lookup :: forall k a. Eq k => k -> Map k a -> Maybe a
lookup k
x Map k a
y = Map k a -> k -> Maybe a
forall k v. Eq k => Map k v -> k -> Maybe v
(|?|) Map k a
y k
x

-- | /O(n)/. Apply a map to a given value, if the key is in the domain returns the image, otherwise return a default value.

--

-- This function is like `findWithDefault` (the order of the argument are reversed though).

findWithDefault' :: (Eq k) => Map k v -> v -> k -> v
findWithDefault' :: forall k v. Eq k => Map k v -> v -> k -> v
findWithDefault' Map k v
f v
d k
key
    | Maybe v -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe v
safeResult = v
d
    | Bool
otherwise = v
result
    where
        safeResult :: Maybe v
safeResult = Map k v
f Map k v -> k -> Maybe v
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
key
        Just v
result = Maybe v
safeResult
        
-- | /O(n)/. The expression @(findWithDefault def k map)@ returns the value at key k or returns default value def when the key is not in the map. 

findWithDefault :: (Eq k) => a -> k -> Map k a -> a
findWithDefault :: forall k a. Eq k => a -> k -> Map k a -> a
findWithDefault a
d k
key Map k a
f = Map k a -> a -> k -> a
forall k v. Eq k => Map k v -> v -> k -> v
findWithDefault' Map k a
f a
d k
key


-- Insertion



-- | /O(1)/. Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value. `insert` is equivalent to @`insertWith` `const`@. 

insert :: k -> a -> Map k a -> Map k a
insert :: forall k a. k -> a -> Map k a -> Map k a
insert k
k a
v (Map Set (k, a)
al) = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ (k, a) -> Set (k, a) -> Set (k, a)
forall a. a -> Set a -> Set a
Set.insert (k
k,a
v) Set (k, a)
al

-- | /O(n)/. Insert with a function, combining new value and old value. @insertWith f key value mp@ will insert the pair (key, value) into mp if key does not exist in the function. If the key does exist, the function will insert the pair (key, f new_value old_value). 

insertWith :: (Eq k) => (v -> v -> v) -> k -> v -> Map k v -> Map k v
insertWith :: forall k v. Eq k => (v -> v -> v) -> k -> v -> Map k v -> Map k v
insertWith v -> v -> v
comb k
k v
v Map k v
f
    | Maybe v -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe v
prev = k -> v -> Map k v -> Map k v
forall k a. k -> a -> Map k a -> Map k a
insert k
k v
v Map k v
f
    | Bool
otherwise = k -> v -> Map k v -> Map k v
forall k a. k -> a -> Map k a -> Map k a
insert k
k (v -> v -> v
comb v
v v
prev_value) Map k v
f
    where
        prev :: Maybe v
prev = Map k v
f Map k v -> k -> Maybe v
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
k
        Just v
prev_value = Maybe v
prev

-- | /O(n)/. Alias for `insertWith` for backward compatibility purposes.

insertWith' :: (Eq k) => (a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWith' :: forall k v. Eq k => (v -> v -> v) -> k -> v -> Map k v -> Map k v
insertWith' = (a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k v. Eq k => (v -> v -> v) -> k -> v -> Map k v -> Map k v
insertWith

-- | /O(n)/. Insert with a function, combining key, new value and old value. @insertWithKey f key value mp@ will insert the pair (key, value) into mp if key does not exist in the function. If the key does exist, the function will insert the pair (key,f key new_value old_value). Note that the key passed to f is the same key passed to `insertWithKey`. 

insertWithKey :: (Eq k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey :: forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey k -> a -> a -> a
comb k
k a
v Map k a
f
    | Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
prev = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insert k
k a
v Map k a
f
    | Bool
otherwise = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insert k
k (k -> a -> a -> a
comb k
k a
v a
prev_value) Map k a
f
    where
        prev :: Maybe a
prev = Map k a
f Map k a -> k -> Maybe a
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
k
        Just a
prev_value = Maybe a
prev

-- | /O(n)/. Alias for `insertWithKey` for backward compatibility purposes.

insertWithKey' :: (Eq k) => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey' :: forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey' = (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey

-- | /O(n)/.  Combines insert operation with old value retrieval. The expression @(insertLookupWithKey f k x map)@ is a pair where the first element is equal to @(lookup k map)@ and the second element equal to @(insertWithKey f k x map)@. 

insertLookupWithKey :: (Eq k) => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
insertLookupWithKey :: forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
insertLookupWithKey k -> a -> a -> a
f k
k a
x Map k a
map = (k -> Map k a -> Maybe a
forall k a. Eq k => k -> Map k a -> Maybe a
lookup k
k Map k a
map, (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
insertWithKey k -> a -> a -> a
f k
k a
x Map k a
map)

-- | /O(n)/. Alias for `insertLookupWithKey` for backward compatibility purposes.

insertLookupWithKey' :: (Eq k) => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
insertLookupWithKey' :: forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
insertLookupWithKey' = (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
insertLookupWithKey

-- | /O(1)/. Insert a new key and value if it is Just in the map. If the key is already present in the map, the associated value is replaced with the supplied value.

insertMaybe :: (Eq k) => k -> Maybe a -> Map k a -> Map k a
insertMaybe :: forall k a. Eq k => k -> Maybe a -> Map k a -> Map k a
insertMaybe k
_ Maybe a
Nothing Map k a
m = Map k a
m
insertMaybe k
k (Just a
v) (Map Set (k, a)
al) = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ (k, a) -> Set (k, a) -> Set (k, a)
forall a. a -> Set a -> Set a
Set.insert (k
k,a
v) Set (k, a)
al


-- Delete/update



-- | /O(n)/. Delete a key and its value from the map. When the key is not a member of the map, the original map is returned. 

delete :: (Eq k) => k -> Map k a -> Map k a
delete :: forall k a. Eq k => k -> Map k a -> Map k a
delete k
key (Map Set (k, a)
al) = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Bool) -> Set (k, a) -> Set (k, a)
forall a. (a -> Bool) -> Set a -> Set a
Set.filter (\(k
k,a
v) -> k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
/= k
k) Set (k, a)
al

-- | /O(n)/. Update a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned. 

adjust :: (Eq k) => (a -> a) -> k -> Map k a -> Map k a
adjust :: forall k a. Eq k => (a -> a) -> k -> Map k a -> Map k a
adjust a -> a
func k
key (Map Set (k, a)
al) = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ (\(k
k,a
v) -> if k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k then (k
k, a -> a
func a
v) else (k
k,a
v)) ((k, a) -> (k, a)) -> Set (k, a) -> Set (k, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k, a)
al

-- | /O(n)/. Adjust a value at a specific key. When the key is not a member of the map, the original map is returned. 

adjustWithKey :: (Eq k) => (k -> a -> a) -> k -> Map k a -> Map k a
adjustWithKey :: forall k a. Eq k => (k -> a -> a) -> k -> Map k a -> Map k a
adjustWithKey k -> a -> a
func k
key (Map Set (k, a)
al) = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ (\(k
k,a
v) -> if k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k then (k
k, k -> a -> a
func k
k a
v) else (k
k,a
v)) ((k, a) -> (k, a)) -> Set (k, a) -> Set (k, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k, a)
al

-- | /O(n)/. The expression (`alter` f k map) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a `Map`. In short : `lookup` k (`alter` f k m) = f (`lookup` k m). 

alter :: (Eq k) => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
alter :: forall k a. Eq k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
alter Maybe a -> Maybe a
func k
key Map k a
f
    | Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
lookupKey = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insert k
key a
unpackedImageNothing Map k a
f
    | Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
result = k -> Map k a -> Map k a
forall k a. Eq k => k -> Map k a -> Map k a
delete k
key Map k a
f
    | Bool
otherwise = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insert k
key a
unpackedResult Map k a
f
    where
        lookupKey :: Maybe a
lookupKey = Map k a
f Map k a -> k -> Maybe a
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
key
        result :: Maybe a
result = Maybe a -> Maybe a
func Maybe a
lookupKey
        Just a
unpackedResult = Maybe a
result
        Just a
unpackedImageNothing = Maybe a -> Maybe a
func Maybe a
forall a. Maybe a
Nothing
      
-- | /O(n)/. The expression (`alterF` f k map) alters the value x at k, or absence thereof. `alterF` can be used to inspect, insert, delete, or update a value in a Map.      

alterF :: (Functor f, Eq k) => (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
alterF :: forall (f :: * -> *) k a.
(Functor f, Eq k) =>
(Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
alterF Maybe a -> f (Maybe a)
func k
key Map k a
f
    | Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
lookupKey = Maybe a -> Map k a
add (Maybe a -> Map k a) -> f (Maybe a) -> f (Map k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Maybe a)
imageNothing
    | Bool
otherwise = Maybe a -> Map k a
treat (Maybe a -> Map k a) -> f (Maybe a) -> f (Map k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Maybe a)
result
    where
        lookupKey :: Maybe a
lookupKey = Map k a
f Map k a -> k -> Maybe a
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
key
        result :: f (Maybe a)
result = Maybe a -> f (Maybe a)
func Maybe a
lookupKey
        treat :: Maybe a -> Map k a
treat Maybe a
x = if Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
x then k -> Map k a -> Map k a
forall k a. Eq k => k -> Map k a -> Map k a
delete k
key Map k a
f else k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insert k
key (Maybe a -> a
forall a. HasCallStack => Maybe a -> a
fromJust Maybe a
x) Map k a
f
        imageNothing :: f (Maybe a)
imageNothing = Maybe a -> f (Maybe a)
func Maybe a
forall a. Maybe a
Nothing
        add :: Maybe a -> Map k a
add Maybe a
x = if Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
x then Map k a
f else k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insert k
key (Maybe a -> a
forall a. HasCallStack => Maybe a -> a
fromJust Maybe a
x) Map k a
f


-- | /O(n)/. The expression @(update f k map)@ updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y. 

update :: (Eq k) => (a -> Maybe a) -> k -> Map k a -> Map k a
update :: forall k a. Eq k => (a -> Maybe a) -> k -> Map k a -> Map k a
update a -> Maybe a
f = (k -> a -> Maybe a) -> k -> Map k a -> Map k a
forall k a. Eq k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
updateWithKey (\k
_ a
x -> a -> Maybe a
f a
x)

-- | /O(n)/. The expression @(updateWithKey f k map)@ updates the value x at k (if it is in the map). If (f k x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y. 

updateWithKey :: (Eq k) => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
updateWithKey :: forall k a. Eq k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
updateWithKey k -> a -> Maybe a
f k
key Map k a
m
    | Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
look = Map k a
m
    | Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
res = k -> Map k a -> Map k a
forall k a. Eq k => k -> Map k a -> Map k a
delete k
key Map k a
m
    | Bool
otherwise = k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insert k
key a
r Map k a
m
    where
        look :: Maybe a
look = Map k a
m Map k a -> k -> Maybe a
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
key
        Just a
v = Maybe a
look
        res :: Maybe a
res = k -> a -> Maybe a
f k
key a
v
        Just a
r = Maybe a
res

-- | /O(n)/. Lookup and update. See also `updateWithKey`. The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted. 

updateLookupWithKey :: (Eq k) => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
updateLookupWithKey :: forall k a.
Eq k =>
(k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
updateLookupWithKey k -> a -> Maybe a
f k
key Map k a
m
    | Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
look = (Maybe a
forall a. Maybe a
Nothing, Map k a
m)
    | Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
res = (a -> Maybe a
forall a. a -> Maybe a
Just a
v, k -> Map k a -> Map k a
forall k a. Eq k => k -> Map k a -> Map k a
delete k
key Map k a
m)
    | Bool
otherwise = (a -> Maybe a
forall a. a -> Maybe a
Just a
v, k -> a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a
insert k
key a
r Map k a
m)
    where
        look :: Maybe a
look = Map k a
m Map k a -> k -> Maybe a
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
key
        Just a
v = Maybe a
look
        res :: Maybe a
res = k -> a -> Maybe a
f k
key a
v
        Just a
r = Maybe a
res


-- Combine



-- | /O(n)/. The expression @(`union` t1 t2)@ takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered. 

union :: (Eq k) => Map k a -> Map k a -> Map k a
union :: forall k a. Eq k => Map k a -> Map k a -> Map k a
union (Map Set (k, a)
al1) (Map Set (k, a)
al2) = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ Set (k, a)
al1 Set (k, a) -> Set (k, a) -> Set (k, a)
forall a. Set a -> Set a -> Set a
||| Set (k, a)
al2

-- | /O(n)/. Union with a combining function.

unionWith :: (Eq k) => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith :: forall k a. Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith a -> a -> a
f Map k a
m1 Map k a
m2 = (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a.
Eq k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey (\k
_ a
x a
y -> a -> a -> a
f a
x a
y) Map k a
m1 Map k a
m2

-- | /O(n)/.

-- Union with a combining function. 

--

-- > let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value

-- > unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]

unionWithKey :: (Eq k) => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey :: forall k a.
Eq k =>
(k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWithKey k -> a -> a -> a
f (Map Set (k, a)
al) Map k a
m2 = Map k a
new_m1 Map k a -> Map k a -> Map k a
forall k a. Eq k => Map k a -> Map k a -> Map k a
`union` Map k a
m2
    where
        new_m1 :: Map k a
new_m1 = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ (\(k
k,a
v) -> if k -> Map k a -> Bool
forall k a. Eq k => k -> Map k a -> Bool
member k
k Map k a
m2 then (k
k,k -> a -> a -> a
f k
k a
v (Map k a
m2 Map k a -> k -> a
forall k v. Eq k => Map k v -> k -> v
|!| k
k)) else (k
k,a
v)) ((k, a) -> (k, a)) -> Set (k, a) -> Set (k, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k, a)
al

-- | The union of a list of maps: @(unions == foldl union empty)@. 

unions :: (Eq k) => [Map k a] -> Map k a
unions :: forall k a. Eq k => [Map k a] -> Map k a
unions = (Map k a -> Map k a -> Map k a) -> Map k a -> [Map k a] -> Map k a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl Map k a -> Map k a -> Map k a
forall k a. Eq k => Map k a -> Map k a -> Map k a
union Map k a
forall k v. Map k v
empty

-- | The union of a list of maps, with a combining operation: @(unionsWith f == foldl (unionWith f) empty)@. 

unionsWith :: (Eq k) => (a -> a -> a) -> [Map k a] -> Map k a
unionsWith :: forall k a. Eq k => (a -> a -> a) -> [Map k a] -> Map k a
unionsWith a -> a -> a
f = (Map k a -> Map k a -> Map k a) -> Map k a -> [Map k a] -> Map k a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl ((a -> a -> a) -> Map k a -> Map k a -> Map k a
forall k a. Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
unionWith a -> a -> a
f) Map k a
forall k v. Map k v
empty


-- Difference



-- | /O(n*m)/. Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y

differenceWith :: (Eq k) => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWith :: forall k a b.
Eq k =>
(a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWith a -> b -> Maybe a
f Map k a
m1 Map k b
m2 = (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
forall k a b.
Eq k =>
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWithKey (\k
_ a
x b
y -> a -> b -> Maybe a
f a
x b
y) Map k a
m1 Map k b
m2


-- | /O(n*m)/. Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y. 

differenceWithKey :: (Eq k) => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWithKey :: forall k a b.
Eq k =>
(k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
differenceWithKey k -> a -> b -> Maybe a
f (Map Set (k, a)
al) Map k b
m2 = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Maybe (k, a)) -> Set (k, a) -> Set (k, a)
forall a b. (a -> Maybe b) -> Set a -> Set b
Set.mapMaybe (\(k
k,a
v) -> if k -> Map k b -> Bool
forall k a. Eq k => k -> Map k a -> Bool
member k
k Map k b
m2 then ((k, Maybe a) -> Maybe (k, a)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence (k
k, k -> a -> b -> Maybe a
f k
k a
v (Map k b
m2 Map k b -> k -> b
forall k v. Eq k => Map k v -> k -> v
|!| k
k))) else (k, a) -> Maybe (k, a)
forall a. a -> Maybe a
Just (k
k, a
v)) Set (k, a)
al


-- Intersection



-- | /O(n*m)/. Intersection of two maps. Return data in the first map for the keys existing in both maps. 

intersection :: (Eq) k => Map k a -> Map k b -> Map k a
intersection :: forall k a b. Eq k => Map k a -> Map k b -> Map k a
intersection = (a -> b -> a) -> Map k a -> Map k b -> Map k a
forall k a b c.
Eq k =>
(a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWith a -> b -> a
forall a b. a -> b -> a
const      
    
-- | /O(n*m)/. Intersection with a combining function. 

intersectionWith :: (Eq k) => (a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWith :: forall k a b c.
Eq k =>
(a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWith a -> b -> c
f Map k a
m1 Map k b
m2 = (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
forall k a b c.
Eq k =>
(k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey (\k
_ a
x b
y -> a -> b -> c
f a
x b
y) Map k a
m1 Map k b
m2

-- | /O(n*m)/. Intersection with a combining function.

intersectionWithKey :: (Eq k) => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey :: forall k a b c.
Eq k =>
(k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWithKey k -> a -> b -> c
f (Map Set (k, a)
al) Map k b
m2 = Set (k, c) -> Map k c
forall k v. Set (k, v) -> Map k v
Map (Set (k, c) -> Map k c) -> Set (k, c) -> Map k c
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Maybe (k, c)) -> Set (k, a) -> Set (k, c)
forall a b. (a -> Maybe b) -> Set a -> Set b
Set.mapMaybe (\(k
k,a
v) -> if k -> Map k b -> Bool
forall k a. Eq k => k -> Map k a -> Bool
member k
k Map k b
m2 then (k, c) -> Maybe (k, c)
forall a. a -> Maybe a
Just (k
k, k -> a -> b -> c
f k
k a
v (Map k b
m2 Map k b -> k -> b
forall k v. Eq k => Map k v -> k -> v
|!| k
k)) else Maybe (k, c)
forall a. Maybe a
Nothing) Set (k, a)
al

-- | Check whether the key sets of two maps are disjoint.

disjoint :: Eq k => Map k a -> Map k b -> Bool
disjoint :: forall k a b. Eq k => Map k a -> Map k b -> Bool
disjoint Map k a
m1 Map k b
m2 = Map k a -> Bool
forall k a. Map k a -> Bool
null (Map k a -> Bool) -> Map k a -> Bool
forall a b. (a -> b) -> a -> b
$ Map k a -> Map k b -> Map k a
forall k a b. Eq k => Map k a -> Map k b -> Map k a
intersection Map k a
m1 Map k b
m2

-- | Relate the keys of one map to the values of the other, by using the values of the former as keys for lookups in the latter.

compose :: Eq b => Map b c -> Map a b -> Map a c 
compose :: forall b c a. Eq b => Map b c -> Map a b -> Map a c
compose = Map b c -> Map a b -> Map a c
forall b c a. Eq b => Map b c -> Map a b -> Map a c
(|.|)

-- | Compose two functions. If the two functions are not composable, strips the functions until they can compose.

(|.|) :: (Eq b) => Map b c -> Map a b -> Map a c
|.| :: forall b c a. Eq b => Map b c -> Map a b -> Map a c
(|.|) Map b c
f2 (Map Set (a, b)
al) = Set (a, c) -> Map a c
forall k v. Set (k, v) -> Map k v
Map (Set (a, c) -> Map a c) -> Set (a, c) -> Map a c
forall a b. (a -> b) -> a -> b
$ ((a, b) -> Maybe (a, c)) -> Set (a, b) -> Set (a, c)
forall a b. (a -> Maybe b) -> Set a -> Set b
Set.mapMaybe (\(a
k,b
v) -> (a, Maybe c) -> Maybe (a, c)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence (a
k,(Map b c
f2 Map b c -> b -> Maybe c
forall k v. Eq k => Map k v -> k -> Maybe v
|?| b
v))) Set (a, b)
al

-- Traversal


-- | /O(n)/. Map a function over all values in the map. 

map :: (a -> b) -> Map k a -> Map k b
map :: forall a b k. (a -> b) -> Map k a -> Map k b
map = (a -> b) -> Map k a -> Map k b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap

-- | /O(n)/. Map a function over all values in the map. 

mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
mapWithKey :: forall k a b. (k -> a -> b) -> Map k a -> Map k b
mapWithKey k -> a -> b
f (Map Set (k, a)
al) = Set (k, b) -> Map k b
forall k v. Set (k, v) -> Map k v
Map (Set (k, b) -> Map k b) -> Set (k, b) -> Map k b
forall a b. (a -> b) -> a -> b
$ (\(k
k,a
a) -> (k
k, k -> a -> b
f k
k a
a)) ((k, a) -> (k, b)) -> Set (k, a) -> Set (k, b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k, a)
al

-- | /O(n)/. The function `mapAccum` threads an accumulating argument through the map. 

mapAccum :: (Eq k) => (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccum :: forall k a b c.
Eq k =>
(a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccum a -> b -> (a, c)
f a
d Map k b
m = (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall k a b c.
Eq k =>
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumWithKey (\a
a k
k b
b -> a -> b -> (a, c)
f a
a b
b) a
d Map k b
m

-- | /O(n^2)/. The function `mapAccumWithKey` threads an accumulating argument through the map. 

mapAccumWithKey :: (Eq k) => (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumWithKey :: forall k a b c.
Eq k =>
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumWithKey a -> k -> b -> (a, c)
f a
d Map k b
m = Set (k, c) -> Map k c
forall k v. Set (k, v) -> Map k v
Map (Set (k, c) -> Map k c)
-> ([(k, c)] -> Set (k, c)) -> [(k, c)] -> Map k c
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [(k, c)] -> Set (k, c)
forall a. [a] -> Set a
set ([(k, c)] -> Map k c) -> (a, [(k, c)]) -> (a, Map k c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> [(k, b)] -> [(k, c)] -> (a, [(k, c)])
helper a
d [(k, b)]
al []
    where 
        al :: [(k, b)]
al = Map k b -> [(k, b)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k b
m
        helper :: a -> [(k, b)] -> [(k, c)] -> (a, [(k, c)])
helper a
d [] [(k, c)]
l = (a
d,[(k, c)]
l)
        helper a
d ((k
k,b
v):[(k, b)]
xs) [(k, c)]
l = a -> [(k, b)] -> [(k, c)] -> (a, [(k, c)])
helper a
new [(k, b)]
xs ((k
k,c
val)(k, c) -> [(k, c)] -> [(k, c)]
forall a. a -> [a] -> [a]
:[(k, c)]
l) 
            where
                (a
new,c
val) = a -> k -> b -> (a, c)
f a
d k
k b
v


-- | /O(n)/. Alias of `mapAccumWithKey` for backward compatibility purposes. We don't implement it because order of pairs should not matter.

mapAccumRWithKey :: (Eq k) => (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumRWithKey :: forall k a b c.
Eq k =>
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumRWithKey = (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
forall k a b c.
Eq k =>
(a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
mapAccumWithKey


-- | /O(n)/. @mapKeys f s@ is the map obtained by applying f to each key of s. 

mapKeys :: (k1 -> k2) -> Map k1 a -> Map k2 a
mapKeys :: forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
mapKeys k1 -> k2
f (Map Set (k1, a)
al) = Set (k2, a) -> Map k2 a
forall k v. Set (k, v) -> Map k v
Map (Set (k2, a) -> Map k2 a) -> Set (k2, a) -> Map k2 a
forall a b. (a -> b) -> a -> b
$ (\(k1
k,a
v) -> (k1 -> k2
f k1
k,a
v)) ((k1, a) -> (k2, a)) -> Set (k1, a) -> Set (k2, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k1, a)
al

-- | /O(n^2)/. @mapKeysWith c f s@ is the map obtained by applying f to each key of s. 

--

-- The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case the associated values will be combined using c. 

mapKeysWith :: (Eq k1, Eq k2) => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
mapKeysWith :: forall k1 k2 a.
(Eq k1, Eq k2) =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
mapKeysWith a -> a -> a
f k1 -> k2
g Map k1 a
m = [(k1, a)] -> Map k2 a -> Map k2 a
helper [(k1, a)]
al Map k2 a
forall k v. Map k v
empty
    where
        al :: [(k1, a)]
al = Map k1 a -> [(k1, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k1 a
m
        helper :: [(k1, a)] -> Map k2 a -> Map k2 a
helper [] Map k2 a
r = Map k2 a
r
        helper ((k1
k,a
v):[(k1, a)]
xs) Map k2 a
r
            | k1 -> k2
g k1
k k2 -> Map k2 a -> Bool
forall k a. Eq k => k -> Map k a -> Bool
`member` Map k2 a
r = [(k1, a)] -> Map k2 a -> Map k2 a
helper [(k1, a)]
xs (k2 -> a -> Map k2 a -> Map k2 a
forall k a. k -> a -> Map k a -> Map k a
insert (k1 -> k2
g k1
k) (a -> a -> a
f a
v (Map k2 a
r Map k2 a -> k2 -> a
forall k v. Eq k => Map k v -> k -> v
|!| (k1 -> k2
g k1
k))) Map k2 a
r)
            | Bool
otherwise = [(k1, a)] -> Map k2 a -> Map k2 a
helper [(k1, a)]
xs (k2 -> a -> Map k2 a -> Map k2 a
forall k a. k -> a -> Map k a -> Map k a
insert (k1 -> k2
g k1
k) a
v Map k2 a
r)

-- | Alias of `mapKeys` defined for backward compatibility.

mapKeysMonotonic ::  (k1 -> k2) -> Map k1 a -> Map k2 a
mapKeysMonotonic :: forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
mapKeysMonotonic = (k1 -> k2) -> Map k1 a -> Map k2 a
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
mapKeys

-- | Eq typeclass must be added.

--

-- It behaves much like a regular traverse except that the traversing function also has access to the key associated with a value and the values are forced before they are installed in the result map.

traverseWithKey :: (Applicative t, Eq k, Eq a) => (k -> a -> t b) -> Map k a -> t (Map k b) 
traverseWithKey :: forall (t :: * -> *) k a b.
(Applicative t, Eq k, Eq a) =>
(k -> a -> t b) -> Map k a -> t (Map k b)
traverseWithKey k -> a -> t b
f Map k a
m = (k -> a -> t (Map k b) -> t (Map k b))
-> t (Map k b) -> Map k a -> t (Map k b)
forall a k b.
(Eq a, Eq k) =>
(k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k a
v t (Map k b)
ys -> (k -> b -> Map k b -> Map k b)
-> t k -> t b -> t (Map k b) -> t (Map k b)
forall (f :: * -> *) a b c d.
Applicative f =>
(a -> b -> c -> d) -> f a -> f b -> f c -> f d
liftA3 k -> b -> Map k b -> Map k b
forall k a. k -> a -> Map k a -> Map k a
insert (k -> t k
forall (f :: * -> *) a. Applicative f => a -> f a
pure k
k) (k -> a -> t b
f k
k a
v) t (Map k b)
ys) (Map k b -> t (Map k b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Map k b
forall a. Monoid a => a
mempty) (AssociationList k a -> Map k a
forall k v. AssociationList k v -> Map k v
fromList(AssociationList k a -> Map k a)
-> (Map k a -> AssociationList k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Map k a -> AssociationList k a
forall k v. Eq k => Map k v -> AssociationList k v
mapToList (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m)

-- | Eq typeclass must be added. Traverse keys/values and collect the Just results.

traverseMaybeWithKey :: (Applicative f, Eq k, Eq a) => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b) 
traverseMaybeWithKey :: forall (f :: * -> *) k a b.
(Applicative f, Eq k, Eq a) =>
(k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
traverseMaybeWithKey k -> a -> f (Maybe b)
f Map k a
m = (k -> a -> f (Map k b) -> f (Map k b))
-> f (Map k b) -> Map k a -> f (Map k b)
forall a k b.
(Eq a, Eq k) =>
(k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey (\k
k a
v f (Map k b)
ys -> (k -> Maybe b -> Map k b -> Map k b)
-> f k -> f (Maybe b) -> f (Map k b) -> f (Map k b)
forall (f :: * -> *) a b c d.
Applicative f =>
(a -> b -> c -> d) -> f a -> f b -> f c -> f d
liftA3 k -> Maybe b -> Map k b -> Map k b
forall k a. Eq k => k -> Maybe a -> Map k a -> Map k a
insertMaybe (k -> f k
forall (f :: * -> *) a. Applicative f => a -> f a
pure k
k) (k -> a -> f (Maybe b)
f k
k a
v) f (Map k b)
ys) (Map k b -> f (Map k b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Map k b
forall a. Monoid a => a
mempty) (AssociationList k a -> Map k a
forall k v. AssociationList k v -> Map k v
fromList(AssociationList k a -> Map k a)
-> (Map k a -> AssociationList k a) -> Map k a -> Map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Map k a -> AssociationList k a
forall k v. Eq k => Map k v -> AssociationList k v
mapToList (Map k a -> Map k a) -> Map k a -> Map k a
forall a b. (a -> b) -> a -> b
$ Map k a
m)

-- Folds


-- | /O(n^2)/. Fold the values in the map using the given right-associative binary operator.

--

-- Note that an Eq constraint must be added.

foldr :: (Eq k) => (a -> b -> b) -> b -> Map k a -> b 
foldr :: forall k a b. Eq k => (a -> b -> b) -> b -> Map k a -> b
foldr a -> b -> b
f b
d Map k a
m = ((k, a) -> b -> b) -> b -> [(k, a)] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
L.foldr (\(k
k,a
v) b
a -> a -> b -> b
f a
v b
a) b
d (Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k a
m)

-- | /O(n^2)/. Fold the values in the map using the given left-associative binary operator.

--

-- Note that an Eq constraint must be added.

foldl :: (Eq k) => (a -> b -> a) -> a -> Map k b -> a 
foldl :: forall k a b. Eq k => (a -> b -> a) -> a -> Map k b -> a
foldl a -> b -> a
f a
d Map k b
m = (a -> (k, b) -> a) -> a -> [(k, b)] -> a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl (\a
a (k
k,b
v) -> a -> b -> a
f a
a b
v) a
d (Map k b -> [(k, b)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k b
m)

-- | `foldrWithKey` from the left.

foldlWithKey :: (Eq k, Eq a) => (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey :: forall k a b.
(Eq k, Eq a) =>
(b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey b -> k -> a -> b
f b
d (Map Set (k, a)
al) = (b -> (k, a) -> b) -> b -> Set (k, a) -> b
forall b a. Eq b => (a -> b -> a) -> a -> Set b -> a
Set.foldl (\b
b (k
k,a
v) -> b -> k -> a -> b
f b
b k
k a
v) b
d Set (k, a)
al

-- | Fold with key.

foldrWithKey :: (Eq a, Eq k) =>(k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey :: forall a k b.
(Eq a, Eq k) =>
(k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey k -> a -> b -> b
f b
d (Map Set (k, a)
al) = ((k, a) -> b -> b) -> b -> Set (k, a) -> b
forall a b. Eq a => (a -> b -> b) -> b -> Set a -> b
Set.foldr (\(k
k,a
v) -> k -> a -> b -> b
f k
k a
v) b
d Set (k, a)
al

-- |  Fold the keys and values in the map using the given monoid.

foldMapWithKey :: (Eq a, Eq k, Monoid m) => (k -> a -> m) -> Map k a -> m
foldMapWithKey :: forall a k m.
(Eq a, Eq k, Monoid m) =>
(k -> a -> m) -> Map k a -> m
foldMapWithKey k -> a -> m
f (Map Set (k, a)
al) = ((k, a) -> m -> m) -> m -> Set (k, a) -> m
forall a b. Eq a => (a -> b -> b) -> b -> Set a -> b
Set.foldr (\(k
k,a
v) m
m -> (k -> a -> m
f k
k a
v) m -> m -> m
forall a. Semigroup a => a -> a -> a
<> m
m) m
forall a. Monoid a => a
mempty Set (k, a)
al


-- Strict folds




-- | Strict foldr.

foldr' :: (Eq k) => (a -> b -> b) -> b -> Map k a -> b
foldr' :: forall k a b. Eq k => (a -> b -> b) -> b -> Map k a -> b
foldr' a -> b -> b
f b
d Map k a
m = ((k, a) -> b -> b) -> b -> [(k, a)] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
L.foldr (\(k
k,a
v) b
a -> a -> b -> b
f a
v b
a) b
d (Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k a
m)

-- | Strict foldl.

foldl' :: (Eq k) => (b -> a -> b) -> b -> Map k a -> b
foldl' :: forall k a b. Eq k => (a -> b -> a) -> a -> Map k b -> a
foldl' b -> a -> b
f b
d Map k a
m = (b -> (k, a) -> b) -> b -> [(k, a)] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
L.foldl' (\b
a (k
k,a
v) -> b -> a -> b
f b
a a
v) b
d (Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k a
m)

-- | Strict `foldrWithKey`.

foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey' :: forall b k a. (b -> k -> a -> b) -> b -> Map k a -> b
foldlWithKey' b -> k -> a -> b
f b
d (Map Set (k, a)
al) = (b -> (k, a) -> b) -> b -> Set (k, a) -> b
forall a b. (a -> b -> a) -> a -> Set b -> a
Set.foldl' (\b
b (k
k,a
v) -> b -> k -> a -> b
f b
b k
k a
v) b
d Set (k, a)
al

-- | Strict `foldrWithKey`.

foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey' :: forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
foldrWithKey' k -> a -> b -> b
f b
d (Map Set (k, a)
al) = ((k, a) -> b -> b) -> b -> Set (k, a) -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
Set.foldr' (\(k
k,a
v) -> k -> a -> b -> b
f k
k a
v) b
d Set (k, a)
al



-- | A universal combining function.

mergeWithKey :: Eq k => (k -> a -> b -> Maybe c) -> (Map k a -> Map k c) -> (Map k b -> Map k c) -> Map k a -> Map k b -> Map k c 
mergeWithKey :: forall k a b c.
Eq k =>
(k -> a -> b -> Maybe c)
-> (Map k a -> Map k c)
-> (Map k b -> Map k c)
-> Map k a
-> Map k b
-> Map k c
mergeWithKey k -> a -> b -> Maybe c
c Map k a -> Map k c
f Map k b -> Map k c
g Map k a
f1 Map k b
f2 = Set (k, c) -> Map k c
forall k v. Set (k, v) -> Map k v
Map (Set (k, c) -> Map k c) -> Set (k, c) -> Map k c
forall a b. (a -> b) -> a -> b
$ (k -> Maybe (k, c)) -> Set k -> Set (k, c)
forall a b. (a -> Maybe b) -> Set a -> Set b
Set.mapMaybe k -> Maybe (k, c)
helper ((Map k a -> Set k
forall k v. Map k v -> Set k
keys' Map k a
f1) Set k -> Set k -> Set k
forall a. Set a -> Set a -> Set a
||| (Map k b -> Set k
forall k v. Map k v -> Set k
keys' Map k b
f2))
    where
        newF1 :: Map k c
newF1 = Map k a -> Map k c
f Map k a
f1
        newF2 :: Map k c
newF2 = Map k b -> Map k c
g Map k b
f2
        helper :: k -> Maybe (k, c)
helper k
k
            | k
k k -> Map k a -> Bool
forall k a. Eq k => k -> Map k a -> Bool
`member` Map k a
f1 Bool -> Bool -> Bool
&& k
k k -> Map k b -> Bool
forall k a. Eq k => k -> Map k a -> Bool
`member` Map k b
f2 = (k, Maybe c) -> Maybe (k, c)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence (k
k, k -> a -> b -> Maybe c
c k
k (Map k a
f1 Map k a -> k -> a
forall k v. Eq k => Map k v -> k -> v
|!| k
k) (Map k b
f2 Map k b -> k -> b
forall k v. Eq k => Map k v -> k -> v
|!| k
k))
            | k
k k -> Map k a -> Bool
forall k a. Eq k => k -> Map k a -> Bool
`member` Map k a
f1 = (k, Maybe c) -> Maybe (k, c)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence (k
k, Map k c
newF1 Map k c -> k -> Maybe c
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
k)
            | k
k k -> Map k b -> Bool
forall k a. Eq k => k -> Map k a -> Bool
`member` Map k b
f2 = (k, Maybe c) -> Maybe (k, c)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence (k
k, Map k c
newF2 Map k c -> k -> Maybe c
forall k v. Eq k => Map k v -> k -> Maybe v
|?| k
k)


-- Conversion



-- | /O(n^2)/. Transform a function back into its underlying association list.

mapToList :: (Eq k) => Map k v -> AssociationList k v
mapToList :: forall k v. Eq k => Map k v -> AssociationList k v
mapToList (Map Set (k, v)
al) = ((k, v) -> (k, v) -> Bool) -> Set (k, v) -> [(k, v)]
forall a. (a -> a -> Bool) -> Set a -> [a]
nubSetBy (\(k, v)
x (k, v)
y -> ((k, v) -> k
forall a b. (a, b) -> a
fst (k, v)
x) k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== ((k, v) -> k
forall a b. (a, b) -> a
fst (k, v)
y)) Set (k, v)
al

-- | /O(n^2)/. Transform a function back into its underlying set of pairs.

mapToSet :: (Eq k) => Map k v -> Set (k,v)
mapToSet :: forall k v. Eq k => Map k v -> Set (k, v)
mapToSet Map k v
m = [(k, v)] -> Set (k, v)
forall a. [a] -> Set a
set ([(k, v)] -> Set (k, v)) -> [(k, v)] -> Set (k, v)
forall a b. (a -> b) -> a -> b
$ Map k v -> [(k, v)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k v
m


-- | /O(n^2)/. Return all values of the map. Beware that an Eq typeclass must be added.

elems :: (Eq k) => Map k a -> [a]
elems :: forall k a. Eq k => Map k a -> [a]
elems Map k a
m = (k, a) -> a
forall a b. (a, b) -> b
snd ((k, a) -> a) -> [(k, a)] -> [a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k a
m

-- | /O(n^2)/. Same as `elems` but returns a `Set`. Beware that an Eq typeclass must be added.

elems' :: (Eq k) => Map k a -> Set a
elems' :: forall k a. Eq k => Map k a -> Set a
elems' = [a] -> Set a
forall a. [a] -> Set a
set([a] -> Set a) -> (Map k a -> [a]) -> Map k a -> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Map k a -> [a]
forall k a. Eq k => Map k a -> [a]
elems

-- | /O(n^2)/. Alias of `elems'`.

values :: (Eq k) => Map k a -> Set a
values :: forall k a. Eq k => Map k a -> Set a
values = Map k a -> Set a
forall k a. Eq k => Map k a -> Set a
elems'

-- | /O(n^2)/. Alias of `elems'`.

image :: (Eq k) => Map k a -> Set a
image :: forall k a. Eq k => Map k a -> Set a
image = Map k a -> Set a
forall k a. Eq k => Map k a -> Set a
elems'

-- | /O(n^2)/. Return the keys of a map. Beware that an Eq typeclass must be added.

keys :: (Eq k) => Map k v -> [k]
keys :: forall k v. Eq k => Map k v -> [k]
keys Map k v
m = (k, v) -> k
forall a b. (a, b) -> a
fst ((k, v) -> k) -> [(k, v)] -> [k]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k v -> [(k, v)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k v
m

-- | /O(n)/. Same as `keys` but returns a `Set`. No Eq typeclass required.

keys' :: Map k v -> Set k
keys' :: forall k v. Map k v -> Set k
keys' (Map Set (k, v)
al) = (k, v) -> k
forall a b. (a, b) -> a
fst ((k, v) -> k) -> Set (k, v) -> Set k
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k, v)
al

-- | /O(n^2)/. Alias of `keys'`.

domain :: Map k a -> Set k
domain :: forall k v. Map k v -> Set k
domain = Map k a -> Set k
forall k v. Map k v -> Set k
keys'

-- | Alias of `mapToList` for backward compatibility. Beware that an Eq typeclass must be added.

assocs :: (Eq k) => Map k a -> [(k, a)]
assocs :: forall k v. Eq k => Map k v -> AssociationList k v
assocs = Map k a -> AssociationList k a
forall k v. Eq k => Map k v -> AssociationList k v
mapToList

-- | Alias of `keys'` for backward compatibility.

keysSet :: Map k a -> Set k 
keysSet :: forall k v. Map k v -> Set k
keysSet = Map k a -> Set k
forall k v. Map k v -> Set k
keys'

-- | /O(n^2)/. Return the set of values of a map.

elemsSet :: (Eq k) => Map k a -> Set a
elemsSet :: forall k a. Eq k => Map k a -> Set a
elemsSet = Map k a -> Set a
forall k a. Eq k => Map k a -> Set a
values

-- | /O(n^2)/. Alias of `mapToList` for backward compatibility. Beware that an Eq typeclass must be added.

toList :: (Eq k) => Map k a -> [(k, a)]
toList :: forall k v. Eq k => Map k v -> AssociationList k v
toList = Map k a -> AssociationList k a
forall k v. Eq k => Map k v -> AssociationList k v
mapToList

-- | Alias of `toList` for backward compatibility.

toAscList :: (Eq k) => Map k a -> [(k, a)]
toAscList :: forall k v. Eq k => Map k v -> AssociationList k v
toAscList = Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
toList

-- | Alias of `toList` for backward compatibility.

toDescList :: (Eq k) => Map k a -> [(k, a)]
toDescList :: forall k v. Eq k => Map k v -> AssociationList k v
toDescList = Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
toList



-- Filter



-- | /O(n)/. Filter all values that satisfy the predicate.

filter :: (a -> Bool) -> Map k a -> Map k a
filter :: forall a k. (a -> Bool) -> Map k a -> Map k a
filter a -> Bool
p (Map Set (k, a)
al) = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Bool) -> Set (k, a) -> Set (k, a)
forall a. (a -> Bool) -> Set a -> Set a
Set.filter (\(k
k,a
v) -> a -> Bool
p a
v) Set (k, a)
al
   
-- | /O(n)/. Filter all keys/values that satisfy the predicate.

filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a 
filterWithKey :: forall k a. (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey k -> a -> Bool
p (Map Set (k, a)
al) = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Bool) -> Set (k, a) -> Set (k, a)
forall a. (a -> Bool) -> Set a -> Set a
Set.filter ((k -> a -> Bool) -> (k, a) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> a -> Bool
p) Set (k, a)
al

-- | /O(n*m)/. Restrict a `Map` to only those keys found in a `Set`.

restrictKeys :: Eq k => Map k a -> Set k -> Map k a
restrictKeys :: forall k a. Eq k => Map k a -> Set k -> Map k a
restrictKeys Map k a
m Set k
s = (k -> a -> Bool) -> Map k a -> Map k a
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey (\k
k a
v -> k
k k -> Set k -> Bool
forall a. Eq a => a -> Set a -> Bool
`isIn` Set k
s) Map k a
m

-- | /O(n*m)/. Remove all keys in a `Set` from a `Map`.

withoutKeys :: Eq k => Map k a -> Set k -> Map k a 
withoutKeys :: forall k a. Eq k => Map k a -> Set k -> Map k a
withoutKeys Map k a
m Set k
s = (k -> a -> Bool) -> Map k a -> Map k a
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey (\k
k a
v -> Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ k
k k -> Set k -> Bool
forall a. Eq a => a -> Set a -> Bool
`isIn` Set k
s) Map k a
m

-- | /O(n)/. Partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate.

partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a)
partition :: forall a k. (a -> Bool) -> Map k a -> (Map k a, Map k a)
partition a -> Bool
p Map k a
m = ((a -> Bool) -> Map k a -> Map k a
forall a k. (a -> Bool) -> Map k a -> Map k a
filter a -> Bool
p Map k a
m, (a -> Bool) -> Map k a -> Map k a
forall a k. (a -> Bool) -> Map k a -> Map k a
filter (Bool -> Bool
not(Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.a -> Bool
p) Map k a
m)

-- | /O(n)/. Partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate. 

partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
partitionWithKey :: forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
partitionWithKey k -> a -> Bool
p Map k a
m = ((k -> a -> Bool) -> Map k a -> Map k a
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey k -> a -> Bool
p Map k a
m, (k -> a -> Bool) -> Map k a -> Map k a
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
filterWithKey (((Bool -> Bool) -> (a -> Bool) -> a -> Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Bool -> Bool
not)((a -> Bool) -> a -> Bool) -> (k -> a -> Bool) -> k -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
.k -> a -> Bool
p) Map k a
m)

-- | /O(n)/. Map values and collect the Just results.

mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b
mapMaybe :: forall a b k. (a -> Maybe b) -> Map k a -> Map k b
mapMaybe a -> Maybe b
f Map k a
m = (k -> a -> Maybe b) -> Map k a -> Map k b
forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
mapMaybeWithKey ((a -> Maybe b) -> k -> a -> Maybe b
forall a b. a -> b -> a
const a -> Maybe b
f) Map k a
m

-- | /O(n)/. Map keys/values and collect the Just results.

mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b 
mapMaybeWithKey :: forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
mapMaybeWithKey k -> a -> Maybe b
f (Map Set (k, a)
al) = Set (k, b) -> Map k b
forall k v. Set (k, v) -> Map k v
Map (Set (k, b) -> Map k b) -> Set (k, b) -> Map k b
forall a b. (a -> b) -> a -> b
$ ((k, a) -> Maybe (k, b)) -> Set (k, a) -> Set (k, b)
forall a b. (a -> Maybe b) -> Set a -> Set b
Set.mapMaybe (k, a) -> Maybe (k, b)
customF Set (k, a)
al
    where
        customF :: (k, a) -> Maybe (k, b)
customF (k
k,a
v) = (k, Maybe b) -> Maybe (k, b)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence (k
k, k -> a -> Maybe b
f k
k a
v)

-- | /O(n)/. Map values and separate the Left and Right results.

mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c) 
mapEither :: forall a b c k. (a -> Either b c) -> Map k a -> (Map k b, Map k c)
mapEither a -> Either b c
f Map k a
m = (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
forall k a b c.
(k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
mapEitherWithKey ((a -> Either b c) -> k -> a -> Either b c
forall a b. a -> b -> a
const a -> Either b c
f) Map k a
m

-- | /O(n)/. Map keys/values and separate the Left and Right results.

mapEitherWithKey :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c) 
mapEitherWithKey :: forall k a b c.
(k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
mapEitherWithKey k -> a -> Either b c
f (Map Set (k, a)
al) = (Set (k, b) -> Map k b
forall k v. Set (k, v) -> Map k v
Map Set (k, b)
ls, Set (k, c) -> Map k c
forall k v. Set (k, v) -> Map k v
Map Set (k, c)
rs)
    where
        (Set (k, b)
ls,Set (k, c)
rs) = ((k, a) -> Either (k, b) (k, c))
-> Set (k, a) -> (Set (k, b), Set (k, c))
forall a b c. (a -> Either b c) -> Set a -> (Set b, Set c)
Set.mapEither (k, a) -> Either (k, b) (k, c)
customF Set (k, a)
al
        customF :: (k, a) -> Either (k, b) (k, c)
customF (k
k,a
v)
            | Either b c -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Either b c
result = (k, b) -> Either (k, b) (k, c)
forall a b. a -> Either a b
Left (k
k,b
l)
            | Bool
otherwise = (k, c) -> Either (k, b) (k, c)
forall a b. b -> Either a b
Right (k
k,c
r)
            where
                result :: Either b c
result = k -> a -> Either b c
f k
k a
v
                Left b
l = Either b c
result
                Right c
r = Either b c
result



-- Submap



-- | /O(max(m^2,n^2))/. This function is defined as @(isSubmapOf = isSubmapOfBy (==))@.

isSubmapOf :: (Eq k, Eq a) => Map k a -> Map k a -> Bool
isSubmapOf :: forall k v. (Eq k, Eq v) => Map k v -> Map k v -> Bool
isSubmapOf = (a -> a -> Bool) -> Map k a -> Map k a -> Bool
forall k a b.
Eq k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
isSubmapOfBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)

-- | /O(max(m^2,n^2))/. Returns True if the keys of the first map is included in the keys of the second and the predicate evaluation at their value is True.

isSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
isSubmapOfBy :: forall k a b.
Eq k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
isSubmapOfBy a -> b -> Bool
p Map k a
m1 Map k b
m2 = (Map k a -> Set k
forall k v. Map k v -> Set k
keys' Map k a
m1) Set k -> Set k -> Bool
forall a. Eq a => Set a -> Set a -> Bool
`isIncludedIn` (Map k b -> Set k
forall k v. Map k v -> Set k
keys' Map k b
m2) Bool -> Bool -> Bool
&& (Set Bool -> Bool
Set.and (Set Bool -> Bool) -> Set Bool -> Bool
forall a b. (a -> b) -> a -> b
$ k -> Bool
test (k -> Bool) -> Set k -> Set Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k a -> Set k
forall k v. Map k v -> Set k
keys' Map k a
m1)
    where
        test :: k -> Bool
test k
k = a -> b -> Bool
p (Map k a
m1 Map k a -> k -> a
forall k v. Eq k => Map k v -> k -> v
|!| k
k) (Map k b
m2 Map k b -> k -> b
forall k v. Eq k => Map k v -> k -> v
|!| k
k)

-- | /O(max(m^2,n^2))/. This function is defined as @(isProperSubmapOf = isProperSubmapOfBy (==))@.

isProperSubmapOf :: (Eq k, Eq a) => Map k a -> Map k a -> Bool
isProperSubmapOf :: forall k v. (Eq k, Eq v) => Map k v -> Map k v -> Bool
isProperSubmapOf = (a -> a -> Bool) -> Map k a -> Map k a -> Bool
forall k a b.
Eq k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
isProperSubmapOfBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)

-- | /O(max(m^2,n^2))/. Returns True if the keys of the first map is strictly included in the keys of the second and the predicate evaluation at their value is True.

isProperSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
isProperSubmapOfBy :: forall k a b.
Eq k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
isProperSubmapOfBy a -> b -> Bool
p Map k a
m1 Map k b
m2 = (Map k a -> Set k
forall k v. Map k v -> Set k
keys' Map k a
m1) Set k -> Set k -> Bool
forall a. Eq a => Set a -> Set a -> Bool
`Set.isProperSubsetOf` (Map k b -> Set k
forall k v. Map k v -> Set k
keys' Map k b
m2) Bool -> Bool -> Bool
&& (Set Bool -> Bool
Set.and (Set Bool -> Bool) -> Set Bool -> Bool
forall a b. (a -> b) -> a -> b
$ k -> Bool
test (k -> Bool) -> Set k -> Set Bool
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map k a -> Set k
forall k v. Map k v -> Set k
keys' Map k a
m1)
    where
        test :: k -> Bool
test k
k = a -> b -> Bool
p (Map k a
m1 Map k a -> k -> a
forall k v. Eq k => Map k v -> k -> v
|!| k
k) (Map k b
m2 Map k b -> k -> b
forall k v. Eq k => Map k v -> k -> v
|!| k
k)



-- Indexed



-- | /O(n^2)/. Lookup the index of a key, which is its zero-based index in the sequence. The index is a number from 0 up to, but not including, the size of the map.

lookupIndex :: Eq k => k -> Map k a -> Maybe Int
lookupIndex :: forall k a. Eq k => k -> Map k a -> Maybe Int
lookupIndex k
k Map k a
m = k -> [k] -> Maybe Int
forall a. Eq a => a -> [a] -> Maybe Int
L.elemIndex k
k (Map k a -> [k]
forall k v. Eq k => Map k v -> [k]
keys Map k a
m)

-- | /O(n^2)/. Return the index of a key, which is its zero-based index in the sequence. The index is a number from 0 up to, but not including, the size of the map. Calls error when the key is not a member of the map.

findIndex :: Eq k => k -> Map k a -> Int
findIndex :: forall k a. Eq k => k -> Map k a -> Int
findIndex k
k Map k a
m
    | Maybe Int -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe Int
index = String -> Int
forall a. HasCallStack => String -> a
error String
"WeakSet.findIndex: element is not in the set"
    | Bool
otherwise = Int
i
    where
        index :: Maybe Int
index = k -> Map k a -> Maybe Int
forall k a. Eq k => k -> Map k a -> Maybe Int
lookupIndex k
k Map k a
m
        Just Int
i = Maybe Int
index
        
-- | /O(n^2)/. Retrieve an element by its index, i.e. by its zero-based index in the sequence. If the index is out of range (less than zero, greater or equal to size of the map), error is called.

elemAt :: Eq k => Int -> Map k a -> (k, a)
elemAt :: forall k a. Eq k => Int -> Map k a -> (k, a)
elemAt Int
i Map k a
m
    | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 Bool -> Bool -> Bool
|| Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= ([(k, a)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [(k, a)]
xs) = String -> (k, a)
forall a. HasCallStack => String -> a
error String
"WeakSet.elemAt: index out of range"
    | Bool
otherwise = [(k, a)] -> Int -> (k, a)
forall a. [a] -> Int -> a
(L.!!) [(k, a)]
xs Int
i
    where
        xs :: [(k, a)]
xs = Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k a
m

-- | Helper function for updateAt.

updateListAt :: Int -> (a -> Maybe a) -> [a] -> [a]
updateListAt :: forall a. Int -> (a -> Maybe a) -> [a] -> [a]
updateListAt Int
_ a -> Maybe a
_ [] = []
updateListAt Int
0 a -> Maybe a
f (a
x : [a]
xs)
    | Maybe a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
Foldable.null Maybe a
result = [a]
xs
    | Bool
otherwise = a
r a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs
    where
        result :: Maybe a
result = a -> Maybe a
f a
x
        Just a
r = Maybe a
result
updateListAt Int
n a -> Maybe a
f (a
x : [a]
xs) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Int -> (a -> Maybe a) -> [a] -> [a]
forall a. Int -> (a -> Maybe a) -> [a] -> [a]
updateListAt (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) a -> Maybe a
f [a]
xs

-- | /O(n^2)/. Update the element at index. Calls error when an invalid index is used.

updateAt :: Eq k => (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
updateAt :: forall k a.
Eq k =>
(k -> a -> Maybe a) -> Int -> Map k a -> Map k a
updateAt k -> a -> Maybe a
f Int
i Map k a
m = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ [(k, a)] -> Set (k, a)
forall a. [a] -> Set a
set ([(k, a)] -> Set (k, a)) -> [(k, a)] -> Set (k, a)
forall a b. (a -> b) -> a -> b
$ Int -> ((k, a) -> Maybe (k, a)) -> [(k, a)] -> [(k, a)]
forall a. Int -> (a -> Maybe a) -> [a] -> [a]
updateListAt Int
i (\(k
k,a
v) -> (k, Maybe a) -> Maybe (k, a)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
sequence (k
k, k -> a -> Maybe a
f k
k a
v)) (Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k a
m)

-- | /O(n^2)/. Delete the element at index, i.e. by its zero-based index in the sequence. If the index is out of range (less than zero, greater or equal to size of the map), error is called.

deleteAt :: (Eq k) => Int -> Map k a -> Map k a
deleteAt :: forall k a. Eq k => Int -> Map k a -> Map k a
deleteAt Int
i Map k a
m = Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ [(k, a)] -> Set (k, a)
forall a. [a] -> Set a
set ([(k, a)] -> Set (k, a)) -> [(k, a)] -> Set (k, a)
forall a b. (a -> b) -> a -> b
$ Int -> [(k, a)] -> [(k, a)]
forall {t} {a}. (Eq t, Num t) => t -> [a] -> [a]
helper Int
i [(k, a)]
al
    where
        al :: [(k, a)]
al = Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k a
m
        helper :: t -> [a] -> [a]
helper t
_ [] = []
        helper t
0 (a
x:[a]
xs) = [a]
xs
        helper t
n (a
x:[a]
xs) = t -> [a] -> [a]
helper (t
nt -> t -> t
forall a. Num a => a -> a -> a
-t
1) [a]
xs

-- | /O(n^2)/. Take a given number of pairs to create a new map.

take :: (Eq k) => Int -> Map k a -> Map k a
take :: forall k a. Eq k => Int -> Map k a -> Map k a
take Int
n Map k a
m = (Map k a, Map k a) -> Map k a
forall a b. (a, b) -> a
fst ((Map k a, Map k a) -> Map k a) -> (Map k a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$ Int -> Map k a -> (Map k a, Map k a)
forall k a. Eq k => Int -> Map k a -> (Map k a, Map k a)
splitAt Int
n Map k a
m

-- | /O(n^2)/. Drop a given number of pairs to create a new map.

drop :: (Eq k) => Int -> Map k a -> Map k a
drop :: forall k a. Eq k => Int -> Map k a -> Map k a
drop Int
n Map k a
m = (Map k a, Map k a) -> Map k a
forall a b. (a, b) -> b
snd ((Map k a, Map k a) -> Map k a) -> (Map k a, Map k a) -> Map k a
forall a b. (a -> b) -> a -> b
$ Int -> Map k a -> (Map k a, Map k a)
forall k a. Eq k => Int -> Map k a -> (Map k a, Map k a)
splitAt Int
n Map k a
m

-- | /O(n^2)/. Split a map at a particular index.

splitAt :: (Eq k) => Int -> Map k a -> (Map k a, Map k a)
splitAt :: forall k a. Eq k => Int -> Map k a -> (Map k a, Map k a)
splitAt Int
n Map k a
m = (Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ [(k, a)] -> Set (k, a)
forall a. [a] -> Set a
set [(k, a)]
l, Set (k, a) -> Map k a
forall k v. Set (k, v) -> Map k v
Map (Set (k, a) -> Map k a) -> Set (k, a) -> Map k a
forall a b. (a -> b) -> a -> b
$ [(k, a)] -> Set (k, a)
forall a. [a] -> Set a
set [(k, a)]
r)
    where
        al :: [(k, a)]
al = Map k a -> [(k, a)]
forall k v. Eq k => Map k v -> AssociationList k v
mapToList Map k a
m
        ([(k, a)]
l,[(k, a)]
r) = Int -> [(k, a)] -> ([(k, a)], [(k, a)])
forall a. Int -> [a] -> ([a], [a])
L.splitAt Int
n [(k, a)]
al


-- Others




-- | /O(n)/. Return the identity function associated to a `Set`.

idFromSet :: Set a -> Map a a
idFromSet :: forall a. Set a -> Map a a
idFromSet Set a
set = Set (a, a) -> Map a a
forall k v. Set (k, v) -> Map k v
Map (Set (a, a) -> Map a a) -> Set (a, a) -> Map a a
forall a b. (a -> b) -> a -> b
$ (\a
x -> (a
x,a
x)) (a -> (a, a)) -> Set a -> Set (a, a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set a
set


-- | /O(n)/. Memorize a Haskell function on a given finite domain. Alias of `fromSet`.

memorizeFunction :: (k -> v) -> Set k -> Map k v
memorizeFunction :: forall k a. (k -> a) -> Set k -> Map k a
memorizeFunction k -> v
f Set k
xs = Set (k, v) -> Map k v
forall k v. Set (k, v) -> Map k v
Map (Set (k, v) -> Map k v) -> Set (k, v) -> Map k v
forall a b. (a -> b) -> a -> b
$ (\k
k -> (k
k, k -> v
f k
k)) (k -> (k, v)) -> Set k -> Set (k, v)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set k
xs

-- | /O(n^2)/. Try to construct an inverse map.

inverse :: (Eq k, Eq v) => Map k v -> Maybe (Map v k)
inverse :: forall k v. (Eq k, Eq v) => Map k v -> Maybe (Map v k)
inverse m :: Map k v
m@(Map Set (k, v)
al)
    | (Set v -> Int
forall a. Eq a => Set a -> Int
cardinal(Set v -> Int) -> (Map k v -> Set v) -> Map k v -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Map k v -> Set v
forall k a. Eq k => Map k a -> Set a
image (Map k v -> Int) -> Map k v -> Int
forall a b. (a -> b) -> a -> b
$ Map k v
m) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== (Set k -> Int
forall a. Eq a => Set a -> Int
cardinal(Set k -> Int) -> (Map k v -> Set k) -> Map k v -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
.Map k v -> Set k
forall k v. Map k v -> Set k
domain (Map k v -> Int) -> Map k v -> Int
forall a b. (a -> b) -> a -> b
$ Map k v
m) = Map v k -> Maybe (Map v k)
forall a. a -> Maybe a
Just (Map v k -> Maybe (Map v k)) -> Map v k -> Maybe (Map v k)
forall a b. (a -> b) -> a -> b
$ Set (v, k) -> Map v k
forall k v. Set (k, v) -> Map k v
Map (Set (v, k) -> Map v k) -> Set (v, k) -> Map v k
forall a b. (a -> b) -> a -> b
$ (\(k
k,v
v) -> (v
v,k
k)) ((k, v) -> (v, k)) -> Set (k, v) -> Set (v, k)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k, v)
al
    | Bool
otherwise = Maybe (Map v k)
forall a. Maybe a
Nothing
    
-- | /O(n)/. Return a pseudo inverse /g/ of a 'Map' /f/ such that @f |.| g |.| f == f@.

pseudoInverse :: Map k v -> Map v k
pseudoInverse :: forall k v. Map k v -> Map v k
pseudoInverse (Map Set (k, v)
al) = Set (v, k) -> Map v k
forall k v. Set (k, v) -> Map k v
Map (Set (v, k) -> Map v k) -> Set (v, k) -> Map v k
forall a b. (a -> b) -> a -> b
$ (\(k
k,v
v) -> (v
v,k
k)) ((k, v) -> (v, k)) -> Set (k, v) -> Set (v, k)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set (k, v)
al

-- | Return all Functions from a domain to a codomain.

enumerateMaps :: (Eq a, Eq b) =>
                    Set a -- ^ Domain.

                 -> Set b -- ^ Codomain.

                 -> Set (Map a b) -- ^ All maps from domain to codomain.

enumerateMaps :: forall a b. (Eq a, Eq b) => Set a -> Set b -> Set (Map a b)
enumerateMaps Set a
dom Set b
codom = [Map a b] -> Set (Map a b)
forall a. [a] -> Set a
set ([Map a b] -> Set (Map a b)) -> [Map a b] -> Set (Map a b)
forall a b. (a -> b) -> a -> b
$ AssociationList a b -> Map a b
forall k v. AssociationList k v -> Map k v
weakMap (AssociationList a b -> Map a b)
-> ([b] -> AssociationList a b) -> [b] -> Map a b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> [a] -> [b] -> AssociationList a b
forall a b. [a] -> [b] -> [(a, b)]
zip (Set a -> [a]
forall a. Eq a => Set a -> [a]
setToList Set a
dom) ([b] -> Map a b) -> [[b]] -> [Map a b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Set [b] -> [[b]]
forall a. Eq a => Set a -> [a]
setToList (Set b
codom Set b -> Int -> Set [b]
forall a. Eq a => Set a -> Int -> Set [a]
|^| (Set a -> Int
forall a. Eq a => Set a -> Int
cardinal Set a
dom))