salak-0.3.1: Configuration (re)Loader and Parser.

Copyright 2019 Daniel YU BSD3 leptonyu@gmail.com experimental portable None Haskell2010

Salak.Trie

Description

A data structure for manipulating properties.

Synopsis

Documentation

data Trie v Source #

A Trie from keys Key to values v, which is a recursive map.

Instances
 Source # Instance detailsDefined in Salak.Trie Methodsfmap :: (a -> b) -> Trie a -> Trie b #(<\$) :: a -> Trie b -> Trie a # Source # Instance detailsDefined in Salak.Trie Methodsfold :: Monoid m => Trie m -> m #foldMap :: Monoid m => (a -> m) -> Trie a -> m #foldr :: (a -> b -> b) -> b -> Trie a -> b #foldr' :: (a -> b -> b) -> b -> Trie a -> b #foldl :: (b -> a -> b) -> b -> Trie a -> b #foldl' :: (b -> a -> b) -> b -> Trie a -> b #foldr1 :: (a -> a -> a) -> Trie a -> a #foldl1 :: (a -> a -> a) -> Trie a -> a #toList :: Trie a -> [a] #null :: Trie a -> Bool #length :: Trie a -> Int #elem :: Eq a => a -> Trie a -> Bool #maximum :: Ord a => Trie a -> a #minimum :: Ord a => Trie a -> a #sum :: Num a => Trie a -> a #product :: Num a => Trie a -> a # Source # Instance detailsDefined in Salak.Trie Methodstraverse :: Applicative f => (a -> f b) -> Trie a -> f (Trie b) #sequenceA :: Applicative f => Trie (f a) -> f (Trie a) #mapM :: Monad m => (a -> m b) -> Trie a -> m (Trie b) #sequence :: Monad m => Trie (m a) -> m (Trie a) # Eq v => Eq (Trie v) Source # Instance detailsDefined in Salak.Trie Methods(==) :: Trie v -> Trie v -> Bool #(/=) :: Trie v -> Trie v -> Bool # Show v => Show (Trie v) Source # Instance detailsDefined in Salak.Trie MethodsshowsPrec :: Int -> Trie v -> ShowS #show :: Trie v -> String #showList :: [Trie v] -> ShowS #

getPrimitive :: Trie v -> Maybe v Source #

Get primitive value of a trie.

getMap :: Trie v -> HashMap Key (Trie v) Source #

Get map value of a trie.

Construction

O(1). The empty trie.

singleton :: v -> Trie v Source #

O(1). A trie with a single element.

Basic interface

null :: Trie v -> Bool Source #

O(1). Return True if this trie is empty, False otherwise.

member :: Eq v => Keys -> Trie v -> Bool Source #

O(log (n+m)). Return True if the specified key is present in the trie, False otherwise.

lookup :: Eq v => Keys -> Trie v -> Maybe v Source #

O(log (n+m)). Return the primitive value to which the specified key is mapped, or Nothing if this trie contains no mapping for the key.

insert :: Eq v => Keys -> v -> Trie v -> Trie v Source #

O(log n). Associate the specified value with the specified key in this trie. If this trie previously contained a mapping for the key, the old value is replaced.

modify :: Eq v => Key -> (Trie v -> Trie v) -> Trie v -> Trie v Source #

O(log m). The expression (modify k f trie) modifies the sub trie at k.

modifyF :: (Monad m, Eq v) => Key -> (Trie v -> m (Trie v)) -> Trie v -> m (Trie v) Source #

O(log m). The expression (modifyF k f trie) modifies the sub trie at k.

modify' :: Eq v => Keys -> (Trie v -> Trie v) -> Trie v -> Trie v Source #

O(log (n+m)). The expression (modify' ks f trie) modifies the sub trie at ks.

update :: Eq v => (Maybe v -> Maybe v) -> Trie v -> Trie v Source #

O(1). The expression (update f trie) updates the primitive value in the trie.

alter :: Eq v => (Maybe v -> Maybe v) -> Keys -> Trie v -> Trie v Source #

O(n). The expression (update f ks trie) updates the primitive value of sub trie at ks.

alterF :: (Functor f, Eq v) => (Maybe v -> f (Maybe v)) -> Keys -> Trie v -> f (Trie v) Source #

O(n). The expression (update f ks trie) updates the primitive value of sub trie at ks.

Lists

toList :: Trie v -> [(Keys, v)] Source #

O(n*m). Return a list of this tries's elements. The list is produced lazily.

fromList :: Eq v => [(Keys, v)] -> Trie v Source #

O(n*m*log n). Construct a trie with the supplied mappings. If the list contains duplicate mappings, the later mappings take precedence.

Filter

filter :: Eq v => (v -> Bool) -> Trie v -> Trie v Source #

O(n). Filter this trie by retaining only elements which values satisfy a predicate.

Combine

unionWith :: Eq v => (Maybe v -> Maybe v -> Maybe v) -> Trie v -> Trie v -> Trie v Source #

O(n+m). The union of two tries. If a key occurs in both tries, the provided function (first argument) will be used to compute the result.

unionWith' :: (Maybe v -> Maybe v -> Maybe v3) -> Trie v -> Trie v -> Trie v3 Source #

O(n+m). The union of two tries. All the keys will be calculated by the provided function.