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

Copyright2019 Daniel YU
LicenseMIT
Maintainerleptonyu@gmail.com
Stabilityexperimental
Portabilityportable
Safe HaskellNone
LanguageHaskell2010

Salak.Trie

Contents

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.

Constructors

Trie 

Fields

Instances
Functor Trie Source # 
Instance details

Defined in Salak.Trie

Methods

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

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

Foldable Trie Source # 
Instance details

Defined in Salak.Trie

Methods

fold :: 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 #

Traversable Trie Source # 
Instance details

Defined in Salak.Trie

Methods

traverse :: 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 details

Defined in Salak.Trie

Methods

(==) :: Trie v -> Trie v -> Bool #

(/=) :: Trie v -> Trie v -> Bool #

Show v => Show (Trie v) Source # 
Instance details

Defined in Salak.Trie

Methods

showsPrec :: Int -> Trie v -> ShowS #

show :: Trie v -> String #

showList :: [Trie v] -> ShowS #

Construction

empty :: Trie v Source #

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.

subTrie :: Key -> Trie v -> Trie v Source #

subTries :: Keys -> Trie v -> Trie v Source #

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.

modify' :: Eq v => (Trie v -> Trie v) -> Keys -> 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.

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.