{-# 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 Control.Applicative (Applicative)
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 :: [(k, v)] -> Trie k v
fromList = (Trie k v -> (k, v) -> Trie k v)
-> Trie k v -> [(k, v)] -> Trie k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Trie k v
acc (k
k,v
v) -> k -> v -> Trie k v -> Trie k v
forall k a. TrieKey k => k -> a -> Trie k a -> Trie k a
insert k
k v
v Trie k v
acc) Trie k v
forall k a. TrieKey k => Trie k a
empty
fromListWith :: TrieKey k => (v -> v -> v) -> [(k,v)] -> Trie k v
fromListWith :: (v -> v -> v) -> [(k, v)] -> Trie k v
fromListWith v -> v -> v
f = (Trie k v -> (k, v) -> Trie k v)
-> Trie k v -> [(k, v)] -> Trie k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Trie k v
acc (k
k,v
v) -> (v -> v -> v) -> k -> v -> Trie k v -> Trie k 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) Trie k v
forall k a. TrieKey k => Trie k a
empty
fromListWith' :: TrieKey k => (v -> v -> v) -> [(k,v)] -> Trie k v
fromListWith' :: (v -> v -> v) -> [(k, v)] -> Trie k v
fromListWith' v -> v -> v
f = (Trie k v -> (k, v) -> Trie k v)
-> Trie k v -> [(k, v)] -> Trie k v
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Trie k v
acc (k
k,v
v) -> (v -> v -> v) -> k -> v -> Trie k v -> Trie k 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) Trie k v
forall k a. TrieKey k => Trie k a
empty
empty :: TrieKey k => Trie k a
empty :: Trie k a
empty = Trie k a
forall k a. TrieKey k => Trie k a
trieEmpty
{-# INLINE empty #-}
null :: TrieKey k => Trie k a -> Bool
null :: Trie k a -> Bool
null = Trie k a -> Bool
forall k a. TrieKey k => Trie k a -> Bool
trieNull
{-# INLINE null #-}
lookup :: TrieKey k => k -> Trie k a -> Maybe a
lookup :: k -> Trie k a -> Maybe a
lookup = k -> Trie k a -> Maybe a
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 :: 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 = (Maybe a -> Trie k a) -> f (Maybe a) -> f (Trie k a)
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 = k -> Trie k a -> Maybe a
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 -> Trie k a -> (a -> Trie k a) -> Maybe a -> Trie k a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Trie k a
m (Trie k a -> a -> Trie k a
forall a b. a -> b -> a
const (k -> Trie k a -> Trie k a
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' -> k -> a -> Trie k a -> Trie k a
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 :: k -> a -> Trie k a -> Trie k a
insert = k -> a -> Trie k a -> Trie k a
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 :: k -> Trie k a -> Trie k a
delete = k -> Trie k a -> Trie k a
forall k a. TrieKey k => k -> Trie k a -> Trie k a
trieDelete
{-# INLINE delete #-}
singleton :: TrieKey k => k -> a -> Trie k a
singleton :: k -> a -> Trie k a
singleton = k -> a -> Trie k a
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 :: (k -> a -> Maybe b) -> Trie k a -> Trie k b
mapMaybeWithKey = (k -> a -> Maybe b) -> Trie k a -> Trie k b
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 :: (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
traverseMaybeWithKey = (k -> a -> f (Maybe b)) -> Trie k a -> f (Trie k b)
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 :: (a -> Bool) -> Trie k a -> Trie k a
filter a -> Bool
p = (k -> a -> Bool) -> Trie k a -> Trie k a
forall k a. TrieKey k => (k -> a -> Bool) -> Trie k a -> Trie k a
filterWithKey ((a -> Bool) -> k -> a -> Bool
forall a b. a -> b -> a
const a -> Bool
p)
filterWithKey :: TrieKey k => (k -> a -> Bool) -> Trie k a -> Trie k a
filterWithKey :: (k -> a -> Bool) -> Trie k a -> Trie k a
filterWithKey k -> a -> Bool
p = (k -> a -> Maybe a) -> Trie k a -> Trie k a
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 = a -> Maybe a
forall a. a -> Maybe a
Just a
x
| Bool
otherwise = Maybe a
forall a. Maybe a
Nothing
fold :: TrieKey k => (a -> r -> r) -> r -> Trie k a -> r
fold :: (a -> r -> r) -> r -> Trie k a -> r
fold = (k -> a -> r -> r) -> r -> Trie k a -> r
forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
trieFoldWithKey ((k -> a -> r -> r) -> r -> Trie k a -> r)
-> ((a -> r -> r) -> k -> a -> r -> r)
-> (a -> r -> r)
-> r
-> Trie k a
-> r
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> r -> r) -> k -> a -> r -> r
forall a b. a -> b -> a
const
{-# INLINE fold #-}
foldWithKey :: TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
foldWithKey :: (k -> a -> r -> r) -> r -> Trie k a -> r
foldWithKey = (k -> a -> r -> r) -> r -> Trie k a -> r
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 :: (k -> a -> f b) -> Trie k a -> f (Trie k b)
traverseWithKey = (k -> a -> f b) -> Trie k a -> f (Trie k b)
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 :: (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 c)
-> (Trie k a -> Trie k c)
-> (Trie k b -> Trie k c)
-> Trie k a
-> Trie k b
-> Trie k c
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 :: k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
alter k
k Maybe a -> Maybe a
f Trie k a
t =
case Maybe a -> Maybe a
f (k -> Trie k a -> Maybe a
forall k a. TrieKey k => k -> Trie k a -> Maybe a
lookup k
k Trie k a
t) of
Just a
v' -> k -> a -> Trie k a -> Trie k a
forall k a. TrieKey k => k -> a -> Trie k a -> Trie k a
insert k
k a
v' Trie k a
t
Maybe a
Nothing -> k -> Trie k a -> Trie k a
forall k a. TrieKey k => k -> Trie k a -> Trie k a
delete k
k Trie k a
t
insertWith :: TrieKey k => (v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith :: (v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith v -> v -> v
f k
k v
v = k -> (Maybe v -> Maybe v) -> Trie k v -> Trie k v
forall k a.
TrieKey k =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
alter k
k ((Maybe v -> Maybe v) -> Trie k v -> Trie k v)
-> (Maybe v -> Maybe v) -> Trie k v -> Trie k v
forall a b. (a -> b) -> a -> b
$ \Maybe v
mb ->
case Maybe v
mb of
Just v
v0 -> v -> Maybe v
forall a. a -> Maybe a
Just (v -> v -> v
f v
v v
v0)
Maybe v
Nothing -> v -> Maybe v
forall a. a -> Maybe a
Just v
v
insertWith' :: TrieKey k => (v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith' :: (v -> v -> v) -> k -> v -> Trie k v -> Trie k v
insertWith' v -> v -> v
f k
k v
v = k -> (Maybe v -> Maybe v) -> Trie k v -> Trie k v
forall k a.
TrieKey k =>
k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
alter k
k ((Maybe v -> Maybe v) -> Trie k v -> Trie k v)
-> (Maybe v -> Maybe v) -> Trie k v -> Trie k v
forall a b. (a -> b) -> a -> b
$ \Maybe v
mb ->
case Maybe v
mb of
Just v
v0 -> v -> Maybe v
forall a. a -> Maybe a
Just (v -> Maybe v) -> v -> Maybe v
forall a b. (a -> b) -> a -> b
$! v -> v -> v
f v
v v
v0
Maybe v
Nothing -> v -> Maybe v
forall a. a -> Maybe a
Just v
v
member :: TrieKey k => k -> Trie k a -> Bool
member :: k -> Trie k a -> Bool
member k
k Trie k a
t = Maybe a -> Bool
forall a. Maybe a -> Bool
isJust (k -> Trie k a -> Maybe a
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 :: k -> Trie k a -> Bool
notMember k
k Trie k a
t = Maybe a -> Bool
forall a. Maybe a -> Bool
isNothing (k -> Trie k a -> Maybe a
forall k a. TrieKey k => k -> Trie k a -> Maybe a
lookup k
k Trie k a
t)
toList :: TrieKey k => Trie k a -> [(k,a)]
toList :: Trie k a -> [(k, a)]
toList = (k -> a -> [(k, a)] -> [(k, a)])
-> [(k, a)] -> Trie k a -> [(k, a)]
forall k a r. TrieKey k => (k -> a -> r -> r) -> r -> Trie k a -> r
foldWithKey (\k
k a
v [(k, a)]
xs -> (k
k,a
v) (k, a) -> [(k, a)] -> [(k, a)]
forall a. a -> [a] -> [a]
: [(k, a)]
xs) []
union :: TrieKey k => Trie k a -> Trie k a -> Trie k a
union :: Trie k a -> Trie k a -> Trie k a
union = (k -> a -> a -> Maybe a)
-> (Trie k a -> Trie k a)
-> (Trie k a -> Trie k a)
-> Trie k a
-> Trie k a
-> Trie k a
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
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
a) Trie k a -> Trie k a
forall a. a -> a
id Trie k a -> Trie k a
forall a. a -> a
id
unionWith :: TrieKey k => (a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
unionWith :: (a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
unionWith a -> a -> a
f = (k -> a -> a -> Maybe a)
-> (Trie k a -> Trie k a)
-> (Trie k a -> Trie k a)
-> Trie k a
-> Trie k a
-> Trie k a
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 -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> a -> a
f a
a a
b)) Trie k a -> Trie k a
forall a. a -> a
id Trie k a -> Trie k a
forall a. a -> a
id
unionWithKey :: TrieKey k => (k -> a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
unionWithKey :: (k -> a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
unionWithKey k -> a -> a -> a
f = (k -> a -> a -> Maybe a)
-> (Trie k a -> Trie k a)
-> (Trie k a -> Trie k a)
-> Trie k a
-> Trie k a
-> Trie k a
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 -> a -> Maybe a
forall a. a -> Maybe a
Just (k -> a -> a -> a
f k
k a
a a
b)) Trie k a -> Trie k a
forall a. a -> a
id Trie k a -> Trie k a
forall a. a -> a
id
intersection :: TrieKey k => Trie k a -> Trie k b -> Trie k a
intersection :: Trie k a -> Trie k b -> Trie k a
intersection = (k -> a -> b -> Maybe a)
-> (Trie k a -> Trie k a)
-> (Trie k b -> Trie k a)
-> Trie k a
-> Trie k b
-> Trie k a
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
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
a) (Trie k a -> Trie k a -> Trie k a
forall a b. a -> b -> a
const Trie k a
forall k a. TrieKey k => Trie k a
empty) (Trie k a -> Trie k b -> Trie k a
forall a b. a -> b -> a
const Trie k a
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 :: (a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
intersectionWith a -> b -> c
f = (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
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 -> c -> Maybe c
forall a. a -> Maybe a
Just (a -> b -> c
f a
a b
b)) (Trie k c -> Trie k a -> Trie k c
forall a b. a -> b -> a
const Trie k c
forall k a. TrieKey k => Trie k a
empty) (Trie k c -> Trie k b -> Trie k c
forall a b. a -> b -> a
const Trie k c
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 :: (k -> a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
intersectionWithKey k -> a -> b -> c
f = (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
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 -> c -> Maybe c
forall a. a -> Maybe a
Just (k -> a -> b -> c
f k
k a
a b
b)) (Trie k c -> Trie k a -> Trie k c
forall a b. a -> b -> a
const Trie k c
forall k a. TrieKey k => Trie k a
empty) (Trie k c -> Trie k b -> Trie k c
forall a b. a -> b -> a
const Trie k c
forall k a. TrieKey k => Trie k a
empty)
difference :: TrieKey k => Trie k a -> Trie k b -> Trie k a
difference :: Trie k a -> Trie k b -> Trie k a
difference = (k -> a -> b -> Maybe a)
-> (Trie k a -> Trie k a)
-> (Trie k b -> Trie k a)
-> Trie k a
-> Trie k b
-> Trie k a
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
forall a. Maybe a
Nothing) Trie k a -> Trie k a
forall a. a -> a
id (Trie k a -> Trie k b -> Trie k a
forall a b. a -> b -> a
const Trie k a
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 :: (a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a
differenceWith a -> b -> Maybe a
f = (k -> a -> b -> Maybe a)
-> (Trie k a -> Trie k a)
-> (Trie k b -> Trie k a)
-> Trie k a
-> Trie k b
-> Trie k a
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) Trie k a -> Trie k a
forall a. a -> a
id (Trie k a -> Trie k b -> Trie k a
forall a b. a -> b -> a
const Trie k a
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 :: (k -> a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a
differenceWithKey k -> a -> b -> Maybe a
f = (k -> a -> b -> Maybe a)
-> (Trie k a -> Trie k a)
-> (Trie k b -> Trie k a)
-> Trie k a
-> Trie k b
-> Trie k a
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 Trie k a -> Trie k a
forall a. a -> a
id (Trie k a -> Trie k b -> Trie k a
forall a b. a -> b -> a
const Trie k a
forall k a. TrieKey k => Trie k a
empty)
mapMaybe :: TrieKey k => (a -> Maybe b) -> Trie k a -> Trie k b
mapMaybe :: (a -> Maybe b) -> Trie k a -> Trie k b
mapMaybe a -> Maybe b
f = (k -> a -> Maybe b) -> Trie k a -> Trie k b
forall k a b.
TrieKey k =>
(k -> a -> Maybe b) -> Trie k a -> Trie k b
mapMaybeWithKey (\k
_ -> a -> Maybe b
f)