-- |
--   Module      :  Data.Edison.Assoc.AssocList
--   Copyright   :  Copyright (c) 1998, 2008 Chris Okasaki
--   License     :  MIT; see COPYRIGHT file for terms and conditions
--
--   Maintainer  :  robdockins AT fastmail DOT fm
--   Stability   :  stable
--   Portability :  GHC, Hugs (MPTC and FD)
--
--   This module implements finite maps as simple association lists.
--
--   Duplicates are removed conceptually, but not physically.  The first
--   occurrence of a given key is the one that is considered to be in the map.
--
--   The list type is mildly customized to prevent boxing the pairs.

module Data.Edison.Assoc.AssocList (
    -- * Type of simple association lists
    FM, -- instance of Assoc(X), FiniteMap(X)
        -- also instance of Functor

    -- * AssocX operations
    empty,singleton,fromSeq,insert,insertSeq,union,unionSeq,delete,deleteAll,
    deleteSeq,null,size,member,count,lookup,lookupM,lookupAll,
    lookupAndDelete,lookupAndDeleteM,lookupAndDeleteAll,
    lookupWithDefault,adjust,adjustAll,adjustOrInsert,adjustAllOrInsert,
    adjustOrDelete,adjustOrDeleteAll,strict,strictWith,
    map,fold,fold',fold1,fold1',filter,partition,elements,structuralInvariant,

    -- * OrdAssocX operations
    minView, minElem, deleteMin, unsafeInsertMin, maxView, maxElem, deleteMax,
    unsafeInsertMax, foldr, foldr', foldl, foldl', foldr1, foldr1',
    foldl1, foldl1', unsafeFromOrdSeq, unsafeAppend,
    filterLT, filterLE, filterGT, filterGE,
    partitionLT_GE, partitionLE_GT, partitionLT_GT,

    -- * Assoc operations
    toSeq,keys,mapWithKey,foldWithKey,foldWithKey',filterWithKey,partitionWithKey,

    -- * OrdAssoc operations
    minViewWithKey, minElemWithKey, maxViewWithKey, maxElemWithKey,
    foldrWithKey, foldrWithKey', foldlWithKey, foldlWithKey', toOrdSeq,

    -- * FiniteMapX operations
    fromSeqWith,fromSeqWithKey,insertWith,insertWithKey,insertSeqWith,
    insertSeqWithKey,unionl,unionr,unionWith,unionSeqWith,intersectionWith,
    difference,properSubset,subset,properSubmapBy,submapBy,sameMapBy,
    properSubmap,submap,sameMap,

    -- * FiniteMap operations
    unionWithKey,unionSeqWithKey,intersectionWithKey,

    -- * Documentation
    moduleName
) where

