Data.GenericTrie

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 = DemoC1 Int | DemoC2 Int Char  deriving Generic

instance TrieKey Demo

Trie interface

newtype Trie k a

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.

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)

alter :: TrieKey k => k -> (Maybe a -> Maybe a) -> Trie k a -> Trie k a

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.

member :: TrieKey k => k -> Trie k a -> Bool

Returns True when the Trie has a value stored at the given key.

notMember :: TrieKey k => k -> Trie k a -> Bool

Returns False when the Trie has a value stored at the given key.

fromList :: TrieKey k => [(k, v)] -> Trie k v

Construct a trie from a list of key/value pairs

toList :: TrieKey k => Trie k a -> [(k, a)]

Transform Trie to an association list.

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

Keys that support prefix-trie map operations.

All operations 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

empty :: Trie k a

Construct an empty trie

trieNull :: Trie k a -> Bool

Test for an empty trie

lookup :: k -> Trie k a -> Maybe a

Lookup element from trie

insert :: k -> a -> Trie k a -> Trie k a

Insert element into trie

delete :: k -> Trie k a -> Trie k a

Delete element from trie

singleton :: 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

mapMaybeWithKey :: (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.

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

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)

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

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)

Manual ord key instance selector

newtype OrdKey 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.

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)

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)