{-# LANGUAGE Safe #-}
module Data.GenericTrie
(
Trie
, TrieKey
, ShowTrieKey
, empty
, singleton
, fromList
, fromListWith
, fromListWith'
, alter
, insert
, insertWith
, insertWith'
, delete
, at
, member
, notMember
, null
, lookup
, foldWithKey
, fold
, toList
, traverseWithKey
, traverseMaybeWithKey
, mapMaybe
, mapMaybeWithKey
, filter
, filterWithKey
, union
, unionWith
, unionWithKey
, intersection
, intersectionWith
, intersectionWithKey
, difference
, differenceWith
, differenceWithKey
, OrdKey(..)
) where
import Data.List (foldl')
import Data.Maybe (isNothing, isJust)
import Prelude hiding (lookup, null, filter)
import Data.GenericTrie.Internal
fromList :: TrieKey k => [(k,v)] -> Trie k v
fromList :: forall k v. TrieKey k => [(k, v)] -> Trie k v
fromList = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Trie k v
acc (k
k,v
v) -> forall k a. TrieKey k => k -> a -> Trie k a -> Trie k a
insert k
k v
v Trie k v
acc) forall k a. TrieKey k => Trie k a
empty
fromListWith :: TrieKey k => (v -> v -> v) -> [(k,v)] -> Trie k v
fromListWith :: forall k v. TrieKey k => (v -> v -> v) -> [(k, v)] -> Trie k v
fromListWith v -> v -> v
f = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Trie k v
acc (k
k,v
v) -> forall k v.
TrieKey k =>
(v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith v -> v -> v
f k
k v
v Trie k v
acc) forall k a. TrieKey k => Trie k a
empty
fromListWith' :: TrieKey k => (v -> v -> v) -> [(k,v)] -> Trie k v
fromListWith' :: forall k v. TrieKey k => (v -> v -> v) -> [(k, v)] -> Trie k v
fromListWith' v -> v -> v
f = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Trie k v
acc (k
k,v
v) -> forall k v.
TrieKey k =>
(v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith' v -> v -> v
f k
k v
v Trie k v
acc) forall k a. TrieKey k => Trie k a
empty
empty :: TrieKey k => Trie k a
empty :: forall k a. TrieKey k => Trie k a
empty = forall k a. TrieKey k => Trie k a
trieEmpty
{-# INLINE empty #-}
null :: TrieKey k => Trie k a -> Bool
null :: forall k a. TrieKey k => Trie k a -> Bool
null = forall k a. TrieKey k => Trie k a -> Bool
trieNull
{-# INLINE null #-}
lookup :: TrieKey k => k -> Trie k a -> Maybe a
lookup :: forall k a. TrieKey k => k -> Trie k a -> Maybe a
lookup = forall k a. TrieKey k => k -> Trie k a -> Maybe a
trieLookup
{-# INLINE lookup #-}
at :: (Functor f, TrieKey k) => k -> (Maybe a -> f (Maybe a)) -> Trie k a -> f (Trie k a)
at :: forall (f :: * -> *) k a.
(Functor f, TrieKey k) =>
k -> (Maybe a -> f (Maybe a)) -> Trie k a -> f (Trie k a)
at k
k Maybe a -> f (Maybe a)
f Trie k a
m = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Maybe a -> Trie k a
aux (Maybe a -> f (Maybe a)
f Maybe a
mv)
where
mv :: Maybe a
mv = forall k a. TrieKey k => k -> Trie k a -> Maybe a
lookup k
k Trie k a
m
aux :: Maybe a -> Trie k a
aux Maybe a
r = case Maybe a
r of
Maybe a
Nothing -> forall b a. b -> (a -> b) -> Maybe a -> b
maybe Trie k a
m (forall a b. a -> b -> a
const (forall k a. TrieKey k => k -> Trie k a -> Trie k a
delete k
k Trie k a
m)) Maybe a
mv
Just a
v' -> forall k a. TrieKey k => k -> a -> Trie k a -> Trie k a
insert k
k a
v' Trie k a
m
insert :: TrieKey k => k -> a -> Trie k a -> Trie k a
insert :: forall k a. TrieKey k => k -> a -> Trie k a -> Trie k a
insert = forall k a. TrieKey k => k -> a -> Trie k a -> Trie k a
trieInsert
{-# INLINE insert #-}
delete :: TrieKey k => k -> Trie k a -> Trie k a
delete :: forall k a. TrieKey k => k -> Trie k a -> Trie k a
delete = forall k a. TrieKey k => k -> Trie k a -> Trie k a
trieDelete
{-# INLINE delete #-}
singleton :: TrieKey k => k -> a -> Trie k a
singleton :: forall k a. TrieKey k => k -> a -> Trie k a
singleton = forall k a. TrieKey k => k -> a -> Trie k a
trieSingleton
{-# INLINE singleton #-}
mapMaybeWithKey :: TrieKey k => (k -> a -> Maybe b) -> Trie k a -> Trie k b
mapMaybeWithKey :: forall k a b.
TrieKey k =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
mapMaybeWithKey = forall k a b.
TrieKey k =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
trieMapMaybeWithKey
{-# INLINE mapMaybeWithKey #-}
traverseMaybeWithKey :: (TrieKey k, Applicative f)
=> (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
traverseMaybeWithKey :: forall k (f :: * -> *) a b.
(TrieKey k, Applicative f) =>
(k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
traverseMaybeWithKey = forall k (f :: * -> *) a b.
(TrieKey k, Applicative f) =>
(k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
trieTraverseMaybeWithKey
{-# INLINE traverseMaybeWithKey #-}
filter :: TrieKey k => (a -> Bool) -> Trie k a -> Trie k a
filter :: forall k a. TrieKey k => (a -> Bool) -> Trie k a -> Trie k a
filter a -> Bool
p = forall k a. TrieKey k => (k -> a -> Bool) -> Trie k a -> Trie k a
filterWithKey (forall a b. a -> b -> a
const a -> Bool
p)
filterWithKey :: TrieKey k => (k -> a -> Bool) -> Trie k a -> Trie k a
filterWithKey :: forall k a. TrieKey k => (k -> a -> Bool) -> Trie k a -> Trie k a
filterWithKey k -> a -> Bool
p = forall k a b.
TrieKey k =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
mapMaybeWithKey k -> a -> Maybe a
aux
where
aux :: k -> a -> Maybe a
aux k
k a
x
| k -> a -> Bool
p k
k a
x = forall a. a -> Maybe a
Just a
x
| Bool
otherwise = forall a. Maybe a
Nothing
fold :: TrieKey k => (a -> r -> r) -> r -> Trie k a -> r
fold :: forall k a r. TrieKey k => (a -> r -> r) -> r -> Trie k a -> r
fold = forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
trieFoldWithKey forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> b -> a
const
{-# INLINE fold #-}
foldWithKey :: TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
foldWithKey :: forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
foldWithKey = forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
trieFoldWithKey
{-# INLINE foldWithKey #-}
traverseWithKey :: (TrieKey k, Applicative f) => (k -> a -> f b) -> Trie k a -> f (Trie k b)
traverseWithKey :: forall k (f :: * -> *) a b.
(TrieKey k, Applicative f) =>
(k -> a -> f b) -> Trie k a -> f (Trie k b)
traverseWithKey = forall k (f :: * -> *) a b.
(TrieKey k, Applicative f) =>
(k -> a -> f b) -> Trie k a -> f (Trie k b)
trieTraverseWithKey
{-# INLINE traverseWithKey #-}
mergeWithKey ::
TrieKey k =>
(k -> a -> b -> Maybe c) ->
(Trie k a -> Trie k c) ->
(Trie k b -> Trie k c) ->
Trie k a -> Trie k b -> Trie k c
mergeWithKey :: forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
trieMergeWithKey
{-# INLINE mergeWithKey #-}
alter :: TrieKey k => k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
alter :: forall k a.
TrieKey k =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
alter = forall k a.
TrieKey k =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
trieAlter
{-# INLINE alter #-}
insertWith :: TrieKey k => (v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith :: forall k v.
TrieKey k =>
(v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith v -> v -> v
f k
k v
v = forall k a.
TrieKey k =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
alter k
k forall a b. (a -> b) -> a -> b
$ \Maybe v
mb ->
case Maybe v
mb of
Just v
v0 -> forall a. a -> Maybe a
Just (v -> v -> v
f v
v v
v0)
Maybe v
Nothing -> forall a. a -> Maybe a
Just v
v
insertWith' :: TrieKey k => (v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith' :: forall k v.
TrieKey k =>
(v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith' v -> v -> v
f k
k v
v = forall k a.
TrieKey k =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
alter k
k forall a b. (a -> b) -> a -> b
$ \Maybe v
mb ->
case Maybe v
mb of
Just v
v0 -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$! v -> v -> v
f v
v v
v0
Maybe v
Nothing -> forall a. a -> Maybe a
Just v
v
member :: TrieKey k => k -> Trie k a -> Bool
member :: forall k a. TrieKey k => k -> Trie k a -> Bool
member k
k Trie k a
t = forall a. Maybe a -> Bool
isJust (forall k a. TrieKey k => k -> Trie k a -> Maybe a
lookup k
k Trie k a
t)
notMember :: TrieKey k => k -> Trie k a -> Bool
notMember :: forall k a. TrieKey k => k -> Trie k a -> Bool
notMember k
k Trie k a
t = forall a. Maybe a -> Bool
isNothing (forall k a. TrieKey k => k -> Trie k a -> Maybe a
lookup k
k Trie k a
t)
union :: TrieKey k => Trie k a -> Trie k a -> Trie k a
union :: forall k a. TrieKey k => Trie k a -> Trie k a -> Trie k a
union = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey (\k
_ a
a a
_ -> forall a. a -> Maybe a
Just a
a) forall a. a -> a
id forall a. a -> a
id
unionWith :: TrieKey k => (a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
unionWith :: forall k a.
TrieKey k =>
(a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
unionWith a -> a -> a
f = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey (\k
_ a
a a
b -> forall a. a -> Maybe a
Just (a -> a -> a
f a
a a
b)) forall a. a -> a
id forall a. a -> a
id
unionWithKey :: TrieKey k => (k -> a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
unionWithKey :: forall k a.
TrieKey k =>
(k -> a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
unionWithKey k -> a -> a -> a
f = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey (\k
k a
a a
b -> forall a. a -> Maybe a
Just (k -> a -> a -> a
f k
k a
a a
b)) forall a. a -> a
id forall a. a -> a
id
intersection :: TrieKey k => Trie k a -> Trie k b -> Trie k a
intersection :: forall k a b. TrieKey k => Trie k a -> Trie k b -> Trie k a
intersection = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey (\k
_ a
a b
_ -> forall a. a -> Maybe a
Just a
a) (forall a b. a -> b -> a
const forall k a. TrieKey k => Trie k a
empty) (forall a b. a -> b -> a
const forall k a. TrieKey k => Trie k a
empty)
intersectionWith :: TrieKey k => (a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
intersectionWith :: forall k a b c.
TrieKey k =>
(a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
intersectionWith a -> b -> c
f = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey (\k
_ a
a b
b -> forall a. a -> Maybe a
Just (a -> b -> c
f a
a b
b)) (forall a b. a -> b -> a
const forall k a. TrieKey k => Trie k a
empty) (forall a b. a -> b -> a
const forall k a. TrieKey k => Trie k a
empty)
intersectionWithKey :: TrieKey k => (k -> a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
intersectionWithKey :: forall k a b c.
TrieKey k =>
(k -> a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
intersectionWithKey k -> a -> b -> c
f = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey (\k
k a
a b
b -> forall a. a -> Maybe a
Just (k -> a -> b -> c
f k
k a
a b
b)) (forall a b. a -> b -> a
const forall k a. TrieKey k => Trie k a
empty) (forall a b. a -> b -> a
const forall k a. TrieKey k => Trie k a
empty)
difference :: TrieKey k => Trie k a -> Trie k b -> Trie k a
difference :: forall k a b. TrieKey k => Trie k a -> Trie k b -> Trie k a
difference = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey (\k
_ a
_ b
_ -> forall a. Maybe a
Nothing) forall a. a -> a
id (forall a b. a -> b -> a
const forall k a. TrieKey k => Trie k a
empty)
differenceWith :: TrieKey k => (a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a
differenceWith :: forall k a b.
TrieKey k =>
(a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a
differenceWith a -> b -> Maybe a
f = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey (\k
_ -> a -> b -> Maybe a
f) forall a. a -> a
id (forall a b. a -> b -> a
const forall k a. TrieKey k => Trie k a
empty)
differenceWithKey :: TrieKey k => (k -> a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a
differenceWithKey :: forall k a b.
TrieKey k =>
(k -> a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a
differenceWithKey k -> a -> b -> Maybe a
f = forall k a b c.
TrieKey k =>
(k -> a -> b -> Maybe c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
mergeWithKey k -> a -> b -> Maybe a
f forall a. a -> a
id (forall a b. a -> b -> a
const forall k a. TrieKey k => Trie k a
empty)
mapMaybe :: TrieKey k => (a -> Maybe b) -> Trie k a -> Trie k b
mapMaybe :: forall k a b. TrieKey k => (a -> Maybe b) -> Trie k a -> Trie k b
mapMaybe a -> Maybe b
f = forall k a b.
TrieKey k =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
mapMaybeWithKey (\k
_ -> a -> Maybe b
f)