import Prelude hiding (null,map,lookup,foldr,foldl,foldr1,foldl1,foldl',filter)
import qualified Prelude
import Data.Monoid
import Data.Semigroup as SG
import qualified Control.Monad.Fail as Fail
import qualified Data.Edison.Assoc as A
import Data.Edison.Prelude ( runFail_ )
import qualified Data.Edison.Seq as S
import qualified Data.Edison.Seq.BinaryRandList as RL
import Data.Edison.Assoc.Defaults
import Test.QuickCheck (Arbitrary(..), CoArbitrary(..), variant)

-- signatures for exported functions
moduleName    :: String
empty         :: Eq k => FM k a
singleton     :: Eq k => k -> a -> FM k a
fromSeq       :: (Eq k,S.Sequence seq) => seq (k,a) -> FM k a
insert        :: Eq k => k -> a -> FM k a -> FM k a
insertSeq     :: (Eq k,S.Sequence seq) => seq (k,a) -> FM k a -> FM k a
union         :: Eq k => FM k a -> FM k a -> FM k a
unionSeq      :: (Eq k,S.Sequence seq) => seq (FM k a) -> FM k a
delete        :: Eq k => k -> FM k a -> FM k a
deleteAll     :: Eq k => k -> FM k a -> FM k a
deleteSeq     :: (Eq k,S.Sequence seq) => seq k -> FM k a -> FM k a
null          :: Eq k => FM k a -> Bool
size          :: Eq k => FM k a -> Int
member        :: Eq k => k -> FM k a -> Bool
count         :: Eq k => k -> FM k a -> Int
lookup        :: Eq k => k -> FM k a -> a
lookupM       :: (Eq k, Fail.MonadFail rm) => k -> FM k a -> rm a
lookupAll     :: (Eq k,S.Sequence seq) => k -> FM k a -> seq a
lookupAndDelete    :: Eq k => k -> FM k a -> (a,FM k a)
lookupAndDeleteM   :: (Eq k, Fail.MonadFail rm)   => k -> FM k a -> rm (a,FM k a)
lookupAndDeleteAll :: (Eq k,S.Sequence seq) => k -> FM k a -> (seq a,FM k a)
lookupWithDefault  :: Eq k => a -> k -> FM k a -> a
adjust             :: Eq k => (a -> a) -> k -> FM k a -> FM k a
adjustAll          :: Eq k => (a -> a) -> k -> FM k a -> FM k a
adjustOrInsert     :: Eq k => (a -> a) -> a -> k -> FM k a -> FM k a
adjustAllOrInsert  :: Eq k => (a -> a) -> a -> k -> FM k a -> FM k a
adjustOrDelete     :: Eq k => (a -> Maybe a) -> k -> FM k a -> FM k a
adjustOrDeleteAll  :: Eq k => (a -> Maybe a) -> k -> FM k a -> FM k a
strict             :: FM k a -> FM k a
strictWith         :: (a -> b) -> FM k a -> FM k a
map           :: Eq k => (a -> b) -> FM k a -> FM k b
fold          :: Eq k => (a -> b -> b) -> b -> FM k a -> b
fold1         :: Eq k => (a -> a -> a) -> FM k a -> a
fold'         :: Eq k => (a -> b -> b) -> b -> FM k a -> b
fold1'        :: Eq k => (a -> a -> a) -> FM k a -> a
filter        :: Eq k => (a -> Bool) -> FM k a -> FM k a
partition     :: Eq k => (a -> Bool) -> FM k a -> (FM k a, FM k a)
elements      :: (Eq k,S.Sequence seq) => FM k a -> seq a

fromSeqWith      :: (Eq k,S.Sequence seq) =>
                        (a -> a -> a) -> seq (k,a) -> FM k a
fromSeqWithKey   :: (Eq k,S.Sequence seq) => (k -> a -> a -> a) -> seq (k,a) -> FM k a
insertWith       :: Eq k => (a -> a -> a) -> k -> a -> FM k a -> FM k a
insertWithKey    :: Eq k => (k -> a -> a -> a) -> k -> a -> FM k a -> FM k a
insertSeqWith    :: (Eq k,S.Sequence seq) =>
                        (a -> a -> a) -> seq (k,a) -> FM k a -> FM k a
insertSeqWithKey :: (Eq k,S.Sequence seq) =>
                        (k -> a -> a -> a) -> seq (k,a) -> FM k a -> FM k a
unionl           :: Eq k => FM k a -> FM k a -> FM k a
unionr           :: Eq k => FM k a -> FM k a -> FM k a
unionWith        :: Eq k => (a -> a -> a) -> FM k a -> FM k a -> FM k a
unionSeqWith     :: (Eq k,S.Sequence seq) =>
                        (a -> a -> a) -> seq (FM k a) -> FM k a
intersectionWith :: Eq k => (a -> b -> c) -> FM k a -> FM k b -> FM k c
difference       :: Eq k => FM k a -> FM k b -> FM k a
properSubset     :: Eq k => FM k a -> FM k b -> Bool
subset           :: Eq k => FM k a -> FM k b -> Bool
properSubmapBy   :: Eq k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
submapBy         :: Eq k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
sameMapBy        :: Eq k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
properSubmap     :: (Eq k, Eq a) => FM k a -> FM k a -> Bool
submap           :: (Eq k, Eq a) => FM k a -> FM k a -> Bool
sameMap          :: (Eq k, Eq a) => FM k a -> FM k a -> Bool

toSeq            :: (Eq k,S.Sequence seq) => FM k a -> seq (k,a)
keys             :: (Eq k,S.Sequence seq) => FM k a -> seq k
mapWithKey       :: Eq k => (k -> a -> b) -> FM k a -> FM k b
foldWithKey      :: Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldWithKey'     :: Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
filterWithKey    :: Eq k => (k -> a -> Bool) -> FM k a -> FM k a
partitionWithKey :: Eq k => (k -> a -> Bool) -> FM k a -> (FM k a, FM k a)

unionWithKey     :: Eq k => (k -> a -> a -> a) -> FM k a -> FM k a -> FM k a
unionSeqWithKey  :: (Eq k,S.Sequence seq) =>
                        (k -> a -> a -> a) -> seq (FM k a) -> FM k a
intersectionWithKey :: Eq k => (k -> a -> b -> c) -> FM k a -> FM k b -> FM k c

minView          :: (Ord k, Fail.MonadFail m) => FM k a -> m (a,FM k a)
minElem          :: Ord k => FM k a -> a
deleteMin        :: Ord k => FM k a -> FM k a
unsafeInsertMin  :: Ord k => k -> a -> FM k a -> FM k a
maxView          :: (Ord k, Fail.MonadFail m) => FM k a -> m (a,FM k a)
maxElem          :: Ord k => FM k a -> a
deleteMax        :: Ord k => FM k a -> FM k a
unsafeInsertMax  :: Ord k => k -> a -> FM k a -> FM k a
foldr            :: Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr1           :: Ord k => (a -> a -> a) -> FM k a -> a
foldl            :: Ord k => (b -> a -> b) -> b -> FM k a -> b
foldl1           :: Ord k => (a -> a -> a) -> FM k a -> a
foldr'           :: Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr1'          :: Ord k => (a -> a -> a) -> FM k a -> a
foldl'           :: Ord k => (b -> a -> b) -> b -> FM k a -> b
foldl1'          :: Ord k => (a -> a -> a) -> FM k a -> a
unsafeFromOrdSeq :: (Ord k,S.Sequence seq) => seq (k,a) -> FM k a
unsafeAppend     :: Ord k => FM k a -> FM k a -> FM k a
filterLT         :: Ord k => k -> FM k a -> FM k a
filterLE         :: Ord k => k -> FM k a -> FM k a
filterGT         :: Ord k => k -> FM k a -> FM k a
filterGE         :: Ord k => k -> FM k a -> FM k a
partitionLT_GE   :: Ord k => k -> FM k a -> (FM k a,FM k a)
partitionLE_GT   :: Ord k => k -> FM k a -> (FM k a,FM k a)
partitionLT_GT   :: Ord k => k -> FM k a -> (FM k a,FM k a)

minViewWithKey    :: (Ord k, Fail.MonadFail m) => FM k a -> m ((k, a), FM k a)
minElemWithKey    :: Ord k => FM k a -> (k,a)
maxViewWithKey    :: (Ord k, Fail.MonadFail m) => FM k a -> m ((k, a), FM k a)
maxElemWithKey    :: Ord k => FM k a -> (k,a)
foldrWithKey      :: Ord k => (k -> a -> b -> b) -> b -> FM k a -> b
foldlWithKey      :: Ord k => (b -> k -> a -> b) -> b -> FM k a -> b
foldrWithKey'     :: Ord k => (k -> a -> b -> b) -> b -> FM k a -> b
foldlWithKey'     :: Ord k => (b -> k -> a -> b) -> b -> FM k a -> b
toOrdSeq          :: (Ord k,S.Sequence seq) => FM k a -> seq (k,a)


moduleName :: String
moduleName = String
"Data.Edison.Assoc.AssocList"


data FM k a = E | I k a (FM k a)

-- no invariants
structuralInvariant :: Eq k => FM k a -> Bool
structuralInvariant :: forall k a. Eq k => FM k a -> Bool
structuralInvariant = Bool -> FM k a -> Bool
forall a b. a -> b -> a
const Bool
True

---------------------------------------
-- some unexported utility functions

-- uncurried insert.
uinsert :: (t, t1) -> FM t t1 -> FM t t1
uinsert :: forall t t1. (t, t1) -> FM t t1 -> FM t t1
uinsert (t
k,t1
x) = t -> t1 -> FM t t1 -> FM t t1
forall k a. k -> a -> FM k a -> FM k a
I t
k t1
x


-- left biased merge.
mergeFM :: (Ord t) => FM t t1 -> FM t t1 -> FM t t1
mergeFM :: forall t t1. Ord t => FM t t1 -> FM t t1 -> FM t t1
mergeFM FM t t1
E FM t t1
m = FM t t1
m
mergeFM FM t t1
m FM t t1
E = FM t t1
m
mergeFM o1 :: FM t t1
o1@(I t
k1 t1
a1 FM t t1
m1) o2 :: FM t t1
o2@(I t
k2 t1
a2 FM t t1
m2) =
  case t -> t -> Ordering
forall a. Ord a => a -> a -> Ordering
compare t
k1 t
k2 of
      Ordering
LT -> t -> t1 -> FM t t1 -> FM t t1
forall k a. k -> a -> FM k a -> FM k a
I t
k1 t1
a1 (FM t t1 -> FM t t1 -> FM t t1
forall t t1. Ord t => FM t t1 -> FM t t1 -> FM t t1
mergeFM FM t t1
m1 FM t t1
o2)
      Ordering
GT -> t -> t1 -> FM t t1 -> FM t t1
forall k a. k -> a -> FM k a -> FM k a
I t
k2 t1
a2 (FM t t1 -> FM t t1 -> FM t t1
forall t t1. Ord t => FM t t1 -> FM t t1 -> FM t t1
mergeFM FM t t1
o1 FM t t1
m2)
      Ordering
EQ -> t -> t1 -> FM t t1 -> FM t t1
forall k a. k -> a -> FM k a -> FM k a
I t
k1 t1
a1 (FM t t1 -> FM t t1 -> FM t t1
forall t t1. Ord t => FM t t1 -> FM t t1 -> FM t t1
mergeFM FM t t1
m1 FM t t1
m2)

toRandList :: FM t t1 -> RL.Seq (FM t t1)
toRandList :: forall t t1. FM t t1 -> Seq (FM t t1)
toRandList FM t t1
E = Seq (FM t t1)
forall a. Seq a
RL.empty
toRandList (I t
k t1
a FM t t1
m) = FM t t1 -> Seq (FM t t1) -> Seq (FM t t1)
forall a. a -> Seq a -> Seq a
RL.lcons (t -> t1 -> FM t t1 -> FM t t1
forall k a. k -> a -> FM k a -> FM k a
I t
k t1
a FM t t1
forall k a. FM k a
E) (FM t t1 -> Seq (FM t t1)
forall t t1. FM t t1 -> Seq (FM t t1)
toRandList FM t t1
m)

mergeSortFM :: (Ord t) => FM t t1 -> FM t t1
mergeSortFM :: forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM FM t t1
m = (FM t t1 -> FM t t1 -> FM t t1)
-> FM t t1 -> Seq (FM t t1) -> FM t t1
forall a. (a -> a -> a) -> a -> Seq a -> a
RL.reducer FM t t1 -> FM t t1 -> FM t t1
forall t t1. Ord t => FM t t1 -> FM t t1 -> FM t t1
mergeFM FM t t1
forall k a. FM k a
E (FM t t1 -> Seq (FM t t1)
forall t t1. FM t t1 -> Seq (FM t t1)
toRandList FM t t1
m)

foldrFM :: Eq k => (a -> b -> b) -> b -> FM k a -> b
foldrFM :: forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
foldrFM a -> b -> b
_ b
z FM k a
E = b
z
foldrFM a -> b -> b
f b
z (I k
k a
a FM k a
m) = a -> b -> b
f a
a ((a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
foldrFM a -> b -> b
f b
z (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))

foldr1FM :: Eq k => (a -> a -> a) -> FM k a -> a
foldr1FM :: forall k a. Eq k => (a -> a -> a) -> FM k a -> a
foldr1FM a -> a -> a
_ (I k
_ a
a FM k a
E) = a
a
foldr1FM a -> a -> a
f (I k
k a
a FM k a
m) = a -> a -> a
f a
a ((a -> a -> a) -> FM k a -> a
forall k a. Eq k => (a -> a -> a) -> FM k a -> a
foldr1FM a -> a -> a
f (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))
foldr1FM a -> a -> a
_ FM k a
_ = String -> a
forall a. HasCallStack => String -> a
error String
"invalid call to foldr1FM on empty map"

foldrFM' :: Eq k => (a -> b -> b) -> b -> FM k a -> b
foldrFM' :: forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
foldrFM' a -> b -> b
_ b
z FM k a
E = b
z
foldrFM' a -> b -> b
f b
z (I k
k a
a FM k a
m) = a -> b -> b
f a
a (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! ((a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
foldrFM' a -> b -> b
f b
z (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))

foldr1FM' :: Eq k => (a -> a -> a) -> FM k a -> a
foldr1FM' :: forall k a. Eq k => (a -> a -> a) -> FM k a -> a
foldr1FM' a -> a -> a
_ (I k
_ a
a FM k a
E) = a
a
foldr1FM' a -> a -> a
f (I k
k a
a FM k a
m) = a -> a -> a
f a
a (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! ((a -> a -> a) -> FM k a -> a
forall k a. Eq k => (a -> a -> a) -> FM k a -> a
foldr1FM' a -> a -> a
f (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))
foldr1FM' a -> a -> a
_ FM k a
_ = String -> a
forall a. HasCallStack => String -> a
error String
"invalid call to foldr1FM' on empty map"

foldlFM :: Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM :: forall k b a. Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM b -> a -> b
_ b
x FM k a
E = b
x
foldlFM b -> a -> b
f b
x (I k
k a
a FM k a
m) = (b -> a -> b) -> b -> FM k a -> b
forall k b a. Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM b -> a -> b
f (b -> a -> b
f b
x a
a) (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

foldlFM' :: Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM' :: forall k b a. Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM' b -> a -> b
_ b
x FM k a
E = b
x
foldlFM' b -> a -> b
f b
x (I k
k a
a FM k a
m) = b
x b -> b -> b
forall a b. a -> b -> b
`seq` (b -> a -> b) -> b -> FM k a -> b
forall k b a. Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM' b -> a -> b
f (b -> a -> b
f b
x a
a) (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

foldrWithKeyFM :: Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKeyFM :: forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKeyFM k -> a -> b -> b
_ b
z FM k a
E = b
z
foldrWithKeyFM k -> a -> b -> b
f b
z (I k
k a
a FM k a
m) = k -> a -> b -> b
f k
k a
a ((k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKeyFM k -> a -> b -> b
f b
z (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))

foldrWithKeyFM' :: Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKeyFM' :: forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKeyFM' k -> a -> b -> b
_ b
z FM k a
E = b
z
foldrWithKeyFM' k -> a -> b -> b
f b
z (I k
k a
a FM k a
m) = k -> a -> b -> b
f k
k a
a (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! ((k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKeyFM' k -> a -> b -> b
f b
z (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))

foldlWithKeyFM :: Eq k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKeyFM :: forall k b a. Eq k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKeyFM b -> k -> a -> b
_ b
x FM k a
E = b
x
foldlWithKeyFM b -> k -> a -> b
f b
x (I k
k a
a FM k a
m) = (b -> k -> a -> b) -> b -> FM k a -> b
forall k b a. Eq k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKeyFM b -> k -> a -> b
f (b -> k -> a -> b
f b
x k
k a
a) (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

foldlWithKeyFM' :: Eq k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKeyFM' :: forall k b a. Eq k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKeyFM' b -> k -> a -> b
_ b
x FM k a
E = b
x
foldlWithKeyFM' b -> k -> a -> b
f b
x (I k
k a
a FM k a
m) = b
x b -> b -> b
forall a b. a -> b -> b
`seq` (b -> k -> a -> b) -> b -> FM k a -> b
forall k b a. Eq k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKeyFM' b -> k -> a -> b
f (b -> k -> a -> b
f b
x k
k a
a) (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

takeWhileFM :: (k -> Bool) -> FM k a -> FM k a
takeWhileFM :: forall k a. (k -> Bool) -> FM k a -> FM k a
takeWhileFM k -> Bool
_ FM k a
E = FM k a
forall k a. FM k a
E
takeWhileFM k -> Bool
p (I k
k a
a FM k a
m)
   | k -> Bool
p k
k       = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
a ((k -> Bool) -> FM k a -> FM k a
forall k a. (k -> Bool) -> FM k a -> FM k a
takeWhileFM k -> Bool
p FM k a
m)
   | Bool
otherwise = FM k a
forall k a. FM k a
E

dropWhileFM :: (k -> Bool) -> FM k a -> FM k a
dropWhileFM :: forall k a. (k -> Bool) -> FM k a -> FM k a
dropWhileFM k -> Bool
_ FM k a
E = FM k a
forall k a. FM k a
E
dropWhileFM k -> Bool
p o :: FM k a
o@(I k
k a
_ FM k a
m)
   | k -> Bool
p k
k       = (k -> Bool) -> FM k a -> FM k a
forall k a. (k -> Bool) -> FM k a -> FM k a
dropWhileFM k -> Bool
p FM k a
m
   | Bool
otherwise = FM k a
o

spanFM :: (k -> Bool) -> FM k a -> (FM k a,FM k a)
spanFM :: forall k a. (k -> Bool) -> FM k a -> (FM k a, FM k a)
spanFM k -> Bool
_ FM k a
E = (FM k a
forall k a. FM k a
E,FM k a
forall k a. FM k a
E)
spanFM k -> Bool
p o :: FM k a
o@(I k
k a
a FM k a
m)
   | k -> Bool
p k
k       = let (FM k a
x,FM k a
y) = (k -> Bool) -> FM k a -> (FM k a, FM k a)
forall k a. (k -> Bool) -> FM k a -> (FM k a, FM k a)
spanFM k -> Bool
p FM k a
m in (k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
a FM k a
x,FM k a
y)
   | Bool
otherwise = (FM k a
forall k a. FM k a
E,FM k a
o)


---------------------------------------------------
-- interface functions

empty :: forall k a. Eq k => FM k a
empty = FM k a
forall k a. FM k a
E
singleton :: forall k a. Eq k => k -> a -> FM k a
singleton k
k a
x = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x FM k a
forall k a. FM k a
E
insert :: forall k a. Eq k => k -> a -> FM k a -> FM k a
insert = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I
insertSeq :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq (k, a) -> FM k a -> FM k a
insertSeq seq (k, a)
kxs FM k a
m = ((k, a) -> FM k a -> FM k a) -> FM k a -> seq (k, a) -> FM k a
forall a b. (a -> b -> b) -> b -> seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr (k, a) -> FM k a -> FM k a
forall t t1. (t, t1) -> FM t t1 -> FM t t1
uinsert FM k a
m seq (k, a)
kxs
fromSeq :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq (k, a) -> FM k a
fromSeq = ((k, a) -> FM k a -> FM k a) -> FM k a -> seq (k, a) -> FM k a
forall a b. (a -> b -> b) -> b -> seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr (k, a) -> FM k a -> FM k a
forall t t1. (t, t1) -> FM t t1 -> FM t t1
uinsert FM k a
forall k a. FM k a
E

union :: forall k a. Eq k => FM k a -> FM k a -> FM k a
union FM k a
m FM k a
E = FM k a
m
union FM k a
E FM k a
m = FM k a
m
union (I k
k a
x FM k a
m1) FM k a
m2 = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x (FM k a -> FM k a -> FM k a
forall k a. Eq k => FM k a -> FM k a -> FM k a
union FM k a
m1 FM k a
m2)

unionSeq :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq (FM k a) -> FM k a
unionSeq = (FM k a -> FM k a -> FM k a) -> FM k a -> seq (FM k a) -> FM k a
forall a b. (a -> b -> b) -> b -> seq a -> b
forall (s :: * -> *) a b.
Sequence s =>
(a -> b -> b) -> b -> s a -> b
S.foldr FM k a -> FM k a -> FM k a
forall k a. Eq k => FM k a -> FM k a -> FM k a
union FM k a
forall k a. FM k a
E

deleteAll :: forall k a. Eq k => k -> FM k a -> FM k a
deleteAll k
_ FM k a
E = FM k a
forall k a. FM k a
E
deleteAll k
key (I k
k a
x FM k a
m) | k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k  = k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
deleteAll k
key FM k a
m
                        | Bool
otherwise = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
deleteAll k
key FM k a
m)

delete :: forall k a. Eq k => k -> FM k a -> FM k a
delete = k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
deleteAll

null :: forall k a. Eq k => FM k a -> Bool
null FM k a
E = Bool
True
null (I k
_ a
_ FM k a
_) = Bool
False

size :: forall k a. Eq k => FM k a -> Int
size FM k a
E = Int
0
size (I k
k a
_ FM k a
m) = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FM k a -> Int
forall k a. Eq k => FM k a -> Int
size (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

member :: forall k a. Eq k => k -> FM k a -> Bool
member k
_ FM k a
E = Bool
False
member k
key (I k
k a
_ FM k a
m) = k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k Bool -> Bool -> Bool
|| k -> FM k a -> Bool
forall k a. Eq k => k -> FM k a -> Bool
member k
key FM k a
m

count :: forall k a. Eq k => k -> FM k a -> Int
count k
_ FM k a
E = Int
0
count k
key (I k
k a
_ FM k a
m) | k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k  = Int
1
                    | Bool
otherwise = k -> FM k a -> Int
forall k a. Eq k => k -> FM k a -> Int
count k
key FM k a
m

lookup :: forall k a. Eq k => k -> FM k a -> a
lookup k
key FM k a
m = Fail a -> a
forall a. Fail a -> a
runFail_ (k -> FM k a -> Fail a
forall k (rm :: * -> *) a.
(Eq k, MonadFail rm) =>
k -> FM k a -> rm a
lookupM k
key FM k a
m)

lookupM :: forall k (rm :: * -> *) a.
(Eq k, MonadFail rm) =>
k -> FM k a -> rm a
lookupM k
_ FM k a
E = String -> rm a
forall a. String -> rm a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"AssocList.lookup: lookup failed"
lookupM k
key (I k
k a
x FM k a
m) | k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k  = a -> rm a
forall a. a -> rm a
forall (m :: * -> *) a. Monad m => a -> m a
return a
x
                      | Bool
otherwise = k -> FM k a -> rm a
forall k (rm :: * -> *) a.
(Eq k, MonadFail rm) =>
k -> FM k a -> rm a
lookupM k
key FM k a
m

lookupAll :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
k -> FM k a -> seq a
lookupAll k
_ FM k a
E = seq a
forall (s :: * -> *) a. Sequence s => s a
S.empty
lookupAll k
key (I k
k a
x FM k a
m) | k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k  = a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a
S.singleton a
x
                        | Bool
otherwise = k -> FM k a -> seq a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
k -> FM k a -> seq a
lookupAll k
key FM k a
m

lookupAndDelete :: forall k a. Eq k => k -> FM k a -> (a, FM k a)
lookupAndDelete k
key FM k a
m = Fail (a, FM k a) -> (a, FM k a)
forall a. Fail a -> a
runFail_ (k -> FM k a -> Fail (a, FM k a)
forall k (rm :: * -> *) a.
(Eq k, MonadFail rm) =>
k -> FM k a -> rm (a, FM k a)
lookupAndDeleteM k
key FM k a
m)

lookupAndDeleteM :: forall k (rm :: * -> *) a.
(Eq k, MonadFail rm) =>
k -> FM k a -> rm (a, FM k a)
lookupAndDeleteM k
_ FM k a
E = String -> rm (a, FM k a)
forall a. String -> rm a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"AssocList.lookupAndDeleteM: lookup failed"
lookupAndDeleteM k
key (I k
k a
x FM k a
m)
   | k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k  = (a, FM k a) -> rm (a, FM k a)
forall a. a -> rm a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x,k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)
   | Bool
otherwise = k -> FM k a -> rm (a, FM k a)
forall k (rm :: * -> *) a.
(Eq k, MonadFail rm) =>
k -> FM k a -> rm (a, FM k a)
lookupAndDeleteM k
key FM k a
m rm (a, FM k a) -> ((a, FM k a) -> rm (a, FM k a)) -> rm (a, FM k a)
forall a b. rm a -> (a -> rm b) -> rm b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>=
                    \ (a
z, FM k a
m') -> (a, FM k a) -> rm (a, FM k a)
forall a. a -> rm a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
z, k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x FM k a
m')

lookupAndDeleteAll :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
k -> FM k a -> (seq a, FM k a)
lookupAndDeleteAll k
key FM k a
m =
   case k -> FM k a -> Maybe (a, FM k a)
forall k (rm :: * -> *) a.
(Eq k, MonadFail rm) =>
k -> FM k a -> rm (a, FM k a)
lookupAndDeleteM k
key FM k a
m of
      Maybe (a, FM k a)
Nothing     -> (seq a
forall (s :: * -> *) a. Sequence s => s a
S.empty,FM k a
m)
      Just (a
z,FM k a
m') -> (a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a
S.singleton a
z,FM k a
m')


lookupWithDefault :: forall k a. Eq k => a -> k -> FM k a -> a
lookupWithDefault a
d k
_ FM k a
E = a
d
lookupWithDefault a
d k
key (I k
k a
x FM k a
m) | k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k = a
x
                                  | Bool
otherwise = a -> k -> FM k a -> a
forall k a. Eq k => a -> k -> FM k a -> a
lookupWithDefault a
d k
key FM k a
m

elements :: forall k (seq :: * -> *) a. (Eq k, Sequence seq) => FM k a -> seq a
elements FM k a
E = seq a
forall (s :: * -> *) a. Sequence s => s a
S.empty
elements (I k
k a
x FM k a
m) = a -> seq a -> seq a
forall a. a -> seq a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons a
x (FM k a -> seq a
forall k (seq :: * -> *) a. (Eq k, Sequence seq) => FM k a -> seq a
elements (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))

adjust :: forall k a. Eq k => (a -> a) -> k -> FM k a -> FM k a
adjust a -> a
_ k
_ FM k a
E = FM k a
forall k a. FM k a
E
adjust a -> a
f k
key (I k
k a
x FM k a
m) | k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k  = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
key (a -> a
f a
x) FM k a
m
                       | Bool
otherwise = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x ((a -> a) -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> a) -> k -> FM k a -> FM k a
adjust a -> a
f k
key FM k a
m)

adjustAll :: forall k a. Eq k => (a -> a) -> k -> FM k a -> FM k a
adjustAll = (a -> a) -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> a) -> k -> FM k a -> FM k a
adjust

adjustOrInsert :: forall k a. Eq k => (a -> a) -> a -> k -> FM k a -> FM k a
adjustOrInsert a -> a
_ a
z k
key FM k a
E = k -> a -> FM k a
forall k a. Eq k => k -> a -> FM k a
singleton k
key a
z
adjustOrInsert a -> a
f a
z k
key (I k
k a
x FM k a
m)
    | k
key k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k  = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
key (a -> a
f a
x) FM k a
m
    | Bool
otherwise = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x ((a -> a) -> a -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> a) -> a -> k -> FM k a -> FM k a
adjustOrInsert a -> a
f a
z k
key FM k a
m)

adjustAllOrInsert :: forall k a. Eq k => (a -> a) -> a -> k -> FM k a -> FM k a
adjustAllOrInsert = (a -> a) -> a -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> a) -> a -> k -> FM k a -> FM k a
adjustOrInsert

adjustOrDelete :: forall k a. Eq k => (a -> Maybe a) -> k -> FM k a -> FM k a
adjustOrDelete = (a -> Maybe a) -> k -> FM k a -> FM k a
forall (m :: * -> *) k a.
AssocX m k =>
(a -> Maybe a) -> k -> m a -> m a
adjustOrDeleteDefault
adjustOrDeleteAll :: forall k a. Eq k => (a -> Maybe a) -> k -> FM k a -> FM k a
adjustOrDeleteAll = (a -> Maybe a) -> k -> FM k a -> FM k a
forall (m :: * -> *) k a.
AssocX m k =>
(a -> Maybe a) -> k -> m a -> m a
adjustOrDeleteAllDefault

map :: forall k a b. Eq k => (a -> b) -> FM k a -> FM k b
map a -> b
_ FM k a
E = FM k b
forall k a. FM k a
E
map a -> b
f (I k
k a
x FM k a
m) = k -> b -> FM k b -> FM k b
forall k a. k -> a -> FM k a -> FM k a
I k
k (a -> b
f a
x) ((a -> b) -> FM k a -> FM k b
forall k a b. Eq k => (a -> b) -> FM k a -> FM k b
map a -> b
f FM k a
m)

fold :: forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
fold a -> b -> b
_ b
c FM k a
E = b
c
fold a -> b -> b
f b
c (I k
k a
x FM k a
m) = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
fold a -> b -> b
f (a -> b -> b
f a
x b
c) (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

fold' :: forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
fold' a -> b -> b
_ b
c FM k a
E = b
c
fold' a -> b -> b
f b
c (I k
k a
x FM k a
m) = b
c b -> b -> b
forall a b. a -> b -> b
`seq` (a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
fold' a -> b -> b
f (a -> b -> b
f a
x b
c) (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

fold1 :: forall k a. Eq k => (a -> a -> a) -> FM k a -> a
fold1 a -> a -> a
_ FM k a
E = String -> a
forall a. HasCallStack => String -> a
error String
"AssocList.fold1: empty map"
fold1 a -> a -> a
f (I k
k a
x FM k a
m) = (a -> a -> a) -> a -> FM k a -> a
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
fold a -> a -> a
f a
x (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

fold1' :: forall k a. Eq k => (a -> a -> a) -> FM k a -> a
fold1' a -> a -> a
_ FM k a
E = String -> a
forall a. HasCallStack => String -> a
error String
"AssocList.fold1': empty map"
fold1' a -> a -> a
f (I k
k a
x FM k a
m) = (a -> a -> a) -> a -> FM k a -> a
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
fold' a -> a -> a
f a
x (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

filter :: forall k a. Eq k => (a -> Bool) -> FM k a -> FM k a
filter a -> Bool
_ FM k a
E = FM k a
forall k a. FM k a
E
filter a -> Bool
p (I k
k a
x FM k a
m) | a -> Bool
p a
x = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x ((a -> Bool) -> FM k a -> FM k a
forall k a. Eq k => (a -> Bool) -> FM k a -> FM k a
filter a -> Bool
p (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))
                   | Bool
otherwise = (a -> Bool) -> FM k a -> FM k a
forall k a. Eq k => (a -> Bool) -> FM k a -> FM k a
filter a -> Bool
p (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

partition :: forall k a. Eq k => (a -> Bool) -> FM k a -> (FM k a, FM k a)
partition a -> Bool
_ FM k a
E = (FM k a
forall k a. FM k a
E, FM k a
forall k a. FM k a
E)
partition a -> Bool
p (I k
k a
x FM k a
m)
    | a -> Bool
p a
x       = (k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x FM k a
m1,FM k a
m2)
    | Bool
otherwise = (FM k a
m1,k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x FM k a
m2)
  where (FM k a
m1,FM k a
m2) = (a -> Bool) -> FM k a -> (FM k a, FM k a)
forall k a. Eq k => (a -> Bool) -> FM k a -> (FM k a, FM k a)
partition a -> Bool
p (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)


toSeq :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
FM k a -> seq (k, a)
toSeq FM k a
E = seq (k, a)
forall (s :: * -> *) a. Sequence s => s a
S.empty
toSeq (I k
k a
x FM k a
m) = (k, a) -> seq (k, a) -> seq (k, a)
forall a. a -> seq a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons (k
k,a
x) (FM k a -> seq (k, a)
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
FM k a -> seq (k, a)
toSeq (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))

keys :: forall k (seq :: * -> *) a. (Eq k, Sequence seq) => FM k a -> seq k
keys FM k a
E = seq k
forall (s :: * -> *) a. Sequence s => s a
S.empty
keys (I k
k a
_ FM k a
m) = k -> seq k -> seq k
forall a. a -> seq a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons k
k (FM k a -> seq k
forall k (seq :: * -> *) a. (Eq k, Sequence seq) => FM k a -> seq k
keys (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))

mapWithKey :: forall k a b. Eq k => (k -> a -> b) -> FM k a -> FM k b
mapWithKey k -> a -> b
_ FM k a
E = FM k b
forall k a. FM k a
E
mapWithKey k -> a -> b
f (I k
k a
x FM k a
m) = k -> b -> FM k b -> FM k b
forall k a. k -> a -> FM k a -> FM k a
I k
k (k -> a -> b
f k
k a
x) ((k -> a -> b) -> FM k a -> FM k b
forall k a b. Eq k => (k -> a -> b) -> FM k a -> FM k b
mapWithKey k -> a -> b
f FM k a
m)

foldWithKey :: forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldWithKey k -> a -> b -> b
_ b
c FM k a
E = b
c
foldWithKey k -> a -> b -> b
f b
c (I k
k a
x FM k a
m) = (k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldWithKey k -> a -> b -> b
f (k -> a -> b -> b
f k
k a
x b
c) (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

foldWithKey' :: forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldWithKey' k -> a -> b -> b
_ b
c FM k a
E = b
c
foldWithKey' k -> a -> b -> b
f b
c (I k
k a
x FM k a
m) = b
c b -> b -> b
forall a b. a -> b -> b
`seq` (k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldWithKey' k -> a -> b -> b
f (k -> a -> b -> b
f k
k a
x b
c) (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

filterWithKey :: forall k a. Eq k => (k -> a -> Bool) -> FM k a -> FM k a
filterWithKey k -> a -> Bool
_ FM k a
E = FM k a
forall k a. FM k a
E
filterWithKey k -> a -> Bool
p (I k
k a
x FM k a
m)
    | k -> a -> Bool
p k
k a
x = k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x ((k -> a -> Bool) -> FM k a -> FM k a
forall k a. Eq k => (k -> a -> Bool) -> FM k a -> FM k a
filterWithKey k -> a -> Bool
p (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m))
    | Bool
otherwise = (k -> a -> Bool) -> FM k a -> FM k a
forall k a. Eq k => (k -> a -> Bool) -> FM k a -> FM k a
filterWithKey k -> a -> Bool
p (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

partitionWithKey :: forall k a. Eq k => (k -> a -> Bool) -> FM k a -> (FM k a, FM k a)
partitionWithKey k -> a -> Bool
_ FM k a
E = (FM k a
forall k a. FM k a
E, FM k a
forall k a. FM k a
E)
partitionWithKey k -> a -> Bool
p (I k
k a
x FM k a
m)
    | k -> a -> Bool
p k
k a
x     = (k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x FM k a
m1,FM k a
m2)
    | Bool
otherwise = (FM k a
m1,k -> a -> FM k a -> FM k a
forall k a. k -> a -> FM k a -> FM k a
I k
k a
x FM k a
m2)
  where (FM k a
m1,FM k a
m2) = (k -> a -> Bool) -> FM k a -> (FM k a, FM k a)
forall k a. Eq k => (k -> a -> Bool) -> FM k a -> (FM k a, FM k a)
partitionWithKey k -> a -> Bool
p (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
m)

unionl :: forall k a. Eq k => FM k a -> FM k a -> FM k a
unionl = FM k a -> FM k a -> FM k a
forall k a. Eq k => FM k a -> FM k a -> FM k a
union
unionr :: forall k a. Eq k => FM k a -> FM k a -> FM k a
unionr = (FM k a -> FM k a -> FM k a) -> FM k a -> FM k a -> FM k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip FM k a -> FM k a -> FM k a
forall k a. Eq k => FM k a -> FM k a -> FM k a
union


findMin :: (Ord t) => t -> t1 -> FM t t1 -> (t, t1)
findMin :: forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMin t
k0 t1
x FM t t1
E = (t
k0,t1
x)
findMin t
k0 t1
a0 (I t
k t1
a FM t t1
m)
        | t
k t -> t -> Bool
forall a. Ord a => a -> a -> Bool
< t
k0    = t -> t1 -> FM t t1 -> (t, t1)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMin t
k  t1
a  (t -> FM t t1 -> FM t t1
forall k a. Eq k => k -> FM k a -> FM k a
delete t
k FM t t1
m)
        | Bool
otherwise = t -> t1 -> FM t t1 -> (t, t1)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMin t
k0 t1
a0 (t -> FM t t1 -> FM t t1
forall k a. Eq k => k -> FM k a -> FM k a
delete t
k FM t t1
m)

findMax ::( Ord t) => t -> t1 -> FM t t1 -> (t, t1)
findMax :: forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMax t
k0 t1
x FM t t1
E = (t
k0,t1
x)
findMax t
k0 t1
a0 (I t
k t1
a FM t t1
m)
        | t
k t -> t -> Bool
forall a. Ord a => a -> a -> Bool
> t
k0    = t -> t1 -> FM t t1 -> (t, t1)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMax t
k  t1
a  (t -> FM t t1 -> FM t t1
forall k a. Eq k => k -> FM k a -> FM k a
delete t
k FM t t1
m)
        | Bool
otherwise = t -> t1 -> FM t t1 -> (t, t1)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMax t
k0 t1
a0 (t -> FM t t1 -> FM t t1
forall k a. Eq k => k -> FM k a -> FM k a
delete t
k FM t t1
m)

minView :: forall k (m :: * -> *) a.
(Ord k, MonadFail m) =>
FM k a -> m (a, FM k a)
minView FM k a
E = String -> m (a, FM k a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minView: empty map")
minView n :: FM k a
n@(I k
k a
a FM k a
m) = let (k
k',a
x) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMin k
k a
a FM k a
m in (a, FM k a) -> m (a, FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x,k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k' FM k a
n)

minElem :: forall k a. Ord k => FM k a -> a
minElem FM k a
E = String -> a
forall a. HasCallStack => String -> a
error (String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minElem: empty map")
minElem (I k
k a
a FM k a
m) = let (k
_,a
x) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMin k
k a
a FM k a
m in a
x

deleteMin :: forall t t1. Ord t => FM t t1 -> FM t t1
deleteMin FM k a
E = String -> FM k a
forall a. HasCallStack => String -> a
error (String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".deleteMin: empty map")
deleteMin n :: FM k a
n@(I k
k a
a FM k a
m) = let (k
k',a
_) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMin k
k a
a FM k a
m in k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k' FM k a
n

unsafeInsertMin :: forall k a. Ord k => k -> a -> FM k a -> FM k a
unsafeInsertMin  = k -> a -> FM k a -> FM k a
forall k a. Eq k => k -> a -> FM k a -> FM k a
insert

maxView :: forall k (m :: * -> *) a.
(Ord k, MonadFail m) =>
FM k a -> m (a, FM k a)
maxView FM k a
E = String -> m (a, FM k a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxView: empty map")
maxView n :: FM k a
n@(I k
k a
a FM k a
m) = let (k
k',a
x) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMax k
k a
a FM k a
m in (a, FM k a) -> m (a, FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x,k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k' FM k a
n)

maxElem :: forall k a. Ord k => FM k a -> a
maxElem FM k a
E = String -> a
forall a. HasCallStack => String -> a
error (String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxElem: empty map")
maxElem (I k
k a
a FM k a
m) = let (k
_,a
x) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMax k
k a
a FM k a
m in a
x

deleteMax :: forall t t1. Ord t => FM t t1 -> FM t t1
deleteMax FM k a
E = String -> FM k a
forall a. HasCallStack => String -> a
error (String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".deleteMax: empty map")
deleteMax n :: FM k a
n@(I k
k a
a FM k a
m) = let (k
k',a
_) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMax k
k a
a FM k a
m in k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k' FM k a
n

unsafeInsertMax :: forall k a. Ord k => k -> a -> FM k a -> FM k a
unsafeInsertMax = k -> a -> FM k a -> FM k a
forall k a. Eq k => k -> a -> FM k a -> FM k a
insert

foldr :: forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr  a -> b -> b
f b
z FM k a
m = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
foldrFM  a -> b -> b
f b
z (FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM FM k a
m)
foldr' :: forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr' a -> b -> b
f b
z FM k a
m = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
foldrFM' a -> b -> b
f b
z (FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM FM k a
m)

foldr1 :: forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldr1 a -> a -> a
f FM k a
m =
  case FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM FM k a
m of
    FM k a
E -> String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".foldlr1: empty map"
    FM k a
n -> (a -> a -> a) -> FM k a -> a
forall k a. Eq k => (a -> a -> a) -> FM k a -> a
foldr1FM a -> a -> a
f FM k a
n

foldr1' :: forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldr1' a -> a -> a
f FM k a
m =
  case FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM FM k a
m of
    FM k a
E -> String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".foldlr1': empty map"
    FM k a
n -> (a -> a -> a) -> FM k a -> a
forall k a. Eq k => (a -> a -> a) -> FM k a -> a
foldr1FM' a -> a -> a
f FM k a
n

foldl :: forall k b a. Ord k => (b -> a -> b) -> b -> FM k a -> b
foldl  b -> a -> b
f b
x FM k a
m = (b -> a -> b) -> b -> FM k a -> b
forall k b a. Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM  b -> a -> b
f b
x (FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM FM k a
m)
foldl' :: forall k b a. Ord k => (b -> a -> b) -> b -> FM k a -> b
foldl' b -> a -> b
f b
x FM k a
m = (b -> a -> b) -> b -> FM k a -> b
forall k b a. Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM' b -> a -> b
f b
x (FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM FM k a
m)

foldl1 :: forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldl1 a -> a -> a
f FM k a
m =
  case FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM FM k a
m of
    FM k a
E -> String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".foldl1: empty map"
    I k
k a
a FM k a
n -> (a -> a -> a) -> a -> FM k a -> a
forall k b a. Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM a -> a -> a
f a
a (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
n)

foldl1' :: forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldl1' a -> a -> a
f FM k a
m =
  case FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM FM k a
m of
    FM k a
E -> String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".foldl1': empty map"
    I k
k a
a FM k a
n -> (a -> a -> a) -> a -> FM k a -> a
forall k b a. Eq k => (b -> a -> b) -> b -> FM k a -> b
foldlFM' a -> a -> a
f a
a (k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
n)

unsafeFromOrdSeq :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
seq (k, a) -> FM k a
unsafeFromOrdSeq   = seq (k, a) -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq (k, a) -> FM k a
fromSeq
unsafeAppend :: forall t t1. Ord t => FM t t1 -> FM t t1 -> FM t t1
unsafeAppend       = FM k a -> FM k a -> FM k a
forall k a. Eq k => FM k a -> FM k a -> FM k a
union
filterLT :: forall k a. Ord k => k -> FM k a -> FM k a
filterLT k
k         = (k -> Bool) -> FM k a -> FM k a
forall k a. (k -> Bool) -> FM k a -> FM k a
takeWhileFM (k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<k
k)  (FM k a -> FM k a) -> (FM k a -> FM k a) -> FM k a -> FM k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
filterLE :: forall k a. Ord k => k -> FM k a -> FM k a
filterLE k
k         = (k -> Bool) -> FM k a -> FM k a
forall k a. (k -> Bool) -> FM k a -> FM k a
takeWhileFM (k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<=k
k) (FM k a -> FM k a) -> (FM k a -> FM k a) -> FM k a -> FM k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
filterGT :: forall k a. Ord k => k -> FM k a -> FM k a
filterGT k
k         = (k -> Bool) -> FM k a -> FM k a
forall k a. (k -> Bool) -> FM k a -> FM k a
dropWhileFM (k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<=k
k) (FM k a -> FM k a) -> (FM k a -> FM k a) -> FM k a -> FM k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
filterGE :: forall k a. Ord k => k -> FM k a -> FM k a
filterGE k
k         = (k -> Bool) -> FM k a -> FM k a
forall k a. (k -> Bool) -> FM k a -> FM k a
dropWhileFM (k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<k
k)  (FM k a -> FM k a) -> (FM k a -> FM k a) -> FM k a -> FM k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
partitionLT_GE :: forall k a. Ord k => k -> FM k a -> (FM k a, FM k a)
partitionLT_GE k
k   = (k -> Bool) -> FM k a -> (FM k a, FM k a)
forall k a. (k -> Bool) -> FM k a -> (FM k a, FM k a)
spanFM (k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<k
k)  (FM k a -> (FM k a, FM k a))
-> (FM k a -> FM k a) -> FM k a -> (FM k a, FM k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
partitionLE_GT :: forall k a. Ord k => k -> FM k a -> (FM k a, FM k a)
partitionLE_GT k
k   = (k -> Bool) -> FM k a -> (FM k a, FM k a)
forall k a. (k -> Bool) -> FM k a -> (FM k a, FM k a)
spanFM (k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<=k
k) (FM k a -> (FM k a, FM k a))
-> (FM k a -> FM k a) -> FM k a -> (FM k a, FM k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
partitionLT_GT :: forall k a. Ord k => k -> FM k a -> (FM k a, FM k a)
partitionLT_GT k
k   = (\(FM k a
x,FM k a
y) -> (FM k a
x,k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k FM k a
y)) ((FM k a, FM k a) -> (FM k a, FM k a))
-> (FM k a -> (FM k a, FM k a)) -> FM k a -> (FM k a, FM k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> Bool) -> FM k a -> (FM k a, FM k a)
forall k a. (k -> Bool) -> FM k a -> (FM k a, FM k a)
spanFM (k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<k
k)  (FM k a -> (FM k a, FM k a))
-> (FM k a -> FM k a) -> FM k a -> (FM k a, FM k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM

minViewWithKey :: forall k (m :: * -> *) a.
(Ord k, MonadFail m) =>
FM k a -> m ((k, a), FM k a)
minViewWithKey FM k a
E   = String -> m ((k, a), FM k a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m ((k, a), FM k a)) -> String -> m ((k, a), FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minViewWithKey: empty map"
minViewWithKey n :: FM k a
n@(I k
k a
a FM k a
m) = let (k
k',a
x) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMin k
k a
a FM k a
m in ((k, a), FM k a) -> m ((k, a), FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((k
k',a
x),k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k' FM k a
n)

minElemWithKey :: forall k a. Ord k => FM k a -> (k, a)
minElemWithKey FM k a
E   = String -> (k, a)
forall a. HasCallStack => String -> a
error (String -> (k, a)) -> String -> (k, a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minElemWithKey: empty map"
minElemWithKey (I k
k a
a FM k a
m) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMin k
k a
a FM k a
m

maxViewWithKey :: forall k (m :: * -> *) a.
(Ord k, MonadFail m) =>
FM k a -> m ((k, a), FM k a)
maxViewWithKey FM k a
E   = String -> m ((k, a), FM k a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m ((k, a), FM k a)) -> String -> m ((k, a), FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxViewWithKey: empty map"
maxViewWithKey n :: FM k a
n@(I k
k a
a FM k a
m) = let (k
k',a
x) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMax k
k a
a FM k a
m in ((k, a), FM k a) -> m ((k, a), FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((k
k',a
x),k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete k
k' FM k a
n)

maxElemWithKey :: forall k a. Ord k => FM k a -> (k, a)
maxElemWithKey FM k a
E   = String -> (k, a)
forall a. HasCallStack => String -> a
error (String -> (k, a)) -> String -> (k, a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxElemWithKey: empty map"
maxElemWithKey (I k
k a
a FM k a
m) = k -> a -> FM k a -> (k, a)
forall t t1. Ord t => t -> t1 -> FM t t1 -> (t, t1)
findMax k
k a
a FM k a
m

foldrWithKey :: forall k a b. Ord k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey  k -> a -> b -> b
f b
z   = (k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKeyFM  k -> a -> b -> b
f b
z (FM k a -> b) -> (FM k a -> FM k a) -> FM k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
foldrWithKey' :: forall k a b. Ord k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey' k -> a -> b -> b
f b
z   = (k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKeyFM' k -> a -> b -> b
f b
z (FM k a -> b) -> (FM k a -> FM k a) -> FM k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
foldlWithKey :: forall k b a. Ord k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKey  b -> k -> a -> b
f b
x   = (b -> k -> a -> b) -> b -> FM k a -> b
forall k b a. Eq k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKeyFM  b -> k -> a -> b
f b
x (FM k a -> b) -> (FM k a -> FM k a) -> FM k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
foldlWithKey' :: forall k b a. Ord k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKey' b -> k -> a -> b
f b
x   = (b -> k -> a -> b) -> b -> FM k a -> b
forall k b a. Eq k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKeyFM' b -> k -> a -> b
f b
x (FM k a -> b) -> (FM k a -> FM k a) -> FM k a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM
toOrdSeq :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
FM k a -> seq (k, a)
toOrdSeq            = FM k a -> seq (k, a)
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
FM k a -> seq (k, a)
toSeq (FM k a -> seq (k, a))
-> (FM k a -> FM k a) -> FM k a -> seq (k, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
mergeSortFM


strict :: forall k a. FM k a -> FM k a
strict n :: FM k a
n@FM k a
E = FM k a
n
strict n :: FM k a
n@(I k
_ a
_ FM k a
m) = FM k a -> FM k a
forall k a. FM k a -> FM k a
strict FM k a
m FM k a -> FM k a -> FM k a
forall a b. a -> b -> b
`seq` FM k a
n

strictWith :: forall a b k. (a -> b) -> FM k a -> FM k a
strictWith a -> b
_ n :: FM k a
n@FM k a
E = FM k a
n
strictWith a -> b
f n :: FM k a
n@(I k
_ a
a FM k a
m) = a -> b
f a
a b -> FM k a -> FM k a
forall a b. a -> b -> b
`seq` (a -> b) -> FM k a -> FM k a
forall a b k. (a -> b) -> FM k a -> FM k a
strictWith a -> b
f FM k a
m FM k a -> FM k a -> FM k a
forall a b. a -> b -> b
`seq` FM k a
n


-- defaults

deleteSeq :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq k -> FM k a -> FM k a
deleteSeq = seq k -> FM k a -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq k -> m a -> m a
deleteSeqUsingFoldr
insertWith :: forall k a. Eq k => (a -> a -> a) -> k -> a -> FM k a -> FM k a
insertWith = (a -> a -> a) -> k -> a -> FM k a -> FM k a
forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> a) -> k -> a -> m a -> m a
insertWithUsingLookupM
insertSeqWith :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
insertSeqWith = (a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithUsingInsertWith
insertWithKey :: forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> FM k a -> FM k a
insertWithKey = (k -> a -> a -> a) -> k -> a -> FM k a -> FM k a
forall (m :: * -> *) k a.
FiniteMapX m k =>
(k -> a -> a -> a) -> k -> a -> m a -> m a
insertWithKeyUsingInsertWith
insertSeqWithKey :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
insertSeqWithKey = (k -> a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithKeyUsingInsertWithKey
unionWith :: forall k a. Eq k => (a -> a -> a) -> FM k a -> FM k a -> FM k a
unionWith = (a -> a -> a) -> FM k a -> FM k a -> FM k a
forall (m :: * -> *) k a.
FiniteMap m k =>
(a -> a -> a) -> m a -> m a -> m a
unionWithUsingInsertWith
unionSeqWith :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(a -> a -> a) -> seq (FM k a) -> FM k a
unionSeqWith = (a -> a -> a) -> seq (FM k a) -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (m a) -> m a
unionSeqWithUsingFoldr
fromSeqWith :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> FM k a
fromSeqWith = (a -> a -> a) -> seq (k, a) -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> m a
fromSeqWithUsingInsertSeqWith
fromSeqWithKey :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> FM k a
fromSeqWithKey = (k -> a -> a -> a) -> seq (k, a) -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> m a
fromSeqWithKeyUsingInsertSeqWithKey
intersectionWith :: forall k a b c. Eq k => (a -> b -> c) -> FM k a -> FM k b -> FM k c
intersectionWith = (a -> b -> c) -> FM k a -> FM k b -> FM k c
forall (m :: * -> *) k a b c.
FiniteMap m k =>
(a -> b -> c) -> m a -> m b -> m c
intersectionWithUsingLookupM
difference :: forall k a b. Eq k => FM k a -> FM k b -> FM k a
difference = FM k a -> FM k b -> FM k a
forall (m :: * -> *) k a b. FiniteMap m k => m a -> m b -> m a
differenceUsingDelete
properSubset :: forall k a b. Eq k => FM k a -> FM k b -> Bool
properSubset = FM k a -> FM k b -> Bool
forall (m :: * -> *) k a b. FiniteMapX m k => m a -> m b -> Bool
properSubsetUsingSubset
subset :: forall k a b. Eq k => FM k a -> FM k b -> Bool
subset = FM k a -> FM k b -> Bool
forall (m :: * -> *) k a b. FiniteMap m k => m a -> m b -> Bool
subsetUsingMember
properSubmapBy :: forall k a. Eq k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
properSubmapBy = (a -> a -> Bool) -> FM k a -> FM k a -> Bool
forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
properSubmapByUsingSubmapBy
submapBy :: forall k a. Eq k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
submapBy = (a -> a -> Bool) -> FM k a -> FM k a -> Bool
forall (m :: * -> *) k a.
FiniteMap m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
submapByUsingLookupM
sameMapBy :: forall k a. Eq k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
sameMapBy = (a -> a -> Bool) -> FM k a -> FM k a -> Bool
forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
sameMapByUsingSubmapBy
properSubmap :: forall k a. (Eq k, Eq a) => FM k a -> FM k a -> Bool
properSubmap = FM k a -> FM k a -> Bool
forall a (m :: * -> *) k.
(Eq a, FiniteMapX m k) =>
m a -> m a -> Bool
A.properSubmap
submap :: forall k a. (Eq k, Eq a) => FM k a -> FM k a -> Bool
submap = FM k a -> FM k a -> Bool
forall a (m :: * -> *) k.
(Eq a, FiniteMapX m k) =>
m a -> m a -> Bool
A.submap
sameMap :: forall k a. (Eq k, Eq a) => FM k a -> FM k a -> Bool
sameMap = FM k a -> FM k a -> Bool
forall a (m :: * -> *) k.
(Eq a, FiniteMapX m k) =>
m a -> m a -> Bool
A.sameMap
unionWithKey :: forall k a.
Eq k =>
(k -> a -> a -> a) -> FM k a -> FM k a -> FM k a
unionWithKey = (k -> a -> a -> a) -> FM k a -> FM k a -> FM k a
forall (m :: * -> *) k a.
FiniteMap m k =>
(k -> a -> a -> a) -> m a -> m a -> m a
unionWithKeyUsingInsertWithKey
unionSeqWithKey :: forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(k -> a -> a -> a) -> seq (FM k a) -> FM k a
unionSeqWithKey = (k -> a -> a -> a) -> seq (FM k a) -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMap m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (m a) -> m a
unionSeqWithKeyUsingFoldr
intersectionWithKey :: forall k a b c.
Eq k =>
(k -> a -> b -> c) -> FM k a -> FM k b -> FM k c
intersectionWithKey = (k -> a -> b -> c) -> FM k a -> FM k b -> FM k c
forall (m :: * -> *) k a b c.
FiniteMap m k =>
(k -> a -> b -> c) -> m a -> m b -> m c
intersectionWithKeyUsingLookupM

-- instance declarations

instance Eq k  => A.AssocX (FM k) k where
  {empty :: forall a. FM k a
empty = FM k a
forall k a. Eq k => FM k a
empty; singleton :: forall a. k -> a -> FM k a
singleton = k -> a -> FM k a
forall k a. Eq k => k -> a -> FM k a
singleton; fromSeq :: forall (seq :: * -> *) a. Sequence seq => seq (k, a) -> FM k a
fromSeq = seq (k, a) -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq (k, a) -> FM k a
fromSeq; insert :: forall a. k -> a -> FM k a -> FM k a
insert = k -> a -> FM k a -> FM k a
forall k a. Eq k => k -> a -> FM k a -> FM k a
insert;
   insertSeq :: forall (seq :: * -> *) a.
Sequence seq =>
seq (k, a) -> FM k a -> FM k a
insertSeq = seq (k, a) -> FM k a -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq (k, a) -> FM k a -> FM k a
insertSeq; union :: forall a. FM k a -> FM k a -> FM k a
union = FM k a -> FM k a -> FM k a
forall k a. Eq k => FM k a -> FM k a -> FM k a
union; unionSeq :: forall (seq :: * -> *) a. Sequence seq => seq (FM k a) -> FM k a
unionSeq = seq (FM k a) -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq (FM k a) -> FM k a
unionSeq;
   delete :: forall a. k -> FM k a -> FM k a
delete = k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
delete; deleteAll :: forall a. k -> FM k a -> FM k a
deleteAll = k -> FM k a -> FM k a
forall k a. Eq k => k -> FM k a -> FM k a
deleteAll; deleteSeq :: forall (seq :: * -> *) a. Sequence seq => seq k -> FM k a -> FM k a
deleteSeq = seq k -> FM k a -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq k -> FM k a -> FM k a
deleteSeq;
   null :: forall a. FM k a -> Bool
null = FM k a -> Bool
forall k a. Eq k => FM k a -> Bool
null; size :: forall a. FM k a -> Int
size = FM k a -> Int
forall k a. Eq k => FM k a -> Int
size; member :: forall a. k -> FM k a -> Bool
member = k -> FM k a -> Bool
forall k a. Eq k => k -> FM k a -> Bool
member; count :: forall a. k -> FM k a -> Int
count = k -> FM k a -> Int
forall k a. Eq k => k -> FM k a -> Int
count;
   lookup :: forall a. k -> FM k a -> a
lookup = k -> FM k a -> a
forall k a. Eq k => k -> FM k a -> a
lookup; lookupM :: forall (rm :: * -> *) a. MonadFail rm => k -> FM k a -> rm a
lookupM = k -> FM k a -> rm a
forall k (rm :: * -> *) a.
(Eq k, MonadFail rm) =>
k -> FM k a -> rm a
lookupM; lookupAll :: forall (seq :: * -> *) a. Sequence seq => k -> FM k a -> seq a
lookupAll = k -> FM k a -> seq a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
k -> FM k a -> seq a
lookupAll;
   lookupAndDelete :: forall a. k -> FM k a -> (a, FM k a)
lookupAndDelete = k -> FM k a -> (a, FM k a)
forall k a. Eq k => k -> FM k a -> (a, FM k a)
lookupAndDelete; lookupAndDeleteM :: forall (rm :: * -> *) a.
MonadFail rm =>
k -> FM k a -> rm (a, FM k a)
lookupAndDeleteM = k -> FM k a -> rm (a, FM k a)
forall k (rm :: * -> *) a.
(Eq k, MonadFail rm) =>
k -> FM k a -> rm (a, FM k a)
lookupAndDeleteM;
   lookupAndDeleteAll :: forall (seq :: * -> *) a.
Sequence seq =>
k -> FM k a -> (seq a, FM k a)
lookupAndDeleteAll = k -> FM k a -> (seq a, FM k a)
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
k -> FM k a -> (seq a, FM k a)
lookupAndDeleteAll;
   lookupWithDefault :: forall a. a -> k -> FM k a -> a
lookupWithDefault = a -> k -> FM k a -> a
forall k a. Eq k => a -> k -> FM k a -> a
lookupWithDefault; adjust :: forall a. (a -> a) -> k -> FM k a -> FM k a
adjust = (a -> a) -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> a) -> k -> FM k a -> FM k a
adjust;
   adjustAll :: forall a. (a -> a) -> k -> FM k a -> FM k a
adjustAll = (a -> a) -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> a) -> k -> FM k a -> FM k a
adjustAll; adjustOrInsert :: forall a. (a -> a) -> a -> k -> FM k a -> FM k a
adjustOrInsert = (a -> a) -> a -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> a) -> a -> k -> FM k a -> FM k a
adjustOrInsert;
   adjustAllOrInsert :: forall a. (a -> a) -> a -> k -> FM k a -> FM k a
adjustAllOrInsert = (a -> a) -> a -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> a) -> a -> k -> FM k a -> FM k a
adjustAllOrInsert;
   adjustOrDelete :: forall a. (a -> Maybe a) -> k -> FM k a -> FM k a
adjustOrDelete = (a -> Maybe a) -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> Maybe a) -> k -> FM k a -> FM k a
adjustOrDelete; adjustOrDeleteAll :: forall a. (a -> Maybe a) -> k -> FM k a -> FM k a
adjustOrDeleteAll = (a -> Maybe a) -> k -> FM k a -> FM k a
forall k a. Eq k => (a -> Maybe a) -> k -> FM k a -> FM k a
adjustOrDeleteAll;
   fold :: forall a b. (a -> b -> b) -> b -> FM k a -> b
fold = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
fold; fold' :: forall a b. (a -> b -> b) -> b -> FM k a -> b
fold' = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (a -> b -> b) -> b -> FM k a -> b
fold'; fold1 :: forall a. (a -> a -> a) -> FM k a -> a
fold1 = (a -> a -> a) -> FM k a -> a
forall k a. Eq k => (a -> a -> a) -> FM k a -> a
fold1; fold1' :: forall a. (a -> a -> a) -> FM k a -> a
fold1' = (a -> a -> a) -> FM k a -> a
forall k a. Eq k => (a -> a -> a) -> FM k a -> a
fold1';
   filter :: forall a. (a -> Bool) -> FM k a -> FM k a
filter = (a -> Bool) -> FM k a -> FM k a
forall k a. Eq k => (a -> Bool) -> FM k a -> FM k a
filter; partition :: forall a. (a -> Bool) -> FM k a -> (FM k a, FM k a)
partition = (a -> Bool) -> FM k a -> (FM k a, FM k a)
forall k a. Eq k => (a -> Bool) -> FM k a -> (FM k a, FM k a)
partition; elements :: forall (seq :: * -> *) a. Sequence seq => FM k a -> seq a
elements = FM k a -> seq a
forall k (seq :: * -> *) a. (Eq k, Sequence seq) => FM k a -> seq a
elements;
   strict :: forall a. FM k a -> FM k a
strict = FM k a -> FM k a
forall k a. FM k a -> FM k a
strict; strictWith :: forall a b. (a -> b) -> FM k a -> FM k a
strictWith = (a -> b) -> FM k a -> FM k a
forall a b k. (a -> b) -> FM k a -> FM k a
strictWith;
   structuralInvariant :: forall a. FM k a -> Bool
structuralInvariant = FM k a -> Bool
forall k a. Eq k => FM k a -> Bool
structuralInvariant; instanceName :: forall a. FM k a -> String
instanceName FM k a
_ = String
moduleName}

instance Ord k => A.OrdAssocX (FM k) k where
  {minView :: forall (rm :: * -> *) a. MonadFail rm => FM k a -> rm (a, FM k a)
minView = FM k a -> rm (a, FM k a)
forall k (m :: * -> *) a.
(Ord k, MonadFail m) =>
FM k a -> m (a, FM k a)
minView; minElem :: forall a. FM k a -> a
minElem = FM k a -> a
forall k a. Ord k => FM k a -> a
minElem; deleteMin :: forall a. FM k a -> FM k a
deleteMin = FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
deleteMin;
   unsafeInsertMin :: forall a. k -> a -> FM k a -> FM k a
unsafeInsertMin = k -> a -> FM k a -> FM k a
forall k a. Ord k => k -> a -> FM k a -> FM k a
unsafeInsertMin; maxView :: forall (rm :: * -> *) a. MonadFail rm => FM k a -> rm (a, FM k a)
maxView = FM k a -> rm (a, FM k a)
forall k (m :: * -> *) a.
(Ord k, MonadFail m) =>
FM k a -> m (a, FM k a)
maxView; maxElem :: forall a. FM k a -> a
maxElem = FM k a -> a
forall k a. Ord k => FM k a -> a
maxElem;
   deleteMax :: forall a. FM k a -> FM k a
deleteMax = FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1
deleteMax; unsafeInsertMax :: forall a. k -> a -> FM k a -> FM k a
unsafeInsertMax = k -> a -> FM k a -> FM k a
forall k a. Ord k => k -> a -> FM k a -> FM k a
unsafeInsertMax;
   foldr :: forall a b. (a -> b -> b) -> b -> FM k a -> b
foldr = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr; foldr' :: forall a b. (a -> b -> b) -> b -> FM k a -> b
foldr' = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr'; foldl :: forall b a. (b -> a -> b) -> b -> FM k a -> b
foldl = (b -> a -> b) -> b -> FM k a -> b
forall k b a. Ord k => (b -> a -> b) -> b -> FM k a -> b
foldl; foldl' :: forall b a. (b -> a -> b) -> b -> FM k a -> b
foldl' = (b -> a -> b) -> b -> FM k a -> b
forall k b a. Ord k => (b -> a -> b) -> b -> FM k a -> b
foldl';
   foldr1 :: forall a. (a -> a -> a) -> FM k a -> a
foldr1 = (a -> a -> a) -> FM k a -> a
forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldr1; foldr1' :: forall a. (a -> a -> a) -> FM k a -> a
foldr1' = (a -> a -> a) -> FM k a -> a
forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldr1'; foldl1 :: forall a. (a -> a -> a) -> FM k a -> a
foldl1 = (a -> a -> a) -> FM k a -> a
forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldl1; foldl1' :: forall a. (a -> a -> a) -> FM k a -> a
foldl1' = (a -> a -> a) -> FM k a -> a
forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldl1';
   unsafeFromOrdSeq :: forall (seq :: * -> *) a. Sequence seq => seq (k, a) -> FM k a
unsafeFromOrdSeq = seq (k, a) -> FM k a
forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
seq (k, a) -> FM k a
unsafeFromOrdSeq; unsafeAppend :: forall a. FM k a -> FM k a -> FM k a
unsafeAppend = FM k a -> FM k a -> FM k a
forall t t1. Ord t => FM t t1 -> FM t t1 -> FM t t1
unsafeAppend;
   filterLT :: forall a. k -> FM k a -> FM k a
filterLT = k -> FM k a -> FM k a
forall k a. Ord k => k -> FM k a -> FM k a
filterLT; filterGT :: forall a. k -> FM k a -> FM k a
filterGT = k -> FM k a -> FM k a
forall k a. Ord k => k -> FM k a -> FM k a
filterGT; filterLE :: forall a. k -> FM k a -> FM k a
filterLE = k -> FM k a -> FM k a
forall k a. Ord k => k -> FM k a -> FM k a
filterLE;
   filterGE :: forall a. k -> FM k a -> FM k a
filterGE = k -> FM k a -> FM k a
forall k a. Ord k => k -> FM k a -> FM k a
filterGE; partitionLT_GE :: forall a. k -> FM k a -> (FM k a, FM k a)
partitionLT_GE = k -> FM k a -> (FM k a, FM k a)
forall k a. Ord k => k -> FM k a -> (FM k a, FM k a)
partitionLT_GE;
   partitionLE_GT :: forall a. k -> FM k a -> (FM k a, FM k a)
partitionLE_GT = k -> FM k a -> (FM k a, FM k a)
forall k a. Ord k => k -> FM k a -> (FM k a, FM k a)
partitionLE_GT; partitionLT_GT :: forall a. k -> FM k a -> (FM k a, FM k a)
partitionLT_GT = k -> FM k a -> (FM k a, FM k a)
forall k a. Ord k => k -> FM k a -> (FM k a, FM k a)
partitionLT_GT}

instance Eq k => A.FiniteMapX (FM k) k where
  {fromSeqWith :: forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (k, a) -> FM k a
fromSeqWith = (a -> a -> a) -> seq (k, a) -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> FM k a
fromSeqWith; fromSeqWithKey :: forall (seq :: * -> *) a.
Sequence seq =>
(k -> a -> a -> a) -> seq (k, a) -> FM k a
fromSeqWithKey = (k -> a -> a -> a) -> seq (k, a) -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> FM k a
fromSeqWithKey;
   insertWith :: forall a. (a -> a -> a) -> k -> a -> FM k a -> FM k a
insertWith  = (a -> a -> a) -> k -> a -> FM k a -> FM k a
forall k a. Eq k => (a -> a -> a) -> k -> a -> FM k a -> FM k a
insertWith; insertWithKey :: forall a. (k -> a -> a -> a) -> k -> a -> FM k a -> FM k a
insertWithKey = (k -> a -> a -> a) -> k -> a -> FM k a -> FM k a
forall k a.
Eq k =>
(k -> a -> a -> a) -> k -> a -> FM k a -> FM k a
insertWithKey;
   insertSeqWith :: forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
insertSeqWith = (a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
insertSeqWith; insertSeqWithKey :: forall (seq :: * -> *) a.
Sequence seq =>
(k -> a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
insertSeqWithKey = (k -> a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> FM k a -> FM k a
insertSeqWithKey;
   unionl :: forall a. FM k a -> FM k a -> FM k a
unionl = FM k a -> FM k a -> FM k a
forall k a. Eq k => FM k a -> FM k a -> FM k a
unionl; unionr :: forall a. FM k a -> FM k a -> FM k a
unionr = FM k a -> FM k a -> FM k a
forall k a. Eq k => FM k a -> FM k a -> FM k a
unionr; unionWith :: forall a. (a -> a -> a) -> FM k a -> FM k a -> FM k a
unionWith = (a -> a -> a) -> FM k a -> FM k a -> FM k a
forall k a. Eq k => (a -> a -> a) -> FM k a -> FM k a -> FM k a
unionWith;
   unionSeqWith :: forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (FM k a) -> FM k a
unionSeqWith = (a -> a -> a) -> seq (FM k a) -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(a -> a -> a) -> seq (FM k a) -> FM k a
unionSeqWith; intersectionWith :: forall a b c. (a -> b -> c) -> FM k a -> FM k b -> FM k c
intersectionWith = (a -> b -> c) -> FM k a -> FM k b -> FM k c
forall k a b c. Eq k => (a -> b -> c) -> FM k a -> FM k b -> FM k c
intersectionWith;
   difference :: forall a b. FM k a -> FM k b -> FM k a
difference = FM k a -> FM k b -> FM k a
forall k a b. Eq k => FM k a -> FM k b -> FM k a
difference; properSubset :: forall a b. FM k a -> FM k b -> Bool
properSubset = FM k a -> FM k b -> Bool
forall k a b. Eq k => FM k a -> FM k b -> Bool
properSubset; subset :: forall a b. FM k a -> FM k b -> Bool
subset = FM k a -> FM k b -> Bool
forall k a b. Eq k => FM k a -> FM k b -> Bool
subset;
   properSubmapBy :: forall a. (a -> a -> Bool) -> FM k a -> FM k a -> Bool
properSubmapBy = (a -> a -> Bool) -> FM k a -> FM k a -> Bool
forall k a. Eq k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
properSubmapBy; submapBy :: forall a. (a -> a -> Bool) -> FM k a -> FM k a -> Bool
submapBy = (a -> a -> Bool) -> FM k a -> FM k a -> Bool
forall k a. Eq k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
submapBy;
   sameMapBy :: forall a. (a -> a -> Bool) -> FM k a -> FM k a -> Bool
sameMapBy = (a -> a -> Bool) -> FM k a -> FM k a -> Bool
forall k a. Eq k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
sameMapBy}

instance Ord k => A.OrdFiniteMapX (FM k) k

instance Eq k  => A.Assoc (FM k) k where
  {toSeq :: forall (seq :: * -> *) a. Sequence seq => FM k a -> seq (k, a)
toSeq = FM k a -> seq (k, a)
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
FM k a -> seq (k, a)
toSeq; keys :: forall (seq :: * -> *) a. Sequence seq => FM k a -> seq k
keys = FM k a -> seq k
forall k (seq :: * -> *) a. (Eq k, Sequence seq) => FM k a -> seq k
keys; mapWithKey :: forall a b. (k -> a -> b) -> FM k a -> FM k b
mapWithKey = (k -> a -> b) -> FM k a -> FM k b
forall k a b. Eq k => (k -> a -> b) -> FM k a -> FM k b
mapWithKey;
   foldWithKey :: forall a b. (k -> a -> b -> b) -> b -> FM k a -> b
foldWithKey = (k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldWithKey; foldWithKey' :: forall a b. (k -> a -> b -> b) -> b -> FM k a -> b
foldWithKey' = (k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Eq k => (k -> a -> b -> b) -> b -> FM k a -> b
foldWithKey';
   filterWithKey :: forall a. (k -> a -> Bool) -> FM k a -> FM k a
filterWithKey = (k -> a -> Bool) -> FM k a -> FM k a
forall k a. Eq k => (k -> a -> Bool) -> FM k a -> FM k a
filterWithKey;
   partitionWithKey :: forall a. (k -> a -> Bool) -> FM k a -> (FM k a, FM k a)
partitionWithKey = (k -> a -> Bool) -> FM k a -> (FM k a, FM k a)
forall k a. Eq k => (k -> a -> Bool) -> FM k a -> (FM k a, FM k a)
partitionWithKey}

instance Ord k => A.OrdAssoc (FM k) k where
  {minViewWithKey :: forall (rm :: * -> *) a.
MonadFail rm =>
FM k a -> rm ((k, a), FM k a)
minViewWithKey = FM k a -> rm ((k, a), FM k a)
forall k (m :: * -> *) a.
(Ord k, MonadFail m) =>
FM k a -> m ((k, a), FM k a)
minViewWithKey; minElemWithKey :: forall a. FM k a -> (k, a)
minElemWithKey = FM k a -> (k, a)
forall k a. Ord k => FM k a -> (k, a)
minElemWithKey;
   maxViewWithKey :: forall (rm :: * -> *) a.
MonadFail rm =>
FM k a -> rm ((k, a), FM k a)
maxViewWithKey = FM k a -> rm ((k, a), FM k a)
forall k (m :: * -> *) a.
(Ord k, MonadFail m) =>
FM k a -> m ((k, a), FM k a)
maxViewWithKey; maxElemWithKey :: forall a. FM k a -> (k, a)
maxElemWithKey = FM k a -> (k, a)
forall k a. Ord k => FM k a -> (k, a)
maxElemWithKey;
   foldrWithKey :: forall a b. (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey = (k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Ord k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey; foldrWithKey' :: forall a b. (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey' = (k -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Ord k => (k -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey';
   foldlWithKey :: forall b a. (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKey = (b -> k -> a -> b) -> b -> FM k a -> b
forall k b a. Ord k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKey; foldlWithKey' :: forall b a. (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKey' = (b -> k -> a -> b) -> b -> FM k a -> b
forall k b a. Ord k => (b -> k -> a -> b) -> b -> FM k a -> b
foldlWithKey';
   toOrdSeq :: forall (seq :: * -> *) a. Sequence seq => FM k a -> seq (k, a)
toOrdSeq = FM k a -> seq (k, a)
forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
FM k a -> seq (k, a)
toOrdSeq}

instance Eq k => A.FiniteMap (FM k) k where
  {unionWithKey :: forall a. (k -> a -> a -> a) -> FM k a -> FM k a -> FM k a
unionWithKey = (k -> a -> a -> a) -> FM k a -> FM k a -> FM k a
forall k a.
Eq k =>
(k -> a -> a -> a) -> FM k a -> FM k a -> FM k a
unionWithKey; unionSeqWithKey :: forall (seq :: * -> *) a.
Sequence seq =>
(k -> a -> a -> a) -> seq (FM k a) -> FM k a
unionSeqWithKey = (k -> a -> a -> a) -> seq (FM k a) -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
(k -> a -> a -> a) -> seq (FM k a) -> FM k a
unionSeqWithKey;
   intersectionWithKey :: forall a b c. (k -> a -> b -> c) -> FM k a -> FM k b -> FM k c
intersectionWithKey = (k -> a -> b -> c) -> FM k a -> FM k b -> FM k c
forall k a b c.
Eq k =>
(k -> a -> b -> c) -> FM k a -> FM k b -> FM k c
intersectionWithKey}

instance Ord k => A.OrdFiniteMap (FM k) k

instance Eq k => Functor (FM k) where
  fmap :: forall a b. (a -> b) -> FM k a -> FM k b
fmap =  (a -> b) -> FM k a -> FM k b
forall k a b. Eq k => (a -> b) -> FM k a -> FM k b
map

instance (Eq k,Eq a) => Eq (FM k a) where
  == :: FM k a -> FM k a -> Bool
(==) = FM k a -> FM k a -> Bool
forall k a. (Eq k, Eq a) => FM k a -> FM k a -> Bool
sameMap

instance (Ord k, Ord a) => Ord (FM k a) where
  compare :: FM k a -> FM k a -> Ordering
compare = FM k a -> FM k a -> Ordering
forall a (m :: * -> *) k.
(Ord a, OrdAssoc m k) =>
m a -> m a -> Ordering
compareUsingToOrdList

instance (Eq k,Show k,Show a) => Show (FM k a) where
  showsPrec :: Int -> FM k a -> String -> String
showsPrec = Int -> FM k a -> String -> String
forall k a (m :: * -> *).
(Show k, Show a, Assoc m k) =>
Int -> m a -> String -> String
showsPrecUsingToList

instance (Eq k,Read k,Read a) => Read (FM k a) where
  readsPrec :: Int -> ReadS (FM k a)
readsPrec = Int -> ReadS (FM k a)
forall k a (m :: * -> *).
(Read k, Read a, AssocX m k) =>
Int -> ReadS (m a)
readsPrecUsingFromList

instance (Eq k,Arbitrary k,Arbitrary a) => Arbitrary (FM k a) where
   arbitrary :: Gen (FM k a)
arbitrary = do ([(k, a)]
xs::[(k,a)]) <- Gen [(k, a)]
forall a. Arbitrary a => Gen a
arbitrary
                  FM k a -> Gen (FM k a)
forall a. a -> Gen a
forall (m :: * -> *) a. Monad m => a -> m a
return (((k, a) -> FM k a -> FM k a) -> FM k a -> [(k, a)] -> FM k a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr ((k -> a -> FM k a -> FM k a) -> (k, a) -> FM k a -> FM k a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> a -> FM k a -> FM k a
forall k a. Eq k => k -> a -> FM k a -> FM k a
insert) FM k a
forall k a. Eq k => FM k a
empty [(k, a)]
xs)

instance (Eq k,CoArbitrary k,CoArbitrary a) => CoArbitrary (FM k a) where
   coarbitrary :: forall b. FM k a -> Gen b -> Gen b
coarbitrary FM k a
E = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
   coarbitrary (I k
k a
a FM k a
m) = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
1 (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. k -> Gen b -> Gen b
forall b. k -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary k
k
                         (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Gen b -> Gen b
forall b. a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary a
a (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM k a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
forall b. FM k a -> Gen b -> Gen b
coarbitrary FM k a
m


instance Eq k => Semigroup (FM k a) where
   <> :: FM k a -> FM k a -> FM k a
(<>) = FM k a -> FM k a -> FM k a
forall k a. Eq k => FM k a -> FM k a -> FM k a
union
instance Eq k => Monoid (FM k a) where
   mempty :: FM k a
mempty  = FM k a
forall k a. Eq k => FM k a
empty
   mappend :: FM k a -> FM k a -> FM k a
mappend = FM k a -> FM k a -> FM k a
forall a. Semigroup a => a -> a -> a
(SG.<>)
   mconcat :: [FM k a] -> FM k a
mconcat = [FM k a] -> FM k a
forall k (seq :: * -> *) a.
(Eq k, Sequence seq) =>
seq (FM k a) -> FM k a
unionSeq