-- File created: 2008-11-11 11:24:30

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

#include "exports.h"

-- | The base implementation of a trie representing a map with list keys,
-- generalized over any type of map from element values to tries.
--
-- Worst-case complexities are given in terms of @n@, @m@, and @s@. @n@ refers
-- to the number of keys in the map and @m@ to their maximum length. @s@ refers
-- to the length of a key given to the function, not any property of the map.
--
-- In addition, the trie's branching factor plays a part in almost every
-- operation, but the complexity depends on the underlying 'Map'. Thus, for
-- instance, 'member' is actually @O(m f(b))@ where @f(b)@ is the complexity of
-- a lookup operation on the 'Map' used. This complexity depends on the
-- underlying operation, which is not part of the specification of the visible
-- function. Thus it could change whilst affecting the complexity only for
-- certain Map types: hence this \"b factor\" is not shown explicitly.
--
-- Disclaimer: the complexities have not been proven.
--
-- Strict versions of functions are provided for those who want to be certain
-- that their 'TrieMap' doesn't contain values consisting of unevaluated
-- thunks. Note, however, that they do not evaluate the whole trie strictly,
-- only the values. And only to one level of depth: for instance, 'alter'' does
-- not 'seq' the value within the 'Maybe', only the 'Maybe' itself. The user
-- should add the strictness in such cases himself, if he so wishes.
--
-- Many functions come in both ordinary and @WithKey@ forms, where the former
-- takes a function of type @a -> b@ and the latter of type @[k] -> a -> b@,
-- where @[k]@ is the key associated with the value @a@. For most of these
-- functions, there is additional overhead involved in keeping track of the
-- key: don't use the latter form of the function unless you need it.
module Data.ListTrie.Map (MAP_EXPORTS) where

