Data.GenericTrie.Internal

Unstable implementation details

Documentation

class TrieKey k where

Types that may be used as the key of a Trie.

For data delcarations, the instance can be automatically derived from a Generic instance.

Minimal complete definition

Nothing

Associated Types

type TrieRep k :: * -> *

Type of the representation of tries for this key.

Methods

trieEmpty :: Trie k a

Construct an empty trie

trieNull :: Trie k a -> Bool

Test for an empty trie

trieLookup :: k -> Trie k a -> Maybe a

Lookup element from trie

trieInsert :: k -> a -> Trie k a -> Trie k a

Insert element into trie

trieDelete :: k -> Trie k a -> Trie k a

Delete element from trie

trieAt :: Functor f => k -> (Maybe a -> f (Maybe a)) -> Trie k a -> f (Trie k a)

trieSingleton :: k -> a -> Trie k a

Construct a trie holding a single value

trieMap :: (a -> b) -> Trie k a -> Trie k b

Apply a function to all values stored in a trie

trieTraverse :: Applicative f => (a -> f b) -> Trie k a -> f (Trie k b)

Traverse the values stored in a trie

trieShowsPrec :: Show a => Int -> Trie k a -> ShowS

Show the representation of a trie

trieMapMaybeWithKey :: (k -> a -> Maybe b) -> Trie k a -> Trie k b

Apply a function to the values of a Trie and keep the elements of the trie that result in a Just value.

trieFoldWithKey :: (k -> a -> r -> r) -> r -> Trie k a -> r

Fold a trie with a function of both key and value.

trieTraverseWithKey :: Applicative f => (k -> a -> f b) -> Trie k a -> f (Trie k b)

Traverse a trie with a function of both key and value.

trieMergeWithKey :: (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

Instances

TrieKey Bool

TrieKey Char

Char tries are implemented with IntMap.

TrieKey Int

Int tries are implemented with IntMap.

TrieKey Integer

Integer tries are implemented with Map.

TrieKey ()

TrieKey k => TrieKey [k]

TrieKey k => TrieKey (Maybe k)

(Show k, Ord k) => TrieKey (OrdKey k)

OrdKey tries are implemented with Map, this is intended for cases where it is better for some reason to force the use of a Map than to use the generically derived structure.

(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)

(TrieKey a, TrieKey b, TrieKey c, TrieKey d) => TrieKey (a, b, c, d)

(TrieKey a, TrieKey b, TrieKey c, TrieKey d, TrieKey e) => TrieKey (a, b, c, d, e)

newtype Trie k a

A map from keys of type k, to values of type a.

Constructors

MkTrie (TrieRep k a)

Instances

TrieKey k => Functor (Trie k)

TrieKey k => Foldable (Trie k)

TrieKey k => Traversable (Trie k)

(Show a, TrieKey k) => Show (Trie k a)

newtype OrdKey k

Tries indexed by OrdKey will be represented as an ordinary Map and the keys will be compared based on the Ord instance for k.

Constructors

OrdKey

Fields

getOrdKey :: k

Instances

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)

OrdKey tries are implemented with Map, this is intended for cases where it is better for some reason to force the use of a Map than to use the generically derived structure.

type TrieRep (OrdKey k) = Map k

Generic derivation implementation

genericTrieNull :: (TrieRep k ~ TrieRepDefault k) => Trie k a -> Bool

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

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)

Generic implementation of trieTraverse. This is the default implementation.

genericTrieShowsPrec :: (Show a, GTrieKeyShow (Rep k), TrieRep k ~ TrieRepDefault k) => Int -> Trie k a -> ShowS

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

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

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

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

Generic implementation of mapMaybe. This is the default implementation.

genericSingleton :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => k -> a -> Trie k a

Generic implementation of singleton. This is the default implementation.

genericEmpty :: (TrieRep k ~ TrieRepDefault k) => Trie k a

Generic implementation of empty. This is the default implementation.

genericAt :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k, Functor f) => k -> (Maybe a -> f (Maybe a)) -> Trie k a -> f (Trie k a)

Generic implementation of insert. This is the default implementation.

genericFoldWithKey :: (GTrieKey (Rep k), Generic k, TrieRep k ~ TrieRepDefault k) => (k -> a -> r -> r) -> r -> Trie k a -> r

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)

Generic implementation of traverseWithKey. This is the default implementation.

type TrieRepDefault k = Compose Maybe (GTrie (Rep k))

The default implementation of a TrieRep is GTrie wrapped in a Maybe. This wrapping is due to the GTrie being a non-empty trie allowing all the of the "emptiness" to be represented at the top level for any given generically implemented key.

class GTrieKey f where

TrieKey operations on Generic representations used to provide the default implementations of tries.

Methods

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)

gtrieAt :: Functor m => (Maybe (GTrie f a) -> r) -> f p -> (Maybe a -> m (Maybe a)) -> GTrie f a -> m r

Instances

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.

data family GTrie f a

Mapping of generic representation of keys to trie structures.

Instances

GTrieKey f => Functor (GTrie f)

(Show a, GTrieKeyShow f) => Show (GTrie f a)

data GTrie V1

data GTrie U1 = UTrie a

data GTrie (K1 i k) = KTrie (Trie k a)

data GTrie ((:+:) f g)

• = STrieL !(GTrie f a)
• | STrieR !(GTrie g a)
• | STrieB !(GTrie f a) !(GTrie g a)

data GTrie ((:*:) f g) = PTrie (GTrie f (GTrie g a))

data GTrie (M1 i c f) = MTrie (GTrie f a)