Safe Haskell | None |
---|---|
Language | Haskell2010 |
This module implements an interface for working with "tries". A key in the trie represents a distinct path through the trie. This can provide benefits when using very large and possibly very similar keys where comparing for order can become expensive, and storing the various keys could be inefficient.
For primitive types like Int
, this library will select efficient
implementations automatically.
All methods of TrieKey
can be derived automatically using
a Generic
instance.
data Demo = DemoC1Int
| DemoC2Int
Char
derivingGeneric
instanceTrieKey
Demo
- newtype Trie k a = MkTrie (TrieRep k a)
- alter :: TrieKey k => k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a
- member :: TrieKey k => k -> Trie k a -> Bool
- notMember :: TrieKey k => k -> Trie k a -> Bool
- fromList :: TrieKey k => [(k, v)] -> Trie k v
- toList :: TrieKey k => Trie k a -> [(k, a)]
- mapMaybe :: TrieKey k => (a -> Maybe b) -> Trie k a -> Trie k b
- union :: TrieKey k => Trie k a -> Trie k a -> Trie k a
- unionWith :: TrieKey k => (a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
- unionWithKey :: TrieKey k => (k -> a -> a -> a) -> Trie k a -> Trie k a -> Trie k a
- intersection :: TrieKey k => Trie k a -> Trie k b -> Trie k a
- intersectionWith :: TrieKey k => (a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
- intersectionWithKey :: TrieKey k => (k -> a -> b -> c) -> Trie k a -> Trie k b -> Trie k c
- difference :: TrieKey k => Trie k a -> Trie k b -> Trie k a
- differenceWith :: TrieKey k => (a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a
- differenceWithKey :: TrieKey k => (k -> a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a
- class TrieKey k where
- type TrieRep k :: * -> *
- empty :: Trie k a
- trieNull :: Trie k a -> Bool
- lookup :: k -> Trie k a -> Maybe a
- insert :: k -> a -> Trie k a -> Trie k a
- delete :: k -> Trie k a -> Trie k a
- singleton :: k -> a -> Trie k a
- trieMap :: (a -> b) -> Trie k a -> Trie k b
- trieTraverse :: Applicative f => (a -> f b) -> Trie k a -> f (Trie k b)
- trieShowsPrec :: Show a => Int -> Trie k a -> ShowS
- mapMaybeWithKey :: (k -> a -> Maybe b) -> Trie k a -> Trie k b
- foldWithKey :: (k -> a -> r -> r) -> r -> Trie k a -> r
- traverseWithKey :: Applicative f => (k -> a -> f b) -> Trie k a -> f (Trie k b)
- 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
- newtype OrdKey k = OrdKey {
- getOrdKey :: k
- genericTrieNull :: (TrieRep k ~ TrieRepDefault k) => Trie k a -> Bool
- genericTrieMap :: (GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k) => (a -> b) -> Trie k a -> Trie k b
- genericTrieTraverse :: (GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k, Applicative f) => (a -> f b) -> Trie k a -> f (Trie k b)
- genericTrieShowsPrec :: (Show a, GTrieKeyShow (Rep k), TrieRep k ~ TrieRepDefault k) => Int -> Trie k a -> ShowS
- genericInsert :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> a -> Trie k a -> Trie k a
- genericLookup :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> Trie k a -> Maybe a
- genericDelete :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> Trie k a -> Trie k a
- genericMapMaybeWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => (k -> a -> Maybe b) -> Trie k a -> Trie k b
- genericSingleton :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> a -> Trie k a
- genericEmpty :: (TrieRep k ~ TrieRepDefault k) => Trie k a
- genericFoldWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => (k -> a -> r -> r) -> r -> Trie k a -> r
- genericTraverseWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k, Applicative f) => (k -> a -> f b) -> Trie k a -> f (Trie k b)
- type TrieRepDefault k = Compose Maybe (GTrie (Rep k))
- class GTrieKey f where
- gtrieLookup :: f p -> GTrie f a -> Maybe a
- gtrieInsert :: f p -> a -> GTrie f a -> GTrie f a
- gtrieSingleton :: f p -> a -> GTrie f a
- gtrieDelete :: f p -> GTrie f a -> Maybe (GTrie f a)
- gtrieMap :: (a -> b) -> GTrie f a -> GTrie f b
- gtrieTraverse :: Applicative m => (a -> m b) -> GTrie f a -> m (GTrie f b)
- gmapMaybeWithKey :: (f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b)
- gfoldWithKey :: (f p -> a -> r -> r) -> r -> GTrie f a -> r
- gtraverseWithKey :: Applicative m => (f p -> a -> m b) -> GTrie f a -> m (GTrie f b)
- gmergeWithKey :: (f p -> a -> b -> Maybe c) -> (GTrie f a -> Maybe (GTrie f c)) -> (GTrie f b -> Maybe (GTrie f c)) -> GTrie f a -> GTrie f b -> Maybe (GTrie f c)
- data family GTrie f a
Trie interface
Effectively an associated datatype of tries indexable by keys of type k
.
By using a separate newtype wrapper around the associated type synonym we're
able to use the same MkTrie
constructor for all of the generic
implementations while still getting the injectivity of a new type.
alter :: TrieKey k => k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a Source
Alter the values of a trie. The function will take the value stored as the given key if one exists and should return a value to insert at that location or Nothing to delete from that location.
differenceWithKey :: TrieKey k => (k -> a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a Source
Keys that support prefix-trie map operations.
All operations can be automatically derived from a Generic
instance.
Nothing
Construct an empty trie
trieNull :: Trie k a -> Bool Source
Test for an empty trie
lookup :: k -> Trie k a -> Maybe a Source
Lookup element from trie
insert :: k -> a -> Trie k a -> Trie k a Source
Insert element into trie
delete :: k -> Trie k a -> Trie k a Source
Delete element from trie
singleton :: k -> a -> Trie k a Source
Construct a trie holding a single value
trieMap :: (a -> b) -> Trie k a -> Trie k b Source
Apply a function to all values stored in a trie
trieTraverse :: Applicative f => (a -> f b) -> Trie k a -> f (Trie k b) Source
Traverse the values stored in a trie
trieShowsPrec :: Show a => Int -> Trie k a -> ShowS Source
Show the representation of a trie
mapMaybeWithKey :: (k -> a -> Maybe b) -> Trie k a -> Trie k b Source
Apply a function to the values of a Trie
and keep the elements
of the trie that result in a Just
value.
foldWithKey :: (k -> a -> r -> r) -> r -> Trie k a -> r Source
Fold a trie with a function of both key and value.
traverseWithKey :: Applicative f => (k -> a -> f b) -> Trie k a -> f (Trie k b) Source
Traverse a trie with a function of both key and value.
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 Source
TrieKey Bool | |
TrieKey Char | 'Char tries are implemented with |
TrieKey Int | |
TrieKey Integer | |
TrieKey () | |
TrieKey k => TrieKey [k] | |
TrieKey k => TrieKey (Maybe k) | |
(Show k, Ord k) => TrieKey (OrdKey k) |
|
(TrieKey a, TrieKey b) => TrieKey (Either a b) | |
(TrieKey a, TrieKey b) => TrieKey (a, b) | |
(TrieKey a, TrieKey b, TrieKey c) => TrieKey (a, b, c) |
Manual ord key instance selector
Eq k => Eq (OrdKey k) | |
Ord k => Ord (OrdKey k) | |
Read k => Read (OrdKey k) | |
Show k => Show (OrdKey k) | |
(Show k, Ord k) => TrieKey (OrdKey k) |
|
type TrieRep (OrdKey k) = Map k |
Generic derivation implementation
genericTrieNull :: (TrieRep k ~ TrieRepDefault k) => Trie k a -> Bool Source
Generic implementation of trieNull
. This is the default implementation.
genericTrieMap :: (GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k) => (a -> b) -> Trie k a -> Trie k b Source
Generic implementation of trieMap
. This is the default implementation.
genericTrieTraverse :: (GTrieKey (Rep k), TrieRep k ~ TrieRepDefault k, Applicative f) => (a -> f b) -> Trie k a -> f (Trie k b) Source
Generic implementation of trieTraverse
. This is the default implementation.
genericTrieShowsPrec :: (Show a, GTrieKeyShow (Rep k), TrieRep k ~ TrieRepDefault k) => Int -> Trie k a -> ShowS Source
Generic implementation of trieShowsPrec
. This is the default implementation.
genericInsert :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> a -> Trie k a -> Trie k a Source
Generic implementation of insert
. This is the default implementation.
genericLookup :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> Trie k a -> Maybe a Source
Generic implementation of lookup
. This is the default implementation.
genericDelete :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> Trie k a -> Trie k a Source
Generic implementation of delete
. This is the default implementation.
genericMapMaybeWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => (k -> a -> Maybe b) -> Trie k a -> Trie k b Source
Generic implementation of mapMaybe
. This is the default implementation.
genericSingleton :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> a -> Trie k a Source
Generic implementation of singleton
. This is the default implementation.
genericEmpty :: (TrieRep k ~ TrieRepDefault k) => Trie k a Source
Generic implementation of empty
. This is the default implementation.
genericFoldWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => (k -> a -> r -> r) -> r -> Trie k a -> r Source
Generic implementation of foldWithKey
. This is the default implementation.
genericTraverseWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k, Applicative f) => (k -> a -> f b) -> Trie k a -> f (Trie k b) Source
Generic implementation of traverseWithKey
. This is the default implementation.
TrieKey operations on Generic representations used to provide the default implementations of tries.
gtrieLookup :: f p -> GTrie f a -> Maybe a Source
gtrieInsert :: f p -> a -> GTrie f a -> GTrie f a Source
gtrieSingleton :: f p -> a -> GTrie f a Source
gtrieDelete :: f p -> GTrie f a -> Maybe (GTrie f a) Source
gtrieMap :: (a -> b) -> GTrie f a -> GTrie f b Source
gtrieTraverse :: Applicative m => (a -> m b) -> GTrie f a -> m (GTrie f b) Source
gmapMaybeWithKey :: (f p -> a -> Maybe b) -> GTrie f a -> Maybe (GTrie f b) Source
gfoldWithKey :: (f p -> a -> r -> r) -> r -> GTrie f a -> r Source
gtraverseWithKey :: Applicative m => (f p -> a -> m b) -> GTrie f a -> m (GTrie f b) Source
gmergeWithKey :: (f p -> a -> b -> Maybe c) -> (GTrie f a -> Maybe (GTrie f c)) -> (GTrie f b -> Maybe (GTrie f c)) -> GTrie f a -> GTrie f b -> Maybe (GTrie f c) Source
GTrieKey V1 | Tries of types without constructors are represented by a unit. |
GTrieKey U1 | Tries of constructors without fields are represented by a single value. |
TrieKey k => GTrieKey (K1 i k) | Generic fields are represented by tries of the field type. |
(GTrieKey f, GTrieKey g) => GTrieKey ((:+:) f g) | Generic sums are represented by up to a pair of sub-tries. |
(GTrieKey f, GTrieKey g) => GTrieKey ((:*:) f g) | Generic products are represented by tries of tries. |
GTrieKey f => GTrieKey (M1 i c f) | Generic metadata is skipped in trie representation and operations. |
Mapping of generic representation of keys to trie structures.