{-# OPTIONS_GHC -Wall -fwarn-tabs #-}
{-# LANGUAGE CPP #-}
#if __GLASGOW_HASKELL__ >= 701
{-# LANGUAGE Safe #-}
#endif
module Data.Trie.Convenience
(
fromListL, fromListR, fromListS
, fromListWith, fromListWith'
, fromListWithL, fromListWithL'
, lookupWithDefault
, insertIfAbsent
, insertWith, insertWith'
, insertWithKey, insertWithKey'
, adjustWithKey
, update, updateWithKey
, disunion
, unionWith, unionWith'
, intersectWith, intersectWith'
) where
import Data.Trie
import Data.Trie.Internal (lookupBy_, alterBy_)
import Data.ByteString (ByteString)
import Data.List (foldl', sortBy)
import Data.Ord (comparing)
fromListL :: [(ByteString,a)] -> Trie a
{-# INLINE fromListL #-}
fromListL :: forall a. [(ByteString, a)] -> Trie a
fromListL = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a b. (a -> b) -> a -> b
$ forall a. ByteString -> a -> Trie a -> Trie a
insertIfAbsent) forall a. Trie a
empty
fromListR :: [(ByteString,a)] -> Trie a
{-# INLINE fromListR #-}
fromListR :: forall a. [(ByteString, a)] -> Trie a
fromListR = forall a. [(ByteString, a)] -> Trie a
fromList
fromListS :: [(ByteString,a)] -> Trie a
{-# INLINE fromListS #-}
fromListS :: forall a. [(ByteString, a)] -> Trie a
fromListS = forall a. [(ByteString, a)] -> Trie a
fromListR forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing forall a b. (a, b) -> a
fst)
fromListWith :: (a -> a -> a) -> [(ByteString,a)] -> Trie a
{-# INLINE fromListWith #-}
fromListWith :: forall a. (a -> a -> a) -> [(ByteString, a)] -> Trie a
fromListWith a -> a -> a
f = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a b. (a -> b) -> a -> b
$ forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy forall {p}. p -> a -> Maybe a -> Maybe a
g) forall a. Trie a
empty
where
g :: p -> a -> Maybe a -> Maybe a
g p
_ a
v Maybe a
Nothing = forall a. a -> Maybe a
Just a
v
g p
_ a
v (Just a
w) = forall a. a -> Maybe a
Just (a -> a -> a
f a
v a
w)
fromListWith' :: (a -> a -> a) -> [(ByteString,a)] -> Trie a
{-# INLINE fromListWith' #-}
fromListWith' :: forall a. (a -> a -> a) -> [(ByteString, a)] -> Trie a
fromListWith' a -> a -> a
f = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a b. (a -> b) -> a -> b
$ forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy forall {p}. p -> a -> Maybe a -> Maybe a
g') forall a. Trie a
empty
where
g' :: p -> a -> Maybe a -> Maybe a
g' p
_ a
v Maybe a
Nothing = forall a. a -> Maybe a
Just a
v
g' p
_ a
v (Just a
w) = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
v a
w
fromListWithL :: (a -> a -> a) -> [(ByteString,a)] -> Trie a
{-# INLINE fromListWithL #-}
fromListWithL :: forall a. (a -> a -> a) -> [(ByteString, a)] -> Trie a
fromListWithL a -> a -> a
f = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a b. (a -> b) -> a -> b
$ forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy forall {p}. p -> a -> Maybe a -> Maybe a
flipG) forall a. Trie a
empty
where
flipG :: p -> a -> Maybe a -> Maybe a
flipG p
_ a
v Maybe a
Nothing = forall a. a -> Maybe a
Just a
v
flipG p
_ a
v (Just a
w) = forall a. a -> Maybe a
Just (a -> a -> a
f a
w a
v)
fromListWithL' :: (a -> a -> a) -> [(ByteString,a)] -> Trie a
{-# INLINE fromListWithL' #-}
fromListWithL' :: forall a. (a -> a -> a) -> [(ByteString, a)] -> Trie a
fromListWithL' a -> a -> a
f = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry forall a b. (a -> b) -> a -> b
$ forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy forall {p}. p -> a -> Maybe a -> Maybe a
flipG') forall a. Trie a
empty
where
flipG' :: p -> a -> Maybe a -> Maybe a
flipG' p
_ a
v Maybe a
Nothing = forall a. a -> Maybe a
Just a
v
flipG' p
_ a
v (Just a
w) = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
w a
v
lookupWithDefault :: a -> ByteString -> Trie a -> a
lookupWithDefault :: forall a. a -> ByteString -> Trie a -> a
lookupWithDefault a
def = forall a b.
(a -> Trie a -> b)
-> (Trie a -> b) -> b -> ByteString -> Trie a -> b
lookupBy_ forall a b. a -> b -> a
const (forall a b. a -> b -> a
const a
def) a
def
insertIfAbsent :: ByteString -> a -> Trie a -> Trie a
insertIfAbsent :: forall a. ByteString -> a -> Trie a -> Trie a
insertIfAbsent =
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy forall a b. (a -> b) -> a -> b
$ \ByteString
_ a
x Maybe a
mv ->
case Maybe a
mv of
Maybe a
Nothing -> forall a. a -> Maybe a
Just a
x
Just a
_ -> Maybe a
mv
insertWith :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWith :: forall a. (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWith a -> a -> a
f =
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy forall a b. (a -> b) -> a -> b
$ \ByteString
_ a
x Maybe a
mv ->
case Maybe a
mv of
Maybe a
Nothing -> forall a. a -> Maybe a
Just a
x
Just a
v -> forall a. a -> Maybe a
Just (a -> a -> a
f a
x a
v)
insertWith' :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWith' :: forall a. (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWith' a -> a -> a
f =
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy forall a b. (a -> b) -> a -> b
$ \ByteString
_ a
x Maybe a
mv ->
case Maybe a
mv of
Maybe a
Nothing -> forall a. a -> Maybe a
Just a
x
Just a
v -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
x a
v
insertWithKey :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWithKey :: forall a.
(ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWithKey ByteString -> a -> a -> a
f =
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy forall a b. (a -> b) -> a -> b
$ \ByteString
k a
x Maybe a
mv ->
case Maybe a
mv of
Maybe a
Nothing -> forall a. a -> Maybe a
Just a
x
Just a
v -> forall a. a -> Maybe a
Just (ByteString -> a -> a -> a
f ByteString
k a
x a
v)
insertWithKey' :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWithKey' :: forall a.
(ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWithKey' ByteString -> a -> a -> a
f =
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy forall a b. (a -> b) -> a -> b
$ \ByteString
k a
x Maybe a
mv ->
case Maybe a
mv of
Maybe a
Nothing -> forall a. a -> Maybe a
Just a
x
Just a
v -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! ByteString -> a -> a -> a
f ByteString
k a
x a
v
adjustWithKey :: (ByteString -> a -> a) -> ByteString -> Trie a -> Trie a
adjustWithKey :: forall a. (ByteString -> a -> a) -> ByteString -> Trie a -> Trie a
adjustWithKey ByteString -> a -> a
f ByteString
q = forall a. (a -> a) -> ByteString -> Trie a -> Trie a
adjust (ByteString -> a -> a
f ByteString
q) ByteString
q
update :: (a -> Maybe a) -> ByteString -> Trie a -> Trie a
update :: forall a. (a -> Maybe a) -> ByteString -> Trie a -> Trie a
update a -> Maybe a
f ByteString
q = forall a.
(Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
alterBy_ (\Maybe a
mx Trie a
t -> (Maybe a
mx forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Maybe a
f, Trie a
t)) ByteString
q
updateWithKey :: (ByteString -> a -> Maybe a) -> ByteString -> Trie a -> Trie a
updateWithKey :: forall a.
(ByteString -> a -> Maybe a) -> ByteString -> Trie a -> Trie a
updateWithKey ByteString -> a -> Maybe a
f ByteString
q = forall a.
(Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
alterBy_ (\Maybe a
mx Trie a
t -> (Maybe a
mx forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ByteString -> a -> Maybe a
f ByteString
q, Trie a
t)) ByteString
q
disunion :: Trie a -> Trie a -> Trie a
disunion :: forall a. Trie a -> Trie a -> Trie a
disunion = forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
_ a
_ -> forall a. Maybe a
Nothing)
unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith :: forall a. (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith a -> a -> a
f = forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
x a
y -> forall a. a -> Maybe a
Just (a -> a -> a
f a
x a
y))
unionWith' :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith' :: forall a. (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith' a -> a -> a
f = forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
x a
y -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
x a
y)
intersectWith :: (a -> b -> c) -> Trie a -> Trie b -> Trie c
intersectWith :: forall a b c. (a -> b -> c) -> Trie a -> Trie b -> Trie c
intersectWith a -> b -> c
f = forall a b c. (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
intersectBy (\a
x b
y -> forall a. a -> Maybe a
Just (a -> b -> c
f a
x b
y))
intersectWith' :: (a -> b -> c) -> Trie a -> Trie b -> Trie c
intersectWith' :: forall a b c. (a -> b -> c) -> Trie a -> Trie b -> Trie c
intersectWith' a -> b -> c
f = forall a b c. (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
intersectBy (\a
x b
y -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! a -> b -> c
f a
x b
y)