import Control.Arrow       ((***), second)
import Control.Monad       (liftM2)
import Data.Binary         (Binary,get,put)
import qualified Data.DList as DL
import Data.Either         (partitionEithers)
import Data.Function       (on)
import qualified Data.Foldable as F
import qualified Data.List.NonEmpty as NE
import qualified Data.Maybe as Maybe
import Data.Semigroup      (Semigroup(..), stimesIdempotent)
import Prelude hiding      (filter, foldl, foldl', foldr, lookup, map, null)
import qualified Prelude

#if __GLASGOW_HASKELL__
import Text.Read (readPrec, lexP, parens, prec, Lexeme(Ident))
#endif

import qualified Data.ListTrie.Base     as Base
import qualified Data.ListTrie.Base.Map as Map
import Data.ListTrie.Base.Classes (fmap')
import Data.ListTrie.Base.Map     (Map, OrdMap)

#include "docs.h"

-- Invariant: any (Tr Nothing _) has a Just descendant.
--
-- | The data structure itself: a map from keys of type @[k]@ to values of type
-- @v@ implemented as a trie, using @map@ to map keys of type @k@ to sub-tries.
--
-- Regarding the instances:
--
-- - The @Trie@ class is internal, ignore it.
--
-- - The 'Eq' constraint for the 'Ord' instance is misleading: it is needed
--   only because 'Eq' is a superclass of 'Ord'.
--
-- - The 'Foldable' and 'Traversable' instances allow folding over and
--   traversing only the values, not the keys.
--
-- - The 'Monoid' instance defines 'mappend' as 'union' and 'mempty' as
--   'empty'.
data TrieMap map k v = Tr (Maybe v) !(CMap map k v)

type CMap map k v = map k (TrieMap map k v)

instance Map map k => Base.Trie TrieMap Maybe map k where
   mkTrie :: forall a. Maybe a -> CMap TrieMap map k a -> TrieMap map k a
mkTrie = Maybe a -> CMap map k a -> TrieMap map k a
forall (map :: * -> * -> *) k v.
Maybe v -> CMap map k v -> TrieMap map k v
Tr
   tParts :: forall a. TrieMap map k a -> (Maybe a, CMap TrieMap map k a)
tParts (Tr Maybe a
v CMap map k a
m) = (Maybe a
v,CMap map k a
m)

-- Don't use CMap in these instances since Haddock won't expand it
instance (Eq (map k (TrieMap map k a)), Eq a) => Eq (TrieMap map k a) where
   Tr Maybe a
v1 map k (TrieMap map k a)
m1 == :: TrieMap map k a -> TrieMap map k a -> Bool
== Tr Maybe a
v2 map k (TrieMap map k a)
m2 = Maybe a
v1 Maybe a -> Maybe a -> Bool
forall a. Eq a => a -> a -> Bool
== Maybe a
v2 Bool -> Bool -> Bool
&& map k (TrieMap map k a)
m1 map k (TrieMap map k a) -> map k (TrieMap map k a) -> Bool
forall a. Eq a => a -> a -> Bool
== map k (TrieMap map k a)
m2

-- Eq constraint only needed because of superclassness... sigh
instance (Eq (map k (TrieMap map k a)), OrdMap map k, Ord k, Ord a)
      => Ord (TrieMap map k a)
 where
   compare :: TrieMap map k a -> TrieMap map k a -> Ordering
compare = [([k], a)] -> [([k], a)] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ([([k], a)] -> [([k], a)] -> Ordering)
-> (TrieMap map k a -> [([k], a)])
-> TrieMap map k a
-> TrieMap map k a
-> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` TrieMap map k a -> [([k], a)]
forall (map :: * -> * -> *) k a.
OrdMap map k =>
TrieMap map k a -> [([k], a)]
toAscList

instance Map map k => Semigroup (TrieMap map k a) where
   <> :: TrieMap map k a -> TrieMap map k a -> TrieMap map k a
(<>) = TrieMap map k a -> TrieMap map k a -> TrieMap map k a
forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> TrieMap map k a -> TrieMap map k a
union
   sconcat :: NonEmpty (TrieMap map k a) -> TrieMap map k a
sconcat = [TrieMap map k a] -> TrieMap map k a
forall (map :: * -> * -> *) k a.
Map map k =>
[TrieMap map k a] -> TrieMap map k a
unions ([TrieMap map k a] -> TrieMap map k a)
-> (NonEmpty (TrieMap map k a) -> [TrieMap map k a])
-> NonEmpty (TrieMap map k a)
-> TrieMap map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty (TrieMap map k a) -> [TrieMap map k a]
forall a. NonEmpty a -> [a]
NE.toList
   stimes :: forall b. Integral b => b -> TrieMap map k a -> TrieMap map k a
stimes = b -> TrieMap map k a -> TrieMap map k a
forall b a. Integral b => b -> a -> a
stimesIdempotent

instance Map map k => Monoid (TrieMap map k a) where
   mempty :: TrieMap map k a
mempty  = TrieMap map k a
forall (map :: * -> * -> *) k a. Map map k => TrieMap map k a
empty
   mappend :: TrieMap map k a -> TrieMap map k a -> TrieMap map k a
mappend = TrieMap map k a -> TrieMap map k a -> TrieMap map k a
forall a. Semigroup a => a -> a -> a
(<>)
   mconcat :: [TrieMap map k a] -> TrieMap map k a
mconcat = [TrieMap map k a] -> TrieMap map k a
forall (map :: * -> * -> *) k a.
Map map k =>
[TrieMap map k a] -> TrieMap map k a
unions

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

instance Map map k => F.Foldable (TrieMap map k) where
   foldl :: forall b a. (b -> a -> b) -> b -> TrieMap map k a -> b
foldl = (a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldl ((a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((b -> a -> b) -> a -> b -> b)
-> (b -> a -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> a -> b) -> a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip
   foldr :: forall a b. (a -> b -> b) -> b -> TrieMap map k a -> b
foldr = (a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldr

instance (Map map k, Traversable (map k)) => Traversable (TrieMap map k) where
   traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> TrieMap map k a -> f (TrieMap map k b)
traverse a -> f b
f (Tr Maybe a
v CMap map k a
m) = Maybe b -> CMap map k b -> TrieMap map k b
forall (map :: * -> * -> *) k v.
Maybe v -> CMap map k v -> TrieMap map k v
Tr (Maybe b -> CMap map k b -> TrieMap map k b)
-> f (Maybe b) -> f (CMap map k b -> TrieMap map k b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> Maybe a -> f (Maybe b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Maybe a -> f (Maybe b)
traverse a -> f b
f Maybe a
v f (CMap map k b -> TrieMap map k b)
-> f (CMap map k b) -> f (TrieMap map k b)
forall a b. f (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (TrieMap map k a -> f (TrieMap map k b))
-> CMap map k a -> f (CMap map k b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> map k a -> f (map k b)
traverse ((a -> f b) -> TrieMap map k a -> f (TrieMap map k b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> TrieMap map k a -> f (TrieMap map k b)
traverse a -> f b
f) CMap map k a
m

instance (Map map k, Show k, Show a) => Show (TrieMap map k a) where
   showsPrec :: Int -> TrieMap map k a -> ShowS
showsPrec Int
p TrieMap map k a
s = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
      String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [([k], a)] -> ShowS
forall a. Show a => a -> ShowS
shows (TrieMap map k a -> [([k], a)]
forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> [([k], a)]
toList TrieMap map k a
s)

instance (Map map k, Read k, Read a) => Read (TrieMap map k a) where
#if __GLASGOW_HASKELL__
   readPrec :: ReadPrec (TrieMap map k a)
readPrec = ReadPrec (TrieMap map k a) -> ReadPrec (TrieMap map k a)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (TrieMap map k a) -> ReadPrec (TrieMap map k a))
-> ReadPrec (TrieMap map k a) -> ReadPrec (TrieMap map k a)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (TrieMap map k a) -> ReadPrec (TrieMap map k a)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (TrieMap map k a) -> ReadPrec (TrieMap map k a))
-> ReadPrec (TrieMap map k a) -> ReadPrec (TrieMap map k a)
forall a b. (a -> b) -> a -> b
$ do
      Ident String
"fromList" <- ReadPrec Lexeme
lexP
      ([([k], a)] -> TrieMap map k a)
-> ReadPrec [([k], a)] -> ReadPrec (TrieMap map k a)
forall a b. (a -> b) -> ReadPrec a -> ReadPrec b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [([k], a)] -> TrieMap map k a
forall (map :: * -> * -> *) k a.
Map map k =>
[([k], a)] -> TrieMap map k a
fromList ReadPrec [([k], a)]
forall a. Read a => ReadPrec a
readPrec
#else
   readsPrec p = readParen (p > 10) $ \r -> do
      ("fromList", list) <- lex r
      (xs, rest) <- readsPrec (p+1) list
      [(fromList xs, rest)]
#endif

instance (Map map k, Binary k, Binary a) => Binary (TrieMap map k a) where
   put :: TrieMap map k a -> Put
put (Tr Maybe a
v CMap map k a
m) = Maybe a -> Put
forall t. Binary t => t -> Put
put Maybe a
v Put -> Put -> Put
forall a b. PutM a -> PutM b -> PutM b
forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> ([(k, TrieMap map k a)] -> Put
forall t. Binary t => t -> Put
put ([(k, TrieMap map k a)] -> Put)
-> (CMap map k a -> [(k, TrieMap map k a)]) -> CMap map k a -> Put
forall b c a. (b -> c) -> (a -> b) -> a -> c
. CMap map k a -> [(k, TrieMap map k a)]
forall a. map k a -> [(k, a)]
forall (m :: * -> * -> *) k a. Map m k => m k a -> [(k, a)]
Map.serializeToList (CMap map k a -> Put) -> CMap map k a -> Put
forall a b. (a -> b) -> a -> b
$ CMap map k a
m)
   get :: Get (TrieMap map k a)
get = (Maybe a -> CMap map k a -> TrieMap map k a)
-> Get (Maybe a) -> Get (CMap map k a) -> Get (TrieMap map k a)
forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 Maybe a -> CMap map k a -> TrieMap map k a
forall (map :: * -> * -> *) k v.
Maybe v -> CMap map k v -> TrieMap map k v
Tr Get (Maybe a)
forall t. Binary t => Get t
get (Get [(k, TrieMap map k a)]
forall t. Binary t => Get t
get Get [(k, TrieMap map k a)]
-> ([(k, TrieMap map k a)] -> Get (CMap map k a))
-> Get (CMap map k a)
forall a b. Get a -> (a -> Get b) -> Get b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= CMap map k a -> Get (CMap map k a)
forall a. a -> Get a
forall (m :: * -> *) a. Monad m => a -> m a
return (CMap map k a -> Get (CMap map k a))
-> ([(k, TrieMap map k a)] -> CMap map k a)
-> [(k, TrieMap map k a)]
-> Get (CMap map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, TrieMap map k a)] -> CMap map k a
forall a. [(k, a)] -> map k a
forall (m :: * -> * -> *) k a. Map m k => [(k, a)] -> m k a
Map.deserializeFromList)

-- * Construction

-- | @O(1)@. The empty map.
empty :: Map map k => TrieMap map k a
empty :: forall (map :: * -> * -> *) k a. Map map k => TrieMap map k a
empty = TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a
Base.empty

-- | @O(s)@. The singleton map containing only the given key-value pair.
singleton :: Map map k => [k] -> a -> TrieMap map k a
singleton :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> a -> TrieMap map k a
singleton = [k] -> a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> a -> trie map k a
Base.singleton

-- * Modification

-- | @O(min(m,s))@. Inserts the key-value pair into the map. If the key is
-- already a member of the map, the given value replaces the old one.
insert :: Map map k => [k] -> a -> TrieMap map k a -> TrieMap map k a
insert :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> a -> TrieMap map k a -> TrieMap map k a
insert = [k] -> a -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> a -> trie map k a -> trie map k a
Base.insert

-- | @O(min(m,s))@. Inserts the key-value pair into the map. If the key is
-- already a member of the map, the given value replaces the old one.
insert' :: Map map k => [k] -> a -> TrieMap map k a -> TrieMap map k a
insert' :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> a -> TrieMap map k a -> TrieMap map k a
insert' = [k] -> a -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> a -> trie map k a -> trie map k a
Base.insert'

-- | @O(min(m,s))@. Inserts the key-value pair into the map. If the key is
-- already a member of the map, the old value is replaced by @f givenValue
-- oldValue@ where @f@ is the given function.
insertWith :: Map map k
           => (a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k a
insertWith :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k a
insertWith = (a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
Base.insertWith

-- | @O(min(m,s))@. Like 'insertWith', but the new value is reduced to weak
-- head normal form before being placed into the map, whether it is the given
-- value or a result of the combining function.
insertWith' :: Map map k
            => (a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k a
insertWith' :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k a
insertWith' = (a -> a -> a) -> [k] -> a -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> a -> a) -> [k] -> a -> trie map k a -> trie map k a
Base.insertWith'

-- | @O(min(m,s))@. Removes the key from the map along with its associated
-- value. If the key is not a member of the map, the map is unchanged.
delete :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a
delete :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> TrieMap map k a -> TrieMap map k a
delete = [k] -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
Base.delete

-- | @O(min(m,s))@. Adjusts the value at the given key by calling the given
-- function on it. If the key is not a member of the map, the map is unchanged.
adjust :: Map map k => (a -> a) -> [k] -> TrieMap map k a -> TrieMap map k a
adjust :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a) -> [k] -> TrieMap map k a -> TrieMap map k a
adjust = (a -> a) -> [k] -> TrieMap map k a -> TrieMap map k a
forall (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) k a.
Trie trie st map k =>
(a -> a) -> [k] -> trie map k a -> trie map k a
Base.adjust

-- | @O(min(m,s))@. Like 'adjust', but the function is applied strictly.
adjust' :: Map map k => (a -> a) -> [k] -> TrieMap map k a -> TrieMap map k a
adjust' :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a) -> [k] -> TrieMap map k a -> TrieMap map k a
adjust' = (a -> a) -> [k] -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> a) -> [k] -> trie map k a -> trie map k a
Base.adjust'

-- | @O(min(m,s))@. Updates the value at the given key: if the given
-- function returns 'Nothing', the value and its associated key are removed; if
-- 'Just'@ a@ is returned, the old value is replaced with @a@. If the key is
-- not a member of the map, the map is unchanged.
update :: Map map k
       => (a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
update :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
update a -> Maybe a
f [k]
k = (Maybe a, TrieMap map k a) -> TrieMap map k a
forall a b. (a, b) -> b
snd ((Maybe a, TrieMap map k a) -> TrieMap map k a)
-> (TrieMap map k a -> (Maybe a, TrieMap map k a))
-> TrieMap map k a
-> TrieMap map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe a)
-> [k] -> TrieMap map k a -> (Maybe a, TrieMap map k a)
forall (map :: * -> * -> *) k a.
Map map k =>
(a -> Maybe a)
-> [k] -> TrieMap map k a -> (Maybe a, TrieMap map k a)
updateLookup a -> Maybe a
f [k]
k

-- | @O(min(m,s))@. Like 'update', but also returns 'Just' the original value,
-- or 'Nothing' if the key is not a member of the map.
updateLookup :: Map map k => (a -> Maybe a)
                          -> [k]
                          -> TrieMap map k a
                          -> (Maybe a, TrieMap map k a)
updateLookup :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> Maybe a)
-> [k] -> TrieMap map k a -> (Maybe a, TrieMap map k a)
updateLookup = (a -> Maybe a)
-> [k] -> TrieMap map k a -> (Maybe a, TrieMap map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> st a) -> [k] -> trie map k a -> (st a, trie map k a)
Base.updateLookup

-- | @O(min(m,s))@. The most general modification function, allowing you to
-- modify the value at the given key, whether or not it is a member of the map.
-- In short: the given function is passed 'Just' the value at the key if it is
-- present, or 'Nothing' otherwise; if the function returns 'Just' a value, the
-- new value is inserted into the map, otherwise the old value is removed. More
-- precisely, for @alter f k m@:
--
-- If @k@ is a member of @m@, @f (@'Just'@ oldValue)@ is called. Now:
--
-- - If @f@ returned 'Just'@ newValue@, @oldValue@ is replaced with @newValue@.
--
-- - If @f@ returned 'Nothing', @k@ and @oldValue@ are removed from the map.
--
-- If, instead, @k@ is not a member of @m@, @f @'Nothing' is called, and:
--
-- - If @f@ returned 'Just'@ value@, @value@ is inserted into the map, at @k@.
--
-- - If @f@ returned 'Nothing', the map is unchanged.
--
-- The function is applied lazily only if the given key is a prefix of another
-- key in the map.
alter :: Map map k
      => (Maybe a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
alter :: forall (map :: * -> * -> *) k a.
Map map k =>
(Maybe a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
alter = (Maybe a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(st a -> st a) -> [k] -> trie map k a -> trie map k a
Base.alter

-- | @O(min(m,s))@. Like 'alter', but the function is always applied strictly.
alter' :: Map map k
       => (Maybe a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
alter' :: forall (map :: * -> * -> *) k a.
Map map k =>
(Maybe a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
alter' = (Maybe a -> Maybe a) -> [k] -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(st a -> st a) -> [k] -> trie map k a -> trie map k a
Base.alter'

-- * Querying

-- | @O(1)@. 'True' iff the map is empty.
null :: Map map k => TrieMap map k a -> Bool
null :: forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> Bool
null = TrieMap map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> Bool
Base.null

-- | @O(n m)@. The number of elements in the map. The value is built up lazily,
-- allowing for delivery of partial results without traversing the whole map.
size :: (Map map k, Num n) => TrieMap map k a -> n
size :: forall (map :: * -> * -> *) k n a.
(Map map k, Num n) =>
TrieMap map k a -> n
size = TrieMap map k a -> n
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k n.
(Boolable (st a), Trie trie st map k, Num n) =>
trie map k a -> n
Base.size

-- | @O(n m)@. The number of elements in the map. The value is built strictly:
-- no value is returned until the map has been fully traversed.
size' :: (Map map k, Num n) => TrieMap map k a -> n
size' :: forall (map :: * -> * -> *) k n a.
(Map map k, Num n) =>
TrieMap map k a -> n
size' = TrieMap map k a -> n
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k n.
(Boolable (st a), Trie trie st map k, Num n) =>
trie map k a -> n
Base.size'

-- | @O(min(m,s))@. 'True' iff the given key is associated with a value in the
-- map.
member :: Map map k => [k] -> TrieMap map k a -> Bool
member :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> TrieMap map k a -> Bool
member = [k] -> TrieMap map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> Bool
Base.member

-- | @O(min(m,s))@. 'False' iff the given key is associated with a value in the
-- map.
notMember :: Map map k => [k] -> TrieMap map k a -> Bool
notMember :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> TrieMap map k a -> Bool
notMember = [k] -> TrieMap map k a -> Bool
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> Bool
Base.notMember

-- | @O(min(m,s))@. 'Just' the value in the map associated with the given key,
-- or 'Nothing' if the key is not a member of the map.
lookup :: Map map k => [k] -> TrieMap map k a -> Maybe a
lookup :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> TrieMap map k a -> Maybe a
lookup = [k] -> TrieMap map k a -> Maybe a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> st a
Base.lookup

-- | @O(min(m,s))@. Like 'lookup', but returns the given value when the key is
-- not a member of the map.
lookupWithDefault :: Map map k => a -> [k] -> TrieMap map k a -> a
lookupWithDefault :: forall (map :: * -> * -> *) k a.
Map map k =>
a -> [k] -> TrieMap map k a -> a
lookupWithDefault = a -> [k] -> TrieMap map k a -> a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
a -> [k] -> trie map k a -> a
Base.lookupWithDefault

-- | @O(min(n1 m1,n2 m2))@. 'True' iff the first map is a submap of the second,
-- i.e. all keys that are members of the first map are also members of the
-- second map, and their associated values are the same.
--
-- > isSubmapOf = isSubmapOfBy (==)
isSubmapOf :: (Map map k, Eq a) => TrieMap map k a -> TrieMap map k a -> Bool
isSubmapOf :: forall (map :: * -> * -> *) k a.
(Map map k, Eq a) =>
TrieMap map k a -> TrieMap map k a -> Bool
isSubmapOf = (a -> a -> Bool) -> TrieMap map k a -> TrieMap map k a -> Bool
forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> Bool) -> TrieMap map k a -> TrieMap map k b -> Bool
isSubmapOfBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)

-- | @O(min(n1 m1,n2 m2))@. Like 'isSubmapOf', but one can specify the equality
-- relation applied to the values.
--
-- 'True' iff all keys that are members of the first map are also members of
-- the second map, and the given function @f@ returns 'True' for all @f
-- firstMapValue secondMapValue@ where @firstMapValue@ and @secondMapValue@ are
-- associated with the same key.
isSubmapOfBy :: Map map k
             => (a -> b -> Bool) -> TrieMap map k a -> TrieMap map k b -> Bool
isSubmapOfBy :: forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> Bool) -> TrieMap map k a -> TrieMap map k b -> Bool
isSubmapOfBy = (a -> b -> Bool) -> TrieMap map k a -> TrieMap map k b -> Bool
forall (st :: * -> *) a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Boolable (st b), Trie trie st map k) =>
(a -> b -> Bool) -> trie map k a -> trie map k b -> Bool
Base.isSubmapOfBy

-- | @O(min(n1 m1,n2 m2))@. 'True' iff the first map is a proper submap of the
-- second, i.e. all keys that are members of the first map are also members of
-- the second map, and their associated values are the same, but the maps are
-- not equal. That is, at least one key was a member of the second map but not
-- the first.
--
-- > isProperSubmapOf = isProperSubmapOfBy (==)
isProperSubmapOf :: (Map map k, Eq a)
                 => TrieMap map k a -> TrieMap map k a -> Bool
isProperSubmapOf :: forall (map :: * -> * -> *) k a.
(Map map k, Eq a) =>
TrieMap map k a -> TrieMap map k a -> Bool
isProperSubmapOf = (a -> a -> Bool) -> TrieMap map k a -> TrieMap map k a -> Bool
forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> Bool) -> TrieMap map k a -> TrieMap map k b -> Bool
isProperSubmapOfBy a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)

-- | @O(min(n1 m1,n2 m2))@. Like 'isProperSubmapOf', but one can specify the
-- equality relation applied to the values.
--
-- 'True' iff all keys that are members of the first map are also members of
-- the second map, and the given function @f@ returns 'True' for all @f
-- firstMapValue secondMapValue@ where @firstMapValue@ and @secondMapValue@ are
-- associated with the same key, and at least one key in the second map is not
-- a member of the first.
isProperSubmapOfBy :: Map map k => (a -> b -> Bool)
                                -> TrieMap map k a
                                -> TrieMap map k b
                                -> Bool
isProperSubmapOfBy :: forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> Bool) -> TrieMap map k a -> TrieMap map k b -> Bool
isProperSubmapOfBy = (a -> b -> Bool) -> TrieMap map k a -> TrieMap map k b -> Bool
forall (st :: * -> *) a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Boolable (st b), Trie trie st map k) =>
(a -> b -> Bool) -> trie map k a -> trie map k b -> Bool
Base.isProperSubmapOfBy

-- * Combination

defaultUnion :: a -> a -> a
defaultUnion :: forall a. a -> a -> a
defaultUnion = a -> a -> a
forall a b. a -> b -> a
const

-- | @O(min(n1 m1,n2 m2))@. The union of the two maps: the map which contains
-- all keys that are members of either map. This union is left-biased: if a key
-- is a member of both maps, the value from the first map is chosen.
--
-- The worst-case performance occurs when the two maps are identical.
--
-- > union = unionWith const
union :: Map map k => TrieMap map k a -> TrieMap map k a -> TrieMap map k a
union :: forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> TrieMap map k a -> TrieMap map k a
union = (a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
unionWith a -> a -> a
forall a. a -> a -> a
defaultUnion

-- | @O(min(n1 m1,n2 m2))@. Like 'union', but the combining function ('const') is
-- applied strictly.
--
-- > union' = unionWith' const
union' :: Map map k => TrieMap map k a -> TrieMap map k a -> TrieMap map k a
union' :: forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> TrieMap map k a -> TrieMap map k a
union' = (a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
unionWith' a -> a -> a
forall a. a -> a -> a
defaultUnion

-- | @O(min(n1 m1,n2 m2))@. Like 'union', but the given function is used to
-- determine the new value if a key is a member of both given maps. For a
-- function @f@, the new value is @f firstMapValue secondMapValue@.
unionWith :: Map map k => (a -> a -> a)
                       -> TrieMap map k a
                       -> TrieMap map k a
                       -> TrieMap map k a
unionWith :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
unionWith = (a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
Base.unionWith

-- | @O(min(n1 m1,n2 m2))@. Like 'unionWith', but the combining function is
-- applied strictly.
unionWith' :: Map map k => (a -> a -> a)
                        -> TrieMap map k a
                        -> TrieMap map k a
                        -> TrieMap map k a
unionWith' :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
unionWith' = (a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> trie map k a -> trie map k a -> trie map k a
Base.unionWith'

-- | @O(min(n1 m1,n2 m2))@. Like 'unionWith', but in addition to the two
-- values, the key is passed to the combining function.
unionWithKey :: Map map k => ([k] -> a -> a -> a)
                          -> TrieMap map k a
                          -> TrieMap map k a
                          -> TrieMap map k a
unionWithKey :: forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
unionWithKey = ([k] -> a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a)
-> trie map k a -> trie map k a -> trie map k a
Base.unionWithKey

-- | @O(min(n1 m1,n2 m2))@. Like 'unionWithKey', but the combining function is
-- applied strictly.
unionWithKey' :: Map map k => ([k] -> a -> a -> a)
                           -> TrieMap map k a
                           -> TrieMap map k a
                           -> TrieMap map k a
unionWithKey' :: forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
unionWithKey' = ([k] -> a -> a -> a)
-> TrieMap map k a -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a)
-> trie map k a -> trie map k a -> trie map k a
Base.unionWithKey'

-- | @O(sum(n))@. The union of all the maps: the map which contains all keys
-- that are members of any of the maps. If a key is a member of multiple maps,
-- the value that occurs in the earliest of the maps (according to the order of
-- the given list) is chosen.
--
-- The worst-case performance occurs when all the maps are identical.
--
-- > unions = unionsWith const
unions :: Map map k => [TrieMap map k a] -> TrieMap map k a
unions :: forall (map :: * -> * -> *) k a.
Map map k =>
[TrieMap map k a] -> TrieMap map k a
unions = (a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
unionsWith a -> a -> a
forall a. a -> a -> a
defaultUnion

-- | @O(sum(n))@. Like 'unions', but the combining function ('const') is
-- applied strictly.
--
-- > unions' = unionsWith' const
unions' :: Map map k => [TrieMap map k a] -> TrieMap map k a
unions' :: forall (map :: * -> * -> *) k a.
Map map k =>
[TrieMap map k a] -> TrieMap map k a
unions' = (a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
unionsWith' a -> a -> a
forall a. a -> a -> a
defaultUnion

-- | @O(sum(n))@. Like 'unions', but the given function determines the final
-- value if a key is a member of more than one map. The function is applied as
-- a left fold over the values in the given list's order. For example:
--
-- > unionsWith (-) [fromList [("a",1)],fromList [("a",2)],fromList [("a",3)]]
-- >    == fromList [("a",(1-2)-3)]
-- >    == fromList [("a",-4)]
unionsWith :: Map map k
           => (a -> a -> a) -> [TrieMap map k a] ->  TrieMap map k a
unionsWith :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
unionsWith = (a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> [trie map k a] -> trie map k a
Base.unionsWith

-- | @O(sum(n))@. Like 'unionsWith', but the combining function is applied
-- strictly.
unionsWith' :: Map map k
            => (a -> a -> a) -> [TrieMap map k a] ->  TrieMap map k a
unionsWith' :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
unionsWith' = (a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Unionable st a, Trie trie st map k) =>
(a -> a -> a) -> [trie map k a] -> trie map k a
Base.unionsWith'

-- | @O(sum(n))@. Like 'unionsWith', but in addition to the two values under
-- consideration, the key is passed to the combining function.
unionsWithKey :: Map map k
              => ([k] -> a -> a -> a) -> [TrieMap map k a] ->  TrieMap map k a
unionsWithKey :: forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
unionsWithKey = ([k] -> a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a) -> [trie map k a] -> trie map k a
Base.unionsWithKey

-- | @O(sum(n))@. Like 'unionsWithKey', but the combining function is applied
-- strictly.
unionsWithKey' :: Map map k
               => ([k] -> a -> a -> a) -> [TrieMap map k a] ->  TrieMap map k a
unionsWithKey' :: forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
unionsWithKey' = ([k] -> a -> a -> a) -> [TrieMap map k a] -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Unionable st a, Trie trie st map k) =>
([k] -> a -> a -> a) -> [trie map k a] -> trie map k a
Base.unionsWithKey'

-- | @O(min(n1 m1,n2 m2))@. The difference of the two maps: the map which
-- contains all keys that are members of the first map and not of the second.
--
-- The worst-case performance occurs when the two maps are identical.
--
-- > difference = differenceWith (\_ _ -> Nothing)
difference :: Map map k
           => TrieMap map k a -> TrieMap map k b -> TrieMap map k a
difference :: forall (map :: * -> * -> *) k a b.
Map map k =>
TrieMap map k a -> TrieMap map k b -> TrieMap map k a
difference = (a -> b -> Maybe a)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> Maybe a)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
differenceWith (\a
_ b
_ -> Maybe a
forall a. Maybe a
Nothing)

-- | @O(min(n1 m1,n2 m2))@. Like 'difference', but the given function
-- determines what to do when a key is a member of both maps. If the function
-- returns 'Nothing', the key is removed; if it returns 'Just' a new value,
-- that value replaces the old one in the first map.
differenceWith :: Map map k => (a -> b -> Maybe a)
                            -> TrieMap map k a
                            -> TrieMap map k b
                            -> TrieMap map k a
differenceWith :: forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> Maybe a)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
differenceWith = (a -> b -> Maybe a)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
forall (st :: * -> *) a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Differentiable st a b, Trie trie st map k) =>
(a -> b -> Maybe a) -> trie map k a -> trie map k b -> trie map k a
Base.differenceWith

-- | @O(min(n1 m1,n2 m2))@. Like 'differenceWith', but in addition to the two
-- values, the key they are associated with is passed to the combining
-- function.
differenceWithKey :: Map map k => ([k] -> a -> b -> Maybe a)
                               -> TrieMap map k a
                               -> TrieMap map k b
                               -> TrieMap map k a
differenceWithKey :: forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> b -> Maybe a)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
differenceWithKey = ([k] -> a -> b -> Maybe a)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
forall (st :: * -> *) a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Differentiable st a b, Trie trie st map k) =>
([k] -> a -> b -> Maybe a)
-> trie map k a -> trie map k b -> trie map k a
Base.differenceWithKey

-- | @O(min(n1 m1,n2 m2))@. The intersection of the two maps: the map which
-- contains all keys that are members of both maps.
--
-- The worst-case performance occurs when the two maps are identical.
--
-- > intersection = intersectionWith const
intersection :: Map map k
             => TrieMap map k a -> TrieMap map k b -> TrieMap map k a
intersection :: forall (map :: * -> * -> *) k a b.
Map map k =>
TrieMap map k a -> TrieMap map k b -> TrieMap map k a
intersection = (a -> b -> a)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
forall (map :: * -> * -> *) k a b c.
Map map k =>
(a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
intersectionWith a -> b -> a
forall a b. a -> b -> a
const

-- | @O(min(n1 m1,n2 m2))@. Like 'intersection', but the combining function is
-- applied strictly.
--
-- > intersection' = intersectionWith' const
intersection' :: Map map k
              => TrieMap map k a -> TrieMap map k b -> TrieMap map k a
intersection' :: forall (map :: * -> * -> *) k a b.
Map map k =>
TrieMap map k a -> TrieMap map k b -> TrieMap map k a
intersection' = (a -> b -> a)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k a
forall (map :: * -> * -> *) k a b c.
Map map k =>
(a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
intersectionWith' a -> b -> a
forall a b. a -> b -> a
const

-- | @O(min(n1 m1,n2 m2))@. Like 'intersection', but the given function
-- determines the new values.
intersectionWith :: Map map k => (a -> b -> c)
                              -> TrieMap map k a
                              -> TrieMap map k b
                              -> TrieMap map k c
intersectionWith :: forall (map :: * -> * -> *) k a b c.
Map map k =>
(a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
intersectionWith = (a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
forall (st :: * -> *) c a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st c), Intersectable st a b c, Trie trie st map k) =>
(a -> b -> c) -> trie map k a -> trie map k b -> trie map k c
Base.intersectionWith

-- | @O(min(n1 m1,n2 m2))@. Like 'intersectionWith', but the combining function
-- is applied strictly.
intersectionWith' :: Map map k => (a -> b -> c)
                               -> TrieMap map k a
                               -> TrieMap map k b
                               -> TrieMap map k c
intersectionWith' :: forall (map :: * -> * -> *) k a b c.
Map map k =>
(a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
intersectionWith' = (a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
forall (st :: * -> *) c a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st c), Intersectable st a b c, Trie trie st map k) =>
(a -> b -> c) -> trie map k a -> trie map k b -> trie map k c
Base.intersectionWith'

-- | @O(min(n1 m1,n2 m2))@. Like 'intersectionWith', but in addition to the two
-- values, the key they are associated with is passed to the combining
-- function.
intersectionWithKey :: Map map k => ([k] -> a -> b -> c)
                                 -> TrieMap map k a
                                 -> TrieMap map k b
                                 -> TrieMap map k c
intersectionWithKey :: forall (map :: * -> * -> *) k a b c.
Map map k =>
([k] -> a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
intersectionWithKey = ([k] -> a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
forall (st :: * -> *) c a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st c), Intersectable st a b c, Trie trie st map k) =>
([k] -> a -> b -> c)
-> trie map k a -> trie map k b -> trie map k c
Base.intersectionWithKey

-- | @O(min(n1 m1,n2 m2))@. Like 'intersectionWithKey', but the combining
-- function is applied strictly.
intersectionWithKey' :: Map map k => ([k] -> a -> b -> c)
                                  -> TrieMap map k a
                                  -> TrieMap map k b
                                  -> TrieMap map k c
intersectionWithKey' :: forall (map :: * -> * -> *) k a b c.
Map map k =>
([k] -> a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
intersectionWithKey' = ([k] -> a -> b -> c)
-> TrieMap map k a -> TrieMap map k b -> TrieMap map k c
forall (st :: * -> *) c a b (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st c), Intersectable st a b c, Trie trie st map k) =>
([k] -> a -> b -> c)
-> trie map k a -> trie map k b -> trie map k c
Base.intersectionWithKey'

-- * Filtering

-- | @O(n m)@. Apply the given function to the elements in the map, discarding
-- those for which the function returns 'False'.
filter :: Map map k => (a -> Bool) -> TrieMap map k a -> TrieMap map k a
filter :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> Bool) -> TrieMap map k a -> TrieMap map k a
filter = ([k] -> a -> Bool) -> TrieMap map k a -> TrieMap map k a
forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> Bool) -> TrieMap map k a -> TrieMap map k a
filterWithKey (([k] -> a -> Bool) -> TrieMap map k a -> TrieMap map k a)
-> ((a -> Bool) -> [k] -> a -> Bool)
-> (a -> Bool)
-> TrieMap map k a
-> TrieMap map k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> [k] -> a -> Bool
forall a b. a -> b -> a
const

-- | @O(n m)@. Like 'filter', but the key associated with the element is also
-- passed to the given predicate.
filterWithKey :: Map map k
              => ([k] -> a -> Bool) -> TrieMap map k a -> TrieMap map k a
filterWithKey :: forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> Bool) -> TrieMap map k a -> TrieMap map k a
filterWithKey = ([k] -> a -> Bool) -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
([k] -> a -> Bool) -> trie map k a -> trie map k a
Base.filterWithKey

-- | @O(n m)@. A pair of maps: the first element contains those values for
-- which the given predicate returns 'True', and the second contains those for
-- which it was 'False'.
partition :: Map map k => (a -> Bool)
                       -> TrieMap map k a
                       -> (TrieMap map k a, TrieMap map k a)
partition :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> Bool)
-> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
partition = ([k] -> a -> Bool)
-> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> Bool)
-> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
partitionWithKey (([k] -> a -> Bool)
 -> TrieMap map k a -> (TrieMap map k a, TrieMap map k a))
-> ((a -> Bool) -> [k] -> a -> Bool)
-> (a -> Bool)
-> TrieMap map k a
-> (TrieMap map k a, TrieMap map k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Bool) -> [k] -> a -> Bool
forall a b. a -> b -> a
const

-- | @O(n m)@. Like 'partition', but the key associated with the element is
-- also passed to the given predicate.
partitionWithKey :: Map map k => ([k] -> a -> Bool)
                              -> TrieMap map k a
                              -> (TrieMap map k a, TrieMap map k a)
partitionWithKey :: forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> Bool)
-> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
partitionWithKey = ([k] -> a -> Bool)
-> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
([k] -> a -> Bool) -> trie map k a -> (trie map k a, trie map k a)
Base.partitionWithKey

-- | @O(n m)@. Apply the given function to the elements in the map, preserving
-- only the 'Just' results.
mapMaybe :: Map map k
         => (a -> Maybe b) -> TrieMap map k a -> TrieMap map k b
mapMaybe :: forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> Maybe b) -> TrieMap map k a -> TrieMap map k b
mapMaybe = ([k] -> a -> Maybe b) -> TrieMap map k a -> TrieMap map k b
forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> Maybe b) -> TrieMap map k a -> TrieMap map k b
mapMaybeWithKey (([k] -> a -> Maybe b) -> TrieMap map k a -> TrieMap map k b)
-> ((a -> Maybe b) -> [k] -> a -> Maybe b)
-> (a -> Maybe b)
-> TrieMap map k a
-> TrieMap map k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe b) -> [k] -> a -> Maybe b
forall a b. a -> b -> a
const

-- | @O(n m)@. Like 'mapMaybe', but the key associated with the element is also
-- passed to the given function.
mapMaybeWithKey :: Map map k
                => ([k] -> a -> Maybe b) -> TrieMap map k a -> TrieMap map k b
mapMaybeWithKey :: forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> Maybe b) -> TrieMap map k a -> TrieMap map k b
mapMaybeWithKey [k] -> a -> Maybe b
f =
   [([k], b)] -> TrieMap map k b
forall (map :: * -> * -> *) k a.
Map map k =>
[([k], a)] -> TrieMap map k a
fromList ([([k], b)] -> TrieMap map k b)
-> (TrieMap map k a -> [([k], b)])
-> TrieMap map k a
-> TrieMap map k b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (([k], a) -> Maybe ([k], b)) -> [([k], a)] -> [([k], b)]
forall a b. (a -> Maybe b) -> [a] -> [b]
Maybe.mapMaybe (\([k]
k,a
v) -> (b -> ([k], b)) -> Maybe b -> Maybe ([k], b)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((,) [k]
k) ([k] -> a -> Maybe b
f [k]
k a
v)) ([([k], a)] -> [([k], b)])
-> (TrieMap map k a -> [([k], a)]) -> TrieMap map k a -> [([k], b)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. TrieMap map k a -> [([k], a)]
forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> [([k], a)]
toList

-- | @O(n m)@. Apply the given function to the elements in the map, separating
-- the 'Left' results from the 'Right'. The first element of the pair contains
-- the former results, and the second the latter.
mapEither :: Map map k => (a -> Either b c)
                       -> TrieMap map k a
                       -> (TrieMap map k b, TrieMap map k c)
mapEither :: forall (map :: * -> * -> *) k a b c.
Map map k =>
(a -> Either b c)
-> TrieMap map k a -> (TrieMap map k b, TrieMap map k c)
mapEither = ([k] -> a -> Either b c)
-> TrieMap map k a -> (TrieMap map k b, TrieMap map k c)
forall (map :: * -> * -> *) k a b c.
Map map k =>
([k] -> a -> Either b c)
-> TrieMap map k a -> (TrieMap map k b, TrieMap map k c)
mapEitherWithKey (([k] -> a -> Either b c)
 -> TrieMap map k a -> (TrieMap map k b, TrieMap map k c))
-> ((a -> Either b c) -> [k] -> a -> Either b c)
-> (a -> Either b c)
-> TrieMap map k a
-> (TrieMap map k b, TrieMap map k c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Either b c) -> [k] -> a -> Either b c
forall a b. a -> b -> a
const

-- | @O(n m)@. Like 'mapEither', but the key associated with the element is
-- also passed to the given function.
mapEitherWithKey :: Map map k => ([k] -> a -> Either b c)
                              -> TrieMap map k a
                              -> (TrieMap map k b, TrieMap map k c)
mapEitherWithKey :: forall (map :: * -> * -> *) k a b c.
Map map k =>
([k] -> a -> Either b c)
-> TrieMap map k a -> (TrieMap map k b, TrieMap map k c)
mapEitherWithKey [k] -> a -> Either b c
f =
   ([([k], b)] -> TrieMap map k b
forall (map :: * -> * -> *) k a.
Map map k =>
[([k], a)] -> TrieMap map k a
fromList ([([k], b)] -> TrieMap map k b)
-> ([([k], c)] -> TrieMap map k c)
-> ([([k], b)], [([k], c)])
-> (TrieMap map k b, TrieMap map k c)
forall b c b' c'. (b -> c) -> (b' -> c') -> (b, b') -> (c, c')
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** [([k], c)] -> TrieMap map k c
forall (map :: * -> * -> *) k a.
Map map k =>
[([k], a)] -> TrieMap map k a
fromList) (([([k], b)], [([k], c)]) -> (TrieMap map k b, TrieMap map k c))
-> (TrieMap map k a -> ([([k], b)], [([k], c)]))
-> TrieMap map k a
-> (TrieMap map k b, TrieMap map k c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Either ([k], b) ([k], c)] -> ([([k], b)], [([k], c)])
forall a b. [Either a b] -> ([a], [b])
partitionEithers ([Either ([k], b) ([k], c)] -> ([([k], b)], [([k], c)]))
-> (TrieMap map k a -> [Either ([k], b) ([k], c)])
-> TrieMap map k a
-> ([([k], b)], [([k], c)])
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   (([k], a) -> Either ([k], b) ([k], c))
-> [([k], a)] -> [Either ([k], b) ([k], c)]
forall a b. (a -> b) -> [a] -> [b]
Prelude.map (\([k]
k,a
v) -> (b -> Either ([k], b) ([k], c))
-> (c -> Either ([k], b) ([k], c))
-> Either b c
-> Either ([k], b) ([k], c)
forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (([k], b) -> Either ([k], b) ([k], c)
forall a b. a -> Either a b
Left (([k], b) -> Either ([k], b) ([k], c))
-> (b -> ([k], b)) -> b -> Either ([k], b) ([k], c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (,) [k]
k) (([k], c) -> Either ([k], b) ([k], c)
forall a b. b -> Either a b
Right (([k], c) -> Either ([k], b) ([k], c))
-> (c -> ([k], c)) -> c -> Either ([k], b) ([k], c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (,) [k]
k) ([k] -> a -> Either b c
f [k]
k a
v)) ([([k], a)] -> [Either ([k], b) ([k], c)])
-> (TrieMap map k a -> [([k], a)])
-> TrieMap map k a
-> [Either ([k], b) ([k], c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
   TrieMap map k a -> [([k], a)]
forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> [([k], a)]
toList

-- * Mapping

-- | @O(n m)@. Apply the given function to all the elements in the map.
map :: Map map k => (a -> b) -> TrieMap map k a -> TrieMap map k b
map :: forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b) -> TrieMap map k a -> TrieMap map k b
map = ((a -> b) -> Maybe a -> Maybe b)
-> (a -> b) -> TrieMap map k a -> TrieMap map k b
forall (map :: * -> * -> *) k a b.
Map map k =>
((a -> b) -> Maybe a -> Maybe b)
-> (a -> b) -> TrieMap map k a -> TrieMap map k b
genericMap (a -> b) -> Maybe a -> Maybe b
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap

-- | @O(n m)@. Like 'map', but apply the function strictly.
map' :: Map map k => (a -> b) -> TrieMap map k a -> TrieMap map k b
map' :: forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b) -> TrieMap map k a -> TrieMap map k b
map' = ((a -> b) -> Maybe a -> Maybe b)
-> (a -> b) -> TrieMap map k a -> TrieMap map k b
forall (map :: * -> * -> *) k a b.
Map map k =>
((a -> b) -> Maybe a -> Maybe b)
-> (a -> b) -> TrieMap map k a -> TrieMap map k b
genericMap (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b.
(Boolable (f a), Unwrappable f, Alt f b) =>
(a -> b) -> f a -> f b
fmap'

genericMap :: Map map k => ((a -> b) -> Maybe a -> Maybe b)
                        -> (a -> b) -> TrieMap map k a -> TrieMap map k b
genericMap :: forall (map :: * -> * -> *) k a b.
Map map k =>
((a -> b) -> Maybe a -> Maybe b)
-> (a -> b) -> TrieMap map k a -> TrieMap map k b
genericMap (a -> b) -> Maybe a -> Maybe b
myFmap a -> b
f (Tr Maybe a
v CMap map k a
m) = Maybe b -> CMap map k b -> TrieMap map k b
forall (map :: * -> * -> *) k v.
Maybe v -> CMap map k v -> TrieMap map k v
Tr ((a -> b) -> Maybe a -> Maybe b
myFmap a -> b
f Maybe a
v)
                                  ((TrieMap map k a -> TrieMap map k b)
-> CMap map k a -> CMap map k b
forall a b. (a -> b) -> map k a -> map k b
forall (m :: * -> * -> *) k a b.
Map m k =>
(a -> b) -> m k a -> m k b
Map.map (((a -> b) -> Maybe a -> Maybe b)
-> (a -> b) -> TrieMap map k a -> TrieMap map k b
forall (map :: * -> * -> *) k a b.
Map map k =>
((a -> b) -> Maybe a -> Maybe b)
-> (a -> b) -> TrieMap map k a -> TrieMap map k b
genericMap (a -> b) -> Maybe a -> Maybe b
myFmap a -> b
f) CMap map k a
m)

-- | @O(n m)@. Like 'map', but also pass the key associated with the element to
-- the given function.
mapWithKey :: Map map k
           => ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
mapWithKey :: forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
mapWithKey = ((a -> b) -> Maybe a -> Maybe b)
-> ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
forall (map :: * -> * -> *) k a b.
Map map k =>
((a -> b) -> Maybe a -> Maybe b)
-> ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
genericMapWithKey (a -> b) -> Maybe a -> Maybe b
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap

-- | @O(n m)@. Like 'mapWithKey', but apply the function strictly.
mapWithKey' :: Map map k
            => ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
mapWithKey' :: forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
mapWithKey' = ((a -> b) -> Maybe a -> Maybe b)
-> ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
forall (map :: * -> * -> *) k a b.
Map map k =>
((a -> b) -> Maybe a -> Maybe b)
-> ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
genericMapWithKey (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b.
(Boolable (f a), Unwrappable f, Alt f b) =>
(a -> b) -> f a -> f b
fmap'

genericMapWithKey :: Map map k
                  => ((a -> b) -> Maybe a -> Maybe b)
                  -> ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
genericMapWithKey :: forall (map :: * -> * -> *) k a b.
Map map k =>
((a -> b) -> Maybe a -> Maybe b)
-> ([k] -> a -> b) -> TrieMap map k a -> TrieMap map k b
genericMapWithKey = DList k
-> ((a -> b) -> Maybe a -> Maybe b)
-> ([k] -> a -> b)
-> TrieMap map k a
-> TrieMap map k b
forall {map :: * -> * -> *} {a} {t} {v} {v}.
Map map a =>
DList a
-> (t -> Maybe v -> Maybe v)
-> ([a] -> t)
-> TrieMap map a v
-> TrieMap map a v
go DList k
forall a. DList a
DL.empty
 where
   go :: DList a
-> (t -> Maybe v -> Maybe v)
-> ([a] -> t)
-> TrieMap map a v
-> TrieMap map a v
go DList a
k t -> Maybe v -> Maybe v
myFmap [a] -> t
f (Tr Maybe v
v CMap map a v
m) =
      Maybe v -> CMap map a v -> TrieMap map a v
forall (map :: * -> * -> *) k v.
Maybe v -> CMap map k v -> TrieMap map k v
Tr (t -> Maybe v -> Maybe v
myFmap ([a] -> t
f ([a] -> t) -> [a] -> t
forall a b. (a -> b) -> a -> b
$ DList a -> [a]
forall a. DList a -> [a]
DL.toList DList a
k) Maybe v
v)
         ((a -> TrieMap map a v -> TrieMap map a v)
-> CMap map a v -> CMap map a v
forall a b. (a -> a -> b) -> map a a -> map a b
forall (m :: * -> * -> *) k a b.
Map m k =>
(k -> a -> b) -> m k a -> m k b
Map.mapWithKey (\a
x -> DList a
-> (t -> Maybe v -> Maybe v)
-> ([a] -> t)
-> TrieMap map a v
-> TrieMap map a v
go (DList a
k DList a -> a -> DList a
forall a. DList a -> a -> DList a
`DL.snoc` a
x) t -> Maybe v -> Maybe v
myFmap [a] -> t
f) CMap map a v
m)

-- | @O(n m)@. Apply the given function to all the keys in a map.
--
-- > mapKeys = mapKeysWith const
mapKeys :: (Map map k1, Map map k2)
        => ([k1] -> [k2]) -> TrieMap map k1 a -> TrieMap map k2 a
mapKeys :: forall (map :: * -> * -> *) k1 k2 a.
(Map map k1, Map map k2) =>
([k1] -> [k2]) -> TrieMap map k1 a -> TrieMap map k2 a
mapKeys = (a -> a -> a)
-> ([k1] -> [k2]) -> TrieMap map k1 a -> TrieMap map k2 a
forall (map :: * -> * -> *) k1 k2 a.
(Map map k1, Map map k2) =>
(a -> a -> a)
-> ([k1] -> [k2]) -> TrieMap map k1 a -> TrieMap map k2 a
mapKeysWith a -> a -> a
forall a b. a -> b -> a
const

-- | @O(n m)@. Like 'mapKeys', but use the first given function to combine
-- elements if the second function gives two keys the same value.
mapKeysWith :: (Map map k1, Map map k2) => (a -> a -> a)
                                        -> ([k1] -> [k2])
                                        -> TrieMap map k1 a
                                        -> TrieMap map k2 a
mapKeysWith :: forall (map :: * -> * -> *) k1 k2 a.
(Map map k1, Map map k2) =>
(a -> a -> a)
-> ([k1] -> [k2]) -> TrieMap map k1 a -> TrieMap map k2 a
mapKeysWith = ([([k2], a)] -> TrieMap map k2 a)
-> ([k1] -> [k2]) -> TrieMap map k1 a -> TrieMap map k2 a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k1 k2.
(Boolable (st a), Trie trie st map k1, Trie trie st map k2) =>
([([k2], a)] -> trie map k2 a)
-> ([k1] -> [k2]) -> trie map k1 a -> trie map k2 a
Base.mapKeysWith (([([k2], a)] -> TrieMap map k2 a)
 -> ([k1] -> [k2]) -> TrieMap map k1 a -> TrieMap map k2 a)
-> ((a -> a -> a) -> [([k2], a)] -> TrieMap map k2 a)
-> (a -> a -> a)
-> ([k1] -> [k2])
-> TrieMap map k1 a
-> TrieMap map k2 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a -> a) -> [([k2], a)] -> TrieMap map k2 a
forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a) -> [([k], a)] -> TrieMap map k a
fromListWith

-- | @O(n m)@. Apply the given function to the contents of all the keys in the
-- map.
--
-- > mapInKeys = mapInKeysWith const
mapInKeys :: (Map map k1, Map map k2)
          => (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
mapInKeys :: forall (map :: * -> * -> *) k1 k2 a.
(Map map k1, Map map k2) =>
(k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
mapInKeys = (a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
forall (map :: * -> * -> *) k1 k2 a.
(Map map k1, Map map k2) =>
(a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
mapInKeysWith a -> a -> a
forall a. a -> a -> a
defaultUnion

-- | @O(n m)@. Like 'mapInKeys', but combine identical keys strictly.
--
-- > mapInKeys' = mapInKeysWith' const
mapInKeys' :: (Map map k1, Map map k2)
           => (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
mapInKeys' :: forall (map :: * -> * -> *) k1 k2 a.
(Map map k1, Map map k2) =>
(k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
mapInKeys' = (a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
forall (map :: * -> * -> *) k1 k2 a.
(Map map k1, Map map k2) =>
(a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
mapInKeysWith' a -> a -> a
forall a. a -> a -> a
defaultUnion

-- | @O(n m)@. Like 'mapInKeys', but use the first given function to combine
-- elements if the second function gives two keys the same value.
mapInKeysWith :: (Map map k1, Map map k2) => (a -> a -> a)
                                          -> (k1 -> k2)
                                          -> TrieMap map k1 a
                                          -> TrieMap map k2 a
mapInKeysWith :: forall (map :: * -> * -> *) k1 k2 a.
(Map map k1, Map map k2) =>
(a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
mapInKeysWith = (a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k1 k2.
(Unionable st a, Trie trie st map k1, Trie trie st map k2) =>
(a -> a -> a) -> (k1 -> k2) -> trie map k1 a -> trie map k2 a
Base.mapInKeysWith

-- | @O(n m)@. Like 'mapInKeysWith', but apply the combining function strictly.
mapInKeysWith' :: (Map map k1, Map map k2) => (a -> a -> a)
                                           -> (k1 -> k2)
                                           -> TrieMap map k1 a
                                           -> TrieMap map k2 a
mapInKeysWith' :: forall (map :: * -> * -> *) k1 k2 a.
(Map map k1, Map map k2) =>
(a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
mapInKeysWith' = (a -> a -> a) -> (k1 -> k2) -> TrieMap map k1 a -> TrieMap map k2 a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k1 k2.
(Unionable st a, Trie trie st map k1, Trie trie st map k2) =>
(a -> a -> a) -> (k1 -> k2) -> trie map k1 a -> trie map k2 a
Base.mapInKeysWith'

-- | @O(n m)@. Like "Data.List".@mapAccumL@ on the 'toList' representation.
--
-- Essentially a combination of 'map' and 'foldl': the given
-- function is applied to each element of the map, resulting in a new value for
-- the accumulator and a replacement element for the map.
mapAccum :: Map map k => (acc -> a -> (acc, b))
                      -> acc
                      -> TrieMap map k a
                      -> (acc, TrieMap map k b)
mapAccum :: forall (map :: * -> * -> *) k acc a b.
Map map k =>
(acc -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccum = ((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccum (acc -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c. (a -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
Map m k =>
(a -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccum (((acc, Maybe b) -> b -> (acc, Maybe b))
-> b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (acc, Maybe b) -> b -> (acc, Maybe b)
forall a b. a -> b -> a
const)

-- | @O(n m)@. Like 'mapAccum', but the function is applied strictly.
mapAccum' :: Map map k => (acc -> a -> (acc, b))
                       -> acc
                       -> TrieMap map k a
                       -> (acc, TrieMap map k b)
mapAccum' :: forall (map :: * -> * -> *) k acc a b.
Map map k =>
(acc -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccum' = ((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccum (acc -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c. (a -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
Map m k =>
(a -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccum b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b. a -> b -> b
seq

-- | @O(n m)@. Like 'mapAccum', but the function receives the key in addition
-- to the value associated with it.
mapAccumWithKey :: Map map k => (acc -> [k] -> a -> (acc, b))
                             -> acc
                             -> TrieMap map k a
                             -> (acc, TrieMap map k b)
mapAccumWithKey :: forall (map :: * -> * -> *) k acc a b.
Map map k =>
(acc -> [k] -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumWithKey = ((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccumWithKey (acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c.
(a -> k -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
Map m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumWithKey (((acc, Maybe b) -> b -> (acc, Maybe b))
-> b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (acc, Maybe b) -> b -> (acc, Maybe b)
forall a b. a -> b -> a
const)

-- | @O(n m)@. Like 'mapAccumWithKey', but the function is applied strictly.
mapAccumWithKey' :: Map map k => (acc -> [k] -> a -> (acc, b))
                              -> acc
                              -> TrieMap map k a
                              -> (acc, TrieMap map k b)
mapAccumWithKey' :: forall (map :: * -> * -> *) k acc a b.
Map map k =>
(acc -> [k] -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumWithKey' = ((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccumWithKey (acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c.
(a -> k -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
Map m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumWithKey b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b. a -> b -> b
seq

-- | @O(n m)@. Like 'mapAccum', but in ascending order, as though operating on
-- the 'toAscList' representation.
mapAccumAsc :: OrdMap map k => (acc -> a -> (acc, b))
                            -> acc
                            -> TrieMap map k a
                            -> (acc, TrieMap map k b)
mapAccumAsc :: forall (map :: * -> * -> *) k acc a b.
OrdMap map k =>
(acc -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumAsc = ((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccum (acc -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c. (a -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumAsc (((acc, Maybe b) -> b -> (acc, Maybe b))
-> b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (acc, Maybe b) -> b -> (acc, Maybe b)
forall a b. a -> b -> a
const)

-- | @O(n m)@. Like 'mapAccumAsc', but the function is applied strictly.
mapAccumAsc' :: OrdMap map k => (acc -> a -> (acc, b))
                             -> acc
                             -> TrieMap map k a
                             -> (acc, TrieMap map k b)
mapAccumAsc' :: forall (map :: * -> * -> *) k acc a b.
OrdMap map k =>
(acc -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumAsc' = ((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccum (acc -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c. (a -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumAsc b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b. a -> b -> b
seq

-- | @O(n m)@. Like 'mapAccumAsc', but the function receives the key in
-- addition to the value associated with it.
mapAccumAscWithKey :: OrdMap map k => (acc -> [k] -> a -> (acc, b))
                                   -> acc
                                   -> TrieMap map k a
                                   -> (acc, TrieMap map k b)
mapAccumAscWithKey :: forall (map :: * -> * -> *) k acc a b.
OrdMap map k =>
(acc -> [k] -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumAscWithKey = ((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccumWithKey (acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c.
(a -> k -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumAscWithKey (((acc, Maybe b) -> b -> (acc, Maybe b))
-> b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (acc, Maybe b) -> b -> (acc, Maybe b)
forall a b. a -> b -> a
const)

-- | @O(n m)@. Like 'mapAccumAscWithKey', but the function is applied strictly.
mapAccumAscWithKey' :: OrdMap map k => (acc -> [k] -> a -> (acc, b))
                                    -> acc
                                    -> TrieMap map k a
                                    -> (acc, TrieMap map k b)
mapAccumAscWithKey' :: forall (map :: * -> * -> *) k acc a b.
OrdMap map k =>
(acc -> [k] -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumAscWithKey' = ((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccumWithKey (acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c.
(a -> k -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumAscWithKey b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b. a -> b -> b
seq

-- | @O(n m)@. Like 'mapAccum', but in descending order, as though operating on
-- the 'toDescList' representation.
mapAccumDesc :: OrdMap map k => (acc -> a -> (acc, b))
                             -> acc
                             -> TrieMap map k a
                             -> (acc, TrieMap map k b)
mapAccumDesc :: forall (map :: * -> * -> *) k acc a b.
OrdMap map k =>
(acc -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumDesc = ((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccum (acc -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c. (a -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumDesc (((acc, Maybe b) -> b -> (acc, Maybe b))
-> b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (acc, Maybe b) -> b -> (acc, Maybe b)
forall a b. a -> b -> a
const)

-- | @O(n m)@. Like 'mapAccumDesc', but the function is applied strictly.
mapAccumDesc' :: OrdMap map k => (acc -> a -> (acc, b))
                              -> acc
                              -> TrieMap map k a
                              -> (acc, TrieMap map k b)
mapAccumDesc' :: forall (map :: * -> * -> *) k acc a b.
OrdMap map k =>
(acc -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumDesc' = ((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccum (acc -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c. (a -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumDesc b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b. a -> b -> b
seq

-- | @O(n m)@. Like 'mapAccumDesc', but the function receives the key in
-- addition to the value associated with it.
mapAccumDescWithKey :: OrdMap map k => (acc -> [k] -> a -> (acc, b))
                                    -> acc
                                    -> TrieMap map k a
                                    -> (acc, TrieMap map k b)
mapAccumDescWithKey :: forall (map :: * -> * -> *) k acc a b.
OrdMap map k =>
(acc -> [k] -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumDescWithKey =
   ((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccumWithKey (acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c.
(a -> k -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumDescWithKey (((acc, Maybe b) -> b -> (acc, Maybe b))
-> b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b c. (a -> b -> c) -> b -> a -> c
flip (acc, Maybe b) -> b -> (acc, Maybe b)
forall a b. a -> b -> a
const)

-- | @O(n m)@. Like 'mapAccumDescWithKey', but the function is applied
-- strictly.
mapAccumDescWithKey' :: OrdMap map k => (acc -> [k] -> a -> (acc, b))
                                     -> acc
                                     -> TrieMap map k a
                                     -> (acc, TrieMap map k b)
mapAccumDescWithKey' :: forall (map :: * -> * -> *) k acc a b.
OrdMap map k =>
(acc -> [k] -> a -> (acc, b))
-> acc -> TrieMap map k a -> (acc, TrieMap map k b)
mapAccumDescWithKey' = ((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccumWithKey (acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
forall a b c.
(a -> k -> b -> (a, c)) -> a -> map k b -> (a, map k c)
forall (m :: * -> * -> *) k a b c.
OrdMap m k =>
(a -> k -> b -> (a, c)) -> a -> m k b -> (a, m k c)
Map.mapAccumDescWithKey b -> (acc, Maybe b) -> (acc, Maybe b)
forall a b. a -> b -> b
seq

genericMapAccum :: Map map k
                => (  (acc -> TrieMap map k a -> (acc, TrieMap map k b))
                   -> acc
                   -> CMap map k a
                   -> (acc, CMap map k b)
                   )
                -> (b -> (acc, Maybe b) -> (acc, Maybe b))
                -> (acc -> a -> (acc, b))
                -> acc
                -> TrieMap map k a
                -> (acc, TrieMap map k b)
genericMapAccum :: forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccum (acc -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
subMapAccum b -> (acc, Maybe b) -> (acc, Maybe b)
seeq acc -> a -> (acc, b)
f acc
acc (Tr Maybe a
mv CMap map k a
m) =
   let (acc
acc', Maybe b
mv') =
          case Maybe a
mv of
               Maybe a
Nothing -> (acc
acc, Maybe b
forall a. Maybe a
Nothing)
               Just a
v  ->
                  let (acc
acc'', b
v') = acc -> a -> (acc, b)
f acc
acc a
v
                   in b
v' b -> (acc, Maybe b) -> (acc, Maybe b)
`seeq` (acc
acc'', b -> Maybe b
forall a. a -> Maybe a
Just b
v')
    in (CMap map k b -> TrieMap map k b)
-> (acc, CMap map k b) -> (acc, TrieMap map k b)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second (Maybe b -> CMap map k b -> TrieMap map k b
forall (map :: * -> * -> *) k v.
Maybe v -> CMap map k v -> TrieMap map k v
Tr Maybe b
mv') ((acc, CMap map k b) -> (acc, TrieMap map k b))
-> (acc, CMap map k b) -> (acc, TrieMap map k b)
forall a b. (a -> b) -> a -> b
$
          (acc -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
subMapAccum (((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccum (acc -> TrieMap map k a -> (acc, TrieMap map k b))
-> acc -> CMap map k a -> (acc, CMap map k b)
subMapAccum b -> (acc, Maybe b) -> (acc, Maybe b)
seeq acc -> a -> (acc, b)
f) acc
acc' CMap map k a
m

genericMapAccumWithKey :: Map map k
                       => (  (  acc
                             -> k
                             -> TrieMap map k a
                             -> (acc, TrieMap map k b)
                             )
                          -> acc
                          -> CMap map k a
                          -> (acc, CMap map k b)
                          )
                       -> (b -> (acc, Maybe b) -> (acc, Maybe b))
                       -> (acc -> [k] -> a -> (acc, b))
                       -> acc
                       -> TrieMap map k a
                       -> (acc, TrieMap map k b)
genericMapAccumWithKey :: forall (map :: * -> * -> *) k acc a b.
Map map k =>
((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
 -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
genericMapAccumWithKey = DList k
-> ((acc -> k -> TrieMap map k a -> (acc, TrieMap map k b))
    -> acc -> CMap map k a -> (acc, CMap map k b))
-> (b -> (acc, Maybe b) -> (acc, Maybe b))
-> (acc -> [k] -> a -> (acc, b))
-> acc
-> TrieMap map k a
-> (acc, TrieMap map k b)
forall {a} {t} {map :: * -> * -> *} {k} {v} {d}
       {map :: * -> * -> *} {k} {v} {b} {a}.
DList a
-> ((t -> a -> TrieMap map k v -> (d, TrieMap map k v))
    -> t -> CMap map k v -> (d, CMap map k v))
-> (b -> (a, Maybe b) -> (t, Maybe v))
-> (t -> [a] -> v -> (a, b))
-> t
-> TrieMap map k v
-> (d, TrieMap map k v)
go DList k
forall a. DList a
DL.empty
 where
   go :: DList a
-> ((t -> a -> TrieMap map k v -> (d, TrieMap map k v))
    -> t -> CMap map k v -> (d, CMap map k v))
-> (b -> (a, Maybe b) -> (t, Maybe v))
-> (t -> [a] -> v -> (a, b))
-> t
-> TrieMap map k v
-> (d, TrieMap map k v)
go DList a
k (t -> a -> TrieMap map k v -> (d, TrieMap map k v))
-> t -> CMap map k v -> (d, CMap map k v)
subMapAccum b -> (a, Maybe b) -> (t, Maybe v)
seeq t -> [a] -> v -> (a, b)
f t
acc (Tr Maybe v
mv CMap map k v
m) =
      let (t
acc', Maybe v
mv') =
             case Maybe v
mv of
                  Maybe v
Nothing -> (t
acc, Maybe v
forall a. Maybe a
Nothing)
                  Just v
v  ->
                     let (a
acc'', b
v') = t -> [a] -> v -> (a, b)
f t
acc (DList a -> [a]
forall a. DList a -> [a]
DL.toList DList a
k) v
v
                      in b
v' b -> (a, Maybe b) -> (t, Maybe v)
`seeq` (a
acc'', b -> Maybe b
forall a. a -> Maybe a
Just b
v')
       in (CMap map k v -> TrieMap map k v)
-> (d, CMap map k v) -> (d, TrieMap map k v)
forall b c d. (b -> c) -> (d, b) -> (d, c)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second (Maybe v -> CMap map k v -> TrieMap map k v
forall (map :: * -> * -> *) k v.
Maybe v -> CMap map k v -> TrieMap map k v
Tr Maybe v
mv') ((d, CMap map k v) -> (d, TrieMap map k v))
-> (d, CMap map k v) -> (d, TrieMap map k v)
forall a b. (a -> b) -> a -> b
$
             (t -> a -> TrieMap map k v -> (d, TrieMap map k v))
-> t -> CMap map k v -> (d, CMap map k v)
subMapAccum (\t
a a
x -> DList a
-> ((t -> a -> TrieMap map k v -> (d, TrieMap map k v))
    -> t -> CMap map k v -> (d, CMap map k v))
-> (b -> (a, Maybe b) -> (t, Maybe v))
-> (t -> [a] -> v -> (a, b))
-> t
-> TrieMap map k v
-> (d, TrieMap map k v)
go (DList a
k DList a -> a -> DList a
forall a. DList a -> a -> DList a
`DL.snoc` a
x) (t -> a -> TrieMap map k v -> (d, TrieMap map k v))
-> t -> CMap map k v -> (d, CMap map k v)
subMapAccum b -> (a, Maybe b) -> (t, Maybe v)
seeq t -> [a] -> v -> (a, b)
f t
a)
                         t
acc' CMap map k v
m

-- * Folding

-- | @O(n m)@. Equivalent to a list @foldr@ on the 'toList' representation,
-- folding only over the elements.
foldr :: Map map k => (a -> b -> b) -> b -> TrieMap map k a -> b
foldr :: forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldr = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldrWithKey (([k] -> a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((a -> b -> b) -> [k] -> a -> b -> b)
-> (a -> b -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> [k] -> a -> b -> b
forall a b. a -> b -> a
const

-- | @O(n m)@. Equivalent to a list @foldr@ on the 'toList' representation,
-- folding over both the keys and the elements.
foldrWithKey :: Map map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldrWithKey :: forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldrWithKey = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
Base.foldrWithKey

-- | @O(n m)@. Equivalent to a list @foldr@ on the 'toAscList' representation.
foldrAsc :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
foldrAsc :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldrAsc = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldrAscWithKey (([k] -> a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((a -> b -> b) -> [k] -> a -> b -> b)
-> (a -> b -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> [k] -> a -> b -> b
forall a b. a -> b -> a
const

-- | @O(n m)@. Equivalent to a list @foldr@ on the 'toAscList' representation,
-- folding over both the keys and the elements.
foldrAscWithKey :: OrdMap map k
                => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldrAscWithKey :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldrAscWithKey = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
Base.foldrAscWithKey

-- | @O(n m)@. Equivalent to a list @foldr@ on the 'toDescList' representation.
foldrDesc :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
foldrDesc :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldrDesc = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldrDescWithKey (([k] -> a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((a -> b -> b) -> [k] -> a -> b -> b)
-> (a -> b -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> [k] -> a -> b -> b
forall a b. a -> b -> a
const

-- | @O(n m)@. Equivalent to a list @foldr@ on the 'toDescList' representation,
-- folding over both the keys and the elements.
foldrDescWithKey :: OrdMap map k
                 => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldrDescWithKey :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldrDescWithKey = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
Base.foldrDescWithKey

-- | @O(n m)@. Equivalent to a list @foldl@ on the toList representation.
foldl :: Map map k => (a -> b -> b) -> b -> TrieMap map k a -> b
foldl :: forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldl = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlWithKey (([k] -> a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((a -> b -> b) -> [k] -> a -> b -> b)
-> (a -> b -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> [k] -> a -> b -> b
forall a b. a -> b -> a
const

-- | @O(n m)@. Equivalent to a list @foldl@ on the toList representation,
-- folding over both the keys and the elements.
foldlWithKey :: Map map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlWithKey :: forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlWithKey = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
Base.foldlWithKey

-- | @O(n m)@. Equivalent to a list @foldl@ on the toAscList representation.
foldlAsc :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
foldlAsc :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldlAsc = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlAscWithKey (([k] -> a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((a -> b -> b) -> [k] -> a -> b -> b)
-> (a -> b -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> [k] -> a -> b -> b
forall a b. a -> b -> a
const

-- | @O(n m)@. Equivalent to a list @foldl@ on the toAscList representation,
-- folding over both the keys and the elements.
foldlAscWithKey :: OrdMap map k
                => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlAscWithKey :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlAscWithKey = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
Base.foldlAscWithKey

-- | @O(n m)@. Equivalent to a list @foldl@ on the toDescList representation.
foldlDesc :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
foldlDesc :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldlDesc = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlDescWithKey (([k] -> a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((a -> b -> b) -> [k] -> a -> b -> b)
-> (a -> b -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> [k] -> a -> b -> b
forall a b. a -> b -> a
const

-- | @O(n m)@. Equivalent to a list @foldl@ on the toDescList representation,
-- folding over both the keys and the elements.
foldlDescWithKey :: OrdMap map k
                 => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlDescWithKey :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlDescWithKey = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
Base.foldlDescWithKey

-- | @O(n m)@. Equivalent to a list @foldl'@ on the 'toList' representation.
foldl' :: Map map k => (a -> b -> b) -> b -> TrieMap map k a -> b
foldl' :: forall (map :: * -> * -> *) k a b.
Map map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldl' = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlWithKey' (([k] -> a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((a -> b -> b) -> [k] -> a -> b -> b)
-> (a -> b -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> [k] -> a -> b -> b
forall a b. a -> b -> a
const

-- | @O(n m)@. Equivalent to a list @foldl'@ on the 'toList' representation,
-- folding over both the keys and the elements.
foldlWithKey' :: Map map k => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlWithKey' :: forall (map :: * -> * -> *) k a b.
Map map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlWithKey' = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
Base.foldlWithKey'

-- | @O(n m)@. Equivalent to a list @foldl'@ on the 'toAscList' representation.
foldlAsc' :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
foldlAsc' :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldlAsc' = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlAscWithKey' (([k] -> a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((a -> b -> b) -> [k] -> a -> b -> b)
-> (a -> b -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> [k] -> a -> b -> b
forall a b. a -> b -> a
const

-- | @O(n m)@. Equivalent to a list @foldl'@ on the 'toAscList' representation,
-- folding over both the keys and the elements.
foldlAscWithKey' :: OrdMap map k
                 => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlAscWithKey' :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlAscWithKey' = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
Base.foldlAscWithKey'

-- | @O(n m)@. Equivalent to a list @foldl'@ on the 'toDescList'
-- representation.
foldlDesc' :: OrdMap map k => (a -> b -> b) -> b -> TrieMap map k a -> b
foldlDesc' :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
(a -> b -> b) -> b -> TrieMap map k a -> b
foldlDesc' = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlDescWithKey' (([k] -> a -> b -> b) -> b -> TrieMap map k a -> b)
-> ((a -> b -> b) -> [k] -> a -> b -> b)
-> (a -> b -> b)
-> b
-> TrieMap map k a
-> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> b) -> [k] -> a -> b -> b
forall a b. a -> b -> a
const

-- | @O(n m)@. Equivalent to a list @foldl'@ on the 'toDescList'
-- representation, folding over both the keys and the elements.
foldlDescWithKey' :: OrdMap map k
                  => ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlDescWithKey' :: forall (map :: * -> * -> *) k a b.
OrdMap map k =>
([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
foldlDescWithKey' = ([k] -> a -> b -> b) -> b -> TrieMap map k a -> b
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k b.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
([k] -> a -> b -> b) -> b -> trie map k a -> b
Base.foldlDescWithKey'

-- * Conversion between lists

-- | @O(n m)@. Converts the map to a list of the key-value pairs contained
-- within, in undefined order.
toList :: Map map k => TrieMap map k a -> [([k],a)]
toList :: forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> [([k], a)]
toList = TrieMap map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> [([k], a)]
Base.toList

-- | @O(n m)@. Converts the map to a list of the key-value pairs contained
-- within, in ascending order.
toAscList :: OrdMap map k => TrieMap map k a -> [([k],a)]
toAscList :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
TrieMap map k a -> [([k], a)]
toAscList = TrieMap map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
Base.toAscList

-- | @O(n m)@. Converts the map to a list of the key-value pairs contained
-- within, in descending order.
toDescList :: OrdMap map k => TrieMap map k a -> [([k],a)]
toDescList :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
TrieMap map k a -> [([k], a)]
toDescList = TrieMap map k a -> [([k], a)]
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> [([k], a)]
Base.toDescList

-- | @O(n m)@. Creates a map from a list of key-value pairs. If a key occurs
-- more than once, the value from the last pair (according to the list's order)
-- is the one which ends up in the map.
--
-- > fromList = fromListWith const
fromList :: Map map k => [([k],a)] -> TrieMap map k a
fromList :: forall (map :: * -> * -> *) k a.
Map map k =>
[([k], a)] -> TrieMap map k a
fromList = [([k], a)] -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[([k], a)] -> trie map k a
Base.fromList

-- | @O(n m)@. Like 'fromList', but the given function is used to determine the
-- final value if a key occurs more than once. The function is applied as
-- though it were flipped and then applied as a left fold over the values in
-- the given list's order. Or, equivalently (except as far as performance is
-- concerned), as though the function were applied as a right fold over the
-- values in the reverse of the given list's order. For example:
--
-- > fromListWith (-) [("a",1),("a",2),("a",3),("a",4)]
-- >    == fromList [("a",4-(3-(2-1)))]
-- >    == fromList [("a",2)]
fromListWith :: Map map k => (a -> a -> a) -> [([k],a)] -> TrieMap map k a
fromListWith :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a) -> [([k], a)] -> TrieMap map k a
fromListWith = (a -> a -> a) -> [([k], a)] -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
(a -> a -> a) -> [([k], a)] -> trie map k a
Base.fromListWith

-- | @O(n m)@. Like 'fromListWith', but the combining function is applied
-- strictly.
fromListWith' :: Map map k => (a -> a -> a) -> [([k],a)] -> TrieMap map k a
fromListWith' :: forall (map :: * -> * -> *) k a.
Map map k =>
(a -> a -> a) -> [([k], a)] -> TrieMap map k a
fromListWith' = (a -> a -> a) -> [([k], a)] -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
(a -> a -> a) -> [([k], a)] -> trie map k a
Base.fromListWith'

-- | @O(n m)@. Like 'fromListWith', but the key, in addition to the values to
-- be combined, is passed to the combining function.
fromListWithKey :: Map map k
                => ([k] -> a -> a -> a) -> [([k],a)] -> TrieMap map k a
fromListWithKey :: forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> a -> a) -> [([k], a)] -> TrieMap map k a
fromListWithKey = ([k] -> a -> a -> a) -> [([k], a)] -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
([k] -> a -> a -> a) -> [([k], a)] -> trie map k a
Base.fromListWithKey

-- | @O(n m)@. Like 'fromListWithKey', but the combining function is applied
-- strictly.
fromListWithKey' :: Map map k
                 => ([k] -> a -> a -> a) -> [([k],a)] -> TrieMap map k a
fromListWithKey' :: forall (map :: * -> * -> *) k a.
Map map k =>
([k] -> a -> a -> a) -> [([k], a)] -> TrieMap map k a
fromListWithKey' = ([k] -> a -> a -> a) -> [([k], a)] -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
([k] -> a -> a -> a) -> [([k], a)] -> trie map k a
Base.fromListWithKey'

-- * Ordering ops

-- | @O(m)@. Removes and returns the minimal key in the map, along with the
-- value associated with it. If the map is empty, 'Nothing' and the original
-- map are returned.
minView :: OrdMap map k => TrieMap map k a -> (Maybe ([k], a), TrieMap map k a)
minView :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
TrieMap map k a -> (Maybe ([k], a), TrieMap map k a)
minView = TrieMap map k a -> (Maybe ([k], a), TrieMap map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> (Maybe ([k], a), trie map k a)
Base.minView

-- | @O(m)@. Removes and returns the maximal key in the map, along with the
-- value associated with it. If the map is empty, 'Nothing' and the original
-- map are returned.
maxView :: OrdMap map k => TrieMap map k a -> (Maybe ([k], a), TrieMap map k a)
maxView :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
TrieMap map k a -> (Maybe ([k], a), TrieMap map k a)
maxView = TrieMap map k a -> (Maybe ([k], a), TrieMap map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> (Maybe ([k], a), trie map k a)
Base.maxView

-- | @O(m)@. Like 'fst' composed with 'minView'. 'Just' the minimal key in the
-- map and its associated value, or 'Nothing' if the map is empty.
findMin :: OrdMap map k => TrieMap map k a -> Maybe ([k], a)
findMin :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
TrieMap map k a -> Maybe ([k], a)
findMin = TrieMap map k a -> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> Maybe ([k], a)
Base.findMin

-- | @O(m)@. Like 'fst' composed with 'maxView'. 'Just' the minimal key in the
-- map and its associated value, or 'Nothing' if the map is empty.
findMax :: OrdMap map k => TrieMap map k a -> Maybe ([k], a)
findMax :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
TrieMap map k a -> Maybe ([k], a)
findMax = TrieMap map k a -> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> Maybe ([k], a)
Base.findMax

-- | @O(m)@. Like 'snd' composed with 'minView'. The map without its minimal
-- key, or the unchanged original map if it was empty.
deleteMin :: OrdMap map k => TrieMap map k a -> TrieMap map k a
deleteMin :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
TrieMap map k a -> TrieMap map k a
deleteMin = TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> trie map k a
Base.deleteMin

-- | @O(m)@. Like 'snd' composed with 'maxView'. The map without its maximal
-- key, or the unchanged original map if it was empty.
deleteMax :: OrdMap map k => TrieMap map k a -> TrieMap map k a
deleteMax :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
TrieMap map k a -> TrieMap map k a
deleteMax = TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
trie map k a -> trie map k a
Base.deleteMax

-- | @O(min(m,s))@. Splits the map in two about the given key. The first
-- element of the resulting pair is a map containing the keys lesser than the
-- given key; the second contains those keys that are greater.
split :: OrdMap map k
      => [k] -> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
split :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
[k] -> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
split = [k] -> TrieMap map k a -> (TrieMap map k a, TrieMap map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> (trie map k a, trie map k a)
Base.split

-- | @O(min(m,s))@. Like 'split', but also returns the value associated with
-- the given key, if any.
splitLookup :: OrdMap map k => [k]
                            -> TrieMap map k a
                            -> (TrieMap map k a, Maybe a, TrieMap map k a)
splitLookup :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
[k]
-> TrieMap map k a -> (TrieMap map k a, Maybe a, TrieMap map k a)
splitLookup = [k]
-> TrieMap map k a -> (TrieMap map k a, Maybe a, TrieMap map k a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> (trie map k a, st a, trie map k a)
Base.splitLookup

-- | @O(m)@. 'Just' the key of the map which precedes the given key in order,
-- along with its associated value, or 'Nothing' if the map is empty.
findPredecessor :: OrdMap map k => [k] -> TrieMap map k a -> Maybe ([k], a)
findPredecessor :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
[k] -> TrieMap map k a -> Maybe ([k], a)
findPredecessor = [k] -> TrieMap map k a -> Maybe ([k], a)
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> Maybe ([k], a)
Base.findPredecessor

-- | @O(m)@. 'Just' the key of the map which succeeds the given key in order,
-- along with its associated value, or 'Nothing' if the map is empty.
findSuccessor :: OrdMap map k => [k] -> TrieMap map k a -> Maybe ([k], a)
findSuccessor :: forall (map :: * -> * -> *) k a.
OrdMap map k =>
[k] -> TrieMap map k a -> Maybe ([k], a)
findSuccessor = [k] -> TrieMap map k a -> Maybe ([k], a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (map :: * -> * -> *)
       (st :: * -> *) k a.
(Boolable (st a), Trie trie st map k, OrdMap map k) =>
[k] -> trie map k a -> Maybe ([k], a)
Base.findSuccessor

-- * Trie-only operations

-- | @O(s)@. The map which contains all keys of which the given key is a
-- prefix. For example:
--
-- > lookupPrefix "ab" (fromList [("a",1),("ab",2),("ac",3),("abc",4)])
-- >    == fromList [("ab",2),("abc",4)]
lookupPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a
lookupPrefix :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> TrieMap map k a -> TrieMap map k a
lookupPrefix = [k] -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
Base.lookupPrefix

-- | @O(s)@. Prepends the given key to all the keys of the map. For example:
--
-- > addPrefix "xa" (fromList [("a",1),("b",2)])
-- >    == fromList [("xaa",1),("xab",2)]
addPrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a
addPrefix :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> TrieMap map k a -> TrieMap map k a
addPrefix = [k] -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
Base.addPrefix

-- | @O(s)@. The map which contains all keys of which the given key is a
-- prefix, with the prefix removed from each key. If the given key is not a
-- prefix of any key in the map, an empty map is returned. For example:
--
-- > deletePrefix "a" (fromList [("a",1),("ab",2),("ac",3)])
-- >    == fromList [("",1),("b",2),("c",3)]
--
-- This function can be used, for instance, to reduce potentially expensive I/O
-- operations: if you need to find the value in a map associated with a string,
-- but you only have a prefix of it and retrieving the rest is an expensive
-- operation, calling 'deletePrefix' with what you have might allow you to
-- avoid the operation: if the resulting map is empty, the entire string cannot
-- be a member of the map.
deletePrefix :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a
deletePrefix :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> TrieMap map k a -> TrieMap map k a
deletePrefix = [k] -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
Base.deletePrefix

-- | @O(s)@. Deletes all keys which are suffixes of the given key. For example:
--
-- > deleteSuffixes "ab" (fromList $ zip ["a","ab","ac","b","abc"] [1..])
-- >    == fromList [("a",1),("ac",3),("b",4)]
deleteSuffixes :: Map map k => [k] -> TrieMap map k a -> TrieMap map k a
deleteSuffixes :: forall (map :: * -> * -> *) k a.
Map map k =>
[k] -> TrieMap map k a -> TrieMap map k a
deleteSuffixes = [k] -> TrieMap map k a -> TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Boolable (st a), Trie trie st map k) =>
[k] -> trie map k a -> trie map k a
Base.deleteSuffixes

-- | @O(m)@. A triple containing the longest common prefix of all keys in the
-- map, the value associated with that prefix, if any, and the map with that
-- prefix removed from all the keys as well as the map itself. Examples:
--
-- > splitPrefix (fromList [("a",1),("b",2)])
-- >    == ("", Nothing, fromList [("a",1),("b",2)])
-- > splitPrefix (fromList [("a",1),("ab",2),("ac",3)])
-- >    == ("a", Just 1, fromList [("b",2),("c",3)])
splitPrefix :: Map map k => TrieMap map k a -> ([k], Maybe a, TrieMap map k a)
splitPrefix :: forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> ([k], Maybe a, TrieMap map k a)
splitPrefix = TrieMap map k a -> ([k], Maybe a, TrieMap map k a)
forall (trie :: (* -> * -> *) -> * -> * -> *) (map :: * -> * -> *)
       (st :: * -> *) k a.
(Alt st a, Trie trie st map k) =>
trie map k a -> ([k], st a, trie map k a)
Base.splitPrefix

-- | @O(m)@. The children of the longest common prefix in the trie as maps,
-- associated with their distinguishing key value. If the map contains less
-- than two keys, this function will return an empty map. Examples;
--
-- > children (fromList [("a",1),("abc",2),("abcd",3)])
-- >    == Map.fromList [('b',fromList [("c",2),("cd",3)])]
-- > children (fromList [("b",1),("c",2)])
-- >    == Map.fromList [('b',fromList [("",1)]),('c',fromList [("",2)])]
children :: Map map k => TrieMap map k a -> map k (TrieMap map k a)
children :: forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> map k (TrieMap map k a)
children = TrieMap map k a -> CMap TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Boolable (st a), Trie trie st map k) =>
trie map k a -> CMap trie map k a
Base.children

-- | @O(1)@. The children of the first element of the longest common prefix in
-- the trie as maps, associated with their distinguishing key value. If the map
-- contains less than two keys, this function will return an empty map.
--
-- If the longest common prefix of all keys in the trie is the empty list, this
-- function is equivalent to 'children'.
--
-- Examples:
--
-- > children1 (fromList [("abc",1),("abcd",2)])
-- >    == Map.fromList [('a',fromList [("bc",1),("bcd",2)])]
-- > children1 (fromList [("b",1),("c",2)])
-- >    == Map.fromList [('b',fromList [("",1)]),('c',fromList [("",2)])]
children1 :: Map map k => TrieMap map k a -> map k (TrieMap map k a)
children1 :: forall (map :: * -> * -> *) k a.
Map map k =>
TrieMap map k a -> map k (TrieMap map k a)
children1 = TrieMap map k a -> CMap TrieMap map k a
forall (st :: * -> *) a (trie :: (* -> * -> *) -> * -> * -> *)
       (map :: * -> * -> *) k.
(Alt st a, Trie trie st map k) =>
trie map k a -> CMap trie map k a
Base.children1

-- * Visualization

-- | @O(n m)@. Displays the map's internal structure in an undefined way. That
-- is to say, no program should depend on the function's results.
showTrie :: (Show k, Show a, Map map k) => TrieMap map k a -> ShowS
showTrie :: forall k a (map :: * -> * -> *).
(Show k, Show a, Map map k) =>
TrieMap map k a -> ShowS
showTrie = (Maybe a -> ShowS) -> TrieMap map k a -> ShowS
forall k (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) a.
(Show k, Trie trie st map k) =>
(st a -> ShowS) -> trie map k a -> ShowS
Base.showTrieWith ((Maybe a -> ShowS) -> TrieMap map k a -> ShowS)
-> (Maybe a -> ShowS) -> TrieMap map k a -> ShowS
forall a b. (a -> b) -> a -> b
$ \Maybe a
mv -> case Maybe a
mv of
                                           Maybe a
Nothing -> Char -> ShowS
showChar Char
' '
                                           Just a
v  -> Int -> a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 a
v

-- | @O(n m)@. Like 'showTrie', but uses the given function to display the
-- elements of the map. Still undefined.
showTrieWith :: (Show k, Map map k)
             => (Maybe a -> ShowS) -> TrieMap map k a -> ShowS
showTrieWith :: forall k (map :: * -> * -> *) a.
(Show k, Map map k) =>
(Maybe a -> ShowS) -> TrieMap map k a -> ShowS
showTrieWith = (Maybe a -> ShowS) -> TrieMap map k a -> ShowS
forall k (trie :: (* -> * -> *) -> * -> * -> *) (st :: * -> *)
       (map :: * -> * -> *) a.
(Show k, Trie trie st map k) =>
(st a -> ShowS) -> trie map k a -> ShowS
Base.showTrieWith