Data.GenericTrie

This module implements an interface for working with maps.

For primitive types, like Int, the library automatically selects an efficient implementation (e.g., an IntMap).

For complex structured types, the library uses an implementation based on tries: this is useful when using large and similar keys where comparing for order may become expensive, and storing the distinct keys would be inefficient.

The OrdKey type allows for maps with complex keys, where the keys are compared based on order, rather than using the trie implementation.

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

data Trie k a

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

Instances

TrieKey k => Functor (Trie k)

Methods

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

(<$) :: a -> Trie k b -> Trie k a

TrieKey k => Foldable (Trie k)

Methods

fold :: Monoid m => Trie k m -> m

foldMap :: Monoid m => (a -> m) -> Trie k a -> m

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

foldr' :: (a -> b -> b) -> b -> Trie k a -> b

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

foldl' :: (b -> a -> b) -> b -> Trie k a -> b

foldr1 :: (a -> a -> a) -> Trie k a -> a

foldl1 :: (a -> a -> a) -> Trie k a -> a

toList :: Trie k a -> [a]

null :: Trie k a -> Bool

length :: Trie k a -> Int

elem :: Eq a => a -> Trie k a -> Bool

maximum :: Ord a => Trie k a -> a

minimum :: Ord a => Trie k a -> a

sum :: Num a => Trie k a -> a

product :: Num a => Trie k a -> a

TrieKey k => Traversable (Trie k)

Methods

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

sequenceA :: Applicative f => Trie k (f a) -> f (Trie k a)

mapM :: Monad m => (a -> m b) -> Trie k a -> m (Trie k b)

sequence :: Monad m => Trie k (m a) -> m (Trie k a)

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

Methods

showsPrec :: Int -> Trie k a -> ShowS

show :: Trie k a -> String

showList :: [Trie k a] -> ShowS

class TrieKey k

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

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

Instances

TrieKey Bool

Associated Types

type TrieRep Bool :: * -> *

Methods

trieEmpty :: Trie Bool a

trieNull :: Trie Bool a -> Bool

trieLookup :: Bool -> Trie Bool a -> Maybe a

trieInsert :: Bool -> a -> Trie Bool a -> Trie Bool a

trieDelete :: Bool -> Trie Bool a -> Trie Bool a

trieSingleton :: Bool -> a -> Trie Bool a

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

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

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

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

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

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

trieMergeWithKey :: (Bool -> a -> b -> Maybe c) -> (Trie Bool a -> Trie Bool c) -> (Trie Bool b -> Trie Bool c) -> Trie Bool a -> Trie Bool b -> Trie Bool c

TrieKey Char

Char tries are implemented with IntMap.

Associated Types

type TrieRep Char :: * -> *

Methods

trieEmpty :: Trie Char a

trieNull :: Trie Char a -> Bool

trieLookup :: Char -> Trie Char a -> Maybe a

trieInsert :: Char -> a -> Trie Char a -> Trie Char a

trieDelete :: Char -> Trie Char a -> Trie Char a

trieSingleton :: Char -> a -> Trie Char a

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

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

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

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

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

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

trieMergeWithKey :: (Char -> a -> b -> Maybe c) -> (Trie Char a -> Trie Char c) -> (Trie Char b -> Trie Char c) -> Trie Char a -> Trie Char b -> Trie Char c

TrieKey Int

Int tries are implemented with IntMap.

Associated Types

type TrieRep Int :: * -> *

Methods

trieEmpty :: Trie Int a

trieNull :: Trie Int a -> Bool

trieLookup :: Int -> Trie Int a -> Maybe a

trieInsert :: Int -> a -> Trie Int a -> Trie Int a

trieDelete :: Int -> Trie Int a -> Trie Int a

trieSingleton :: Int -> a -> Trie Int a

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

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

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

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

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

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

trieMergeWithKey :: (Int -> a -> b -> Maybe c) -> (Trie Int a -> Trie Int c) -> (Trie Int b -> Trie Int c) -> Trie Int a -> Trie Int b -> Trie Int c

TrieKey Integer

Integer tries are implemented with Map.

Associated Types

type TrieRep Integer :: * -> *

Methods

trieEmpty :: Trie Integer a

trieNull :: Trie Integer a -> Bool

trieLookup :: Integer -> Trie Integer a -> Maybe a

trieInsert :: Integer -> a -> Trie Integer a -> Trie Integer a

trieDelete :: Integer -> Trie Integer a -> Trie Integer a

trieSingleton :: Integer -> a -> Trie Integer a

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

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

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

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

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

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

trieMergeWithKey :: (Integer -> a -> b -> Maybe c) -> (Trie Integer a -> Trie Integer c) -> (Trie Integer b -> Trie Integer c) -> Trie Integer a -> Trie Integer b -> Trie Integer c

TrieKey ()

Associated Types

type TrieRep () :: * -> *

Methods

trieEmpty :: Trie () a

trieNull :: Trie () a -> Bool

trieLookup :: () -> Trie () a -> Maybe a

trieInsert :: () -> a -> Trie () a -> Trie () a

trieDelete :: () -> Trie () a -> Trie () a

trieSingleton :: () -> a -> Trie () a

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

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

trieShowsPrec :: Show a => Int -> Trie () a -> ShowS

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

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

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

trieMergeWithKey :: (() -> a -> b -> Maybe c) -> (Trie () a -> Trie () c) -> (Trie () b -> Trie () c) -> Trie () a -> Trie () b -> Trie () c

TrieKey k => TrieKey [k]

Associated Types

type TrieRep [k] :: * -> *

Methods

trieEmpty :: Trie [k] a

trieNull :: Trie [k] a -> Bool

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

trieInsert :: [k] -> a -> Trie [k] a -> Trie [k] a

trieDelete :: [k] -> Trie [k] a -> Trie [k] a

trieSingleton :: [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

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

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

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

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

TrieKey k => TrieKey (Maybe k)

Associated Types

type TrieRep (Maybe k) :: * -> *

Methods

trieEmpty :: Trie (Maybe k) a

trieNull :: Trie (Maybe k) a -> Bool

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

trieInsert :: Maybe k -> a -> Trie (Maybe k) a -> Trie (Maybe k) a

trieDelete :: Maybe k -> Trie (Maybe k) a -> Trie (Maybe k) a

trieSingleton :: Maybe k -> a -> Trie (Maybe k) a

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

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

trieShowsPrec :: Show a => Int -> Trie (Maybe k) a -> ShowS

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

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

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

trieMergeWithKey :: (Maybe k -> a -> b -> Maybe c) -> (Trie (Maybe k) a -> Trie (Maybe k) c) -> (Trie (Maybe k) b -> Trie (Maybe k) c) -> Trie (Maybe k) a -> Trie (Maybe k) b -> Trie (Maybe k) c

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

Associated Types

type TrieRep (OrdKey k) :: * -> *

Methods

trieEmpty :: Trie (OrdKey k) a

trieNull :: Trie (OrdKey k) a -> Bool

trieLookup :: OrdKey k -> Trie (OrdKey k) a -> Maybe a

trieInsert :: OrdKey k -> a -> Trie (OrdKey k) a -> Trie (OrdKey k) a

trieDelete :: OrdKey k -> Trie (OrdKey k) a -> Trie (OrdKey k) a

trieSingleton :: OrdKey k -> a -> Trie (OrdKey k) a

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

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

trieShowsPrec :: Show a => Int -> Trie (OrdKey k) a -> ShowS

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

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

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

trieMergeWithKey :: (OrdKey k -> a -> b -> Maybe c) -> (Trie (OrdKey k) a -> Trie (OrdKey k) c) -> (Trie (OrdKey k) b -> Trie (OrdKey k) c) -> Trie (OrdKey k) a -> Trie (OrdKey k) b -> Trie (OrdKey k) c

(TrieKey a, TrieKey b) => TrieKey (Either a b)

Associated Types

type TrieRep (Either a b) :: * -> *

Methods

trieEmpty :: Trie (Either a b) a

trieNull :: Trie (Either a b) a -> Bool

trieLookup :: Either a b -> Trie (Either a b) a -> Maybe a

trieInsert :: Either a b -> a -> Trie (Either a b) a -> Trie (Either a b) a

trieDelete :: Either a b -> Trie (Either a b) a -> Trie (Either a b) a

trieSingleton :: Either a b -> a -> Trie (Either a b) a

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

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

trieShowsPrec :: Show a => Int -> Trie (Either a b) a -> ShowS

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

trieFoldWithKey :: (Either a b -> a -> r -> r) -> r -> Trie (Either a b) a -> r

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

trieMergeWithKey :: (Either a b -> a -> b -> Maybe c) -> (Trie (Either a b) a -> Trie (Either a b) c) -> (Trie (Either a b) b -> Trie (Either a b) c) -> Trie (Either a b) a -> Trie (Either a b) b -> Trie (Either a b) c

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

Associated Types

type TrieRep (a, b) :: * -> *

Methods

trieEmpty :: Trie (a, b) a

trieNull :: Trie (a, b) a -> Bool

trieLookup :: (a, b) -> Trie (a, b) a -> Maybe a

trieInsert :: (a, b) -> a -> Trie (a, b) a -> Trie (a, b) a

trieDelete :: (a, b) -> Trie (a, b) a -> Trie (a, b) a

trieSingleton :: (a, b) -> a -> Trie (a, b) a

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

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

trieShowsPrec :: Show a => Int -> Trie (a, b) a -> ShowS

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

trieFoldWithKey :: ((a, b) -> a -> r -> r) -> r -> Trie (a, b) a -> r

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

trieMergeWithKey :: ((a, b) -> a -> b -> Maybe c) -> (Trie (a, b) a -> Trie (a, b) c) -> (Trie (a, b) b -> Trie (a, b) c) -> Trie (a, b) a -> Trie (a, b) b -> Trie (a, b) c

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

Associated Types

type TrieRep (a, b, c) :: * -> *

Methods

trieEmpty :: Trie (a, b, c) a

trieNull :: Trie (a, b, c) a -> Bool

trieLookup :: (a, b, c) -> Trie (a, b, c) a -> Maybe a

trieInsert :: (a, b, c) -> a -> Trie (a, b, c) a -> Trie (a, b, c) a

trieDelete :: (a, b, c) -> Trie (a, b, c) a -> Trie (a, b, c) a

trieSingleton :: (a, b, c) -> a -> Trie (a, b, c) a

trieMap :: (a -> b) -> Trie (a, b, c) a -> Trie (a, b, c) b

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

trieShowsPrec :: Show a => Int -> Trie (a, b, c) a -> ShowS

trieMapMaybeWithKey :: ((a, b, c) -> a -> Maybe b) -> Trie (a, b, c) a -> Trie (a, b, c) b

trieFoldWithKey :: ((a, b, c) -> a -> r -> r) -> r -> Trie (a, b, c) a -> r

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

trieMergeWithKey :: ((a, b, c) -> a -> b -> Maybe c) -> (Trie (a, b, c) a -> Trie (a, b, c) c) -> (Trie (a, b, c) b -> Trie (a, b, c) c) -> Trie (a, b, c) a -> Trie (a, b, c) b -> Trie (a, b, c) c

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

Associated Types

type TrieRep (a, b, c, d) :: * -> *

Methods

trieEmpty :: Trie (a, b, c, d) a

trieNull :: Trie (a, b, c, d) a -> Bool

trieLookup :: (a, b, c, d) -> Trie (a, b, c, d) a -> Maybe a

trieInsert :: (a, b, c, d) -> a -> Trie (a, b, c, d) a -> Trie (a, b, c, d) a

trieDelete :: (a, b, c, d) -> Trie (a, b, c, d) a -> Trie (a, b, c, d) a

trieSingleton :: (a, b, c, d) -> a -> Trie (a, b, c, d) a

trieMap :: (a -> b) -> Trie (a, b, c, d) a -> Trie (a, b, c, d) b

trieTraverse :: Applicative f => (a -> f b) -> Trie (a, b, c, d) a -> f (Trie (a, b, c, d) b)

trieShowsPrec :: Show a => Int -> Trie (a, b, c, d) a -> ShowS

trieMapMaybeWithKey :: ((a, b, c, d) -> a -> Maybe b) -> Trie (a, b, c, d) a -> Trie (a, b, c, d) b

trieFoldWithKey :: ((a, b, c, d) -> a -> r -> r) -> r -> Trie (a, b, c, d) a -> r

trieTraverseWithKey :: Applicative f => ((a, b, c, d) -> a -> f b) -> Trie (a, b, c, d) a -> f (Trie (a, b, c, d) b)

trieMergeWithKey :: ((a, b, c, d) -> a -> b -> Maybe c) -> (Trie (a, b, c, d) a -> Trie (a, b, c, d) c) -> (Trie (a, b, c, d) b -> Trie (a, b, c, d) c) -> Trie (a, b, c, d) a -> Trie (a, b, c, d) b -> Trie (a, b, c, d) c

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

Associated Types

type TrieRep (a, b, c, d, e) :: * -> *

Methods

trieEmpty :: Trie (a, b, c, d, e) a

trieNull :: Trie (a, b, c, d, e) a -> Bool

trieLookup :: (a, b, c, d, e) -> Trie (a, b, c, d, e) a -> Maybe a

trieInsert :: (a, b, c, d, e) -> a -> Trie (a, b, c, d, e) a -> Trie (a, b, c, d, e) a

trieDelete :: (a, b, c, d, e) -> Trie (a, b, c, d, e) a -> Trie (a, b, c, d, e) a

trieSingleton :: (a, b, c, d, e) -> a -> Trie (a, b, c, d, e) a

trieMap :: (a -> b) -> Trie (a, b, c, d, e) a -> Trie (a, b, c, d, e) b

trieTraverse :: Applicative f => (a -> f b) -> Trie (a, b, c, d, e) a -> f (Trie (a, b, c, d, e) b)

trieShowsPrec :: Show a => Int -> Trie (a, b, c, d, e) a -> ShowS

trieMapMaybeWithKey :: ((a, b, c, d, e) -> a -> Maybe b) -> Trie (a, b, c, d, e) a -> Trie (a, b, c, d, e) b

trieFoldWithKey :: ((a, b, c, d, e) -> a -> r -> r) -> r -> Trie (a, b, c, d, e) a -> r

trieTraverseWithKey :: Applicative f => ((a, b, c, d, e) -> a -> f b) -> Trie (a, b, c, d, e) a -> f (Trie (a, b, c, d, e) b)

trieMergeWithKey :: ((a, b, c, d, e) -> a -> b -> Maybe c) -> (Trie (a, b, c, d, e) a -> Trie (a, b, c, d, e) c) -> (Trie (a, b, c, d, e) b -> Trie (a, b, c, d, e) c) -> Trie (a, b, c, d, e) a -> Trie (a, b, c, d, e) b -> Trie (a, b, c, d, e) c

Construction

empty :: TrieKey k => Trie k a

Construct an empty trie

singleton :: TrieKey k => k -> a -> Trie k a

Construct a trie holding a single value

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

Construct a trie from a list of key-value pairs

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

Construct a trie from a list of key-value pairs. The given function is used to combine values at the same key.

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

Version of fromListWith which is strict in the result of the combining function.

Updates

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

Alter the value at the given key location. The parameter function takes the value stored at the given key, if one exists, and should return a value to insert at that location, or Nothing to delete from that location.

insert :: TrieKey k => k -> a -> Trie k a -> Trie k a

Insert an element into a trie

insertWith :: TrieKey k => (v -> v -> v) -> k -> v -> Trie k v -> Trie k v

Insert a value at the given key. The combining function is used when a value is already stored at that key. The new value is the first argument to the combining function.

insertWith' :: TrieKey k => (v -> v -> v) -> k -> v -> Trie k v -> Trie k v

Version of insertWith that is strict in the result of combining two elements.

delete :: TrieKey k => k -> Trie k a -> Trie k a

Delete an element from a trie

at :: (Functor f, TrieKey k) => k -> (Maybe a -> f (Maybe a)) -> Trie k a -> f (Trie k a)

Lens for the value at a given key

Queries

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.

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

Test for an empty trie

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

Lookup an element from a trie

Folding

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

Fold a trie with a function of both key and value

fold :: TrieKey k => (a -> r -> r) -> r -> Trie k a -> r

Fold a trie with a function of the value

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

Transform a trie to an association list.

Traversing

traverseWithKey :: (TrieKey k, Applicative f) => (k -> a -> f b) -> Trie k a -> f (Trie k b)

Traverse a trie with a function of both key and value

mapMaybe :: TrieKey k => (a -> Maybe b) -> Trie k a -> Trie k b

Map a function over a trie filtering out elements where function returns Nothing

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

filter :: TrieKey k => (a -> Bool) -> Trie k a -> Trie k a

Filter the values of a trie with the given predicate.

filterWithKey :: TrieKey k => (k -> a -> Bool) -> Trie k a -> Trie k a

Version of filter where the predicate also gets the key.

Combining maps

union :: TrieKey k => Trie k a -> Trie k a -> Trie k a

Left-biased union of two tries

unionWith :: TrieKey k => (a -> a -> a) -> Trie k a -> Trie k a -> Trie k a

Union of two tries with function used to merge overlapping elements

unionWithKey :: TrieKey k => (k -> a -> a -> a) -> Trie k a -> Trie k a -> Trie k a

Union of two tries with function used to merge overlapping elements along with key

intersection :: TrieKey k => Trie k a -> Trie k b -> Trie k a

Left-biased intersection of two tries

intersectionWith :: TrieKey k => (a -> b -> c) -> Trie k a -> Trie k b -> Trie k c

Intersection of two tries parameterized by a combining function of the values at overlapping keys

intersectionWithKey :: TrieKey k => (k -> a -> b -> c) -> Trie k a -> Trie k b -> Trie k c

Intersection of two tries parameterized by a combining function of the key and the values at overlapping keys

difference :: TrieKey k => Trie k a -> Trie k b -> Trie k a

Remove the keys of the right trie from the left trie

differenceWith :: TrieKey k => (a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a

Parameterized difference using a custom merge function. Return Just to change the value stored in left trie, or Nothing to remove from the left trie.

differenceWithKey :: TrieKey k => (k -> a -> b -> Maybe a) -> Trie k a -> Trie k b -> Trie k a

differenceWith where function also has access to the key

Keys using Ord

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)

Methods

(==) :: OrdKey k -> OrdKey k -> Bool

(/=) :: OrdKey k -> OrdKey k -> Bool

Ord k => Ord (OrdKey k)

Methods

compare :: OrdKey k -> OrdKey k -> Ordering

(<) :: OrdKey k -> OrdKey k -> Bool

(<=) :: OrdKey k -> OrdKey k -> Bool

(>) :: OrdKey k -> OrdKey k -> Bool

(>=) :: OrdKey k -> OrdKey k -> Bool

max :: OrdKey k -> OrdKey k -> OrdKey k

min :: OrdKey k -> OrdKey k -> OrdKey k

Read k => Read (OrdKey k)

Methods

readsPrec :: Int -> ReadS (OrdKey k)

readList :: ReadS [OrdKey k]

readPrec :: ReadPrec (OrdKey k)

readListPrec :: ReadPrec [OrdKey k]

Show k => Show (OrdKey k)

Methods

showsPrec :: Int -> OrdKey k -> ShowS

show :: OrdKey k -> String

showList :: [OrdKey k] -> ShowS

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

Associated Types

type TrieRep (OrdKey k) :: * -> *

Methods

trieEmpty :: Trie (OrdKey k) a

trieNull :: Trie (OrdKey k) a -> Bool

trieLookup :: OrdKey k -> Trie (OrdKey k) a -> Maybe a

trieInsert :: OrdKey k -> a -> Trie (OrdKey k) a -> Trie (OrdKey k) a

trieDelete :: OrdKey k -> Trie (OrdKey k) a -> Trie (OrdKey k) a

trieSingleton :: OrdKey k -> a -> Trie (OrdKey k) a

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

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

trieShowsPrec :: Show a => Int -> Trie (OrdKey k) a -> ShowS

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

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

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

trieMergeWithKey :: (OrdKey k -> a -> b -> Maybe c) -> (Trie (OrdKey k) a -> Trie (OrdKey k) c) -> (Trie (OrdKey k) b -> Trie (OrdKey k) c) -> Trie (OrdKey k) a -> Trie (OrdKey k) b -> Trie (OrdKey k) c

type TrieRep (OrdKey k)

type TrieRep (OrdKey k) = Map k