Copyright	2019 Daniel YU
License	MIT
Maintainer	leptonyu@gmail.com
Stability	experimental
Portability	portable
Safe Haskell	None
Language	Haskell2010

Salak.Trie

Contents

Construction
Basic interface
Lists
Filter
Combine

Description

A data structure for manipulating properties.

Synopsis

data Trie v = Trie {
- tvar :: !(Maybe v)
- tmap :: !(HashMap Key (Trie v))
}
empty :: Trie v
singleton :: v -> Trie v
null :: Trie v -> Bool
member :: Eq v => Keys -> Trie v -> Bool
lookup :: Eq v => Keys -> Trie v -> Maybe v
subTrie :: Key -> Trie v -> Trie v
subTries :: Keys -> Trie v -> Trie v
insert :: Eq v => Keys -> v -> Trie v -> Trie v
modify :: Eq v => Key -> (Trie v -> Trie v) -> Trie v -> Trie v
modify' :: Eq v => (Trie v -> Trie v) -> Keys -> Trie v -> Trie v
update :: Eq v => (Maybe v -> Maybe v) -> Trie v -> Trie v
alter :: Eq v => (Maybe v -> Maybe v) -> Keys -> Trie v -> Trie v
toList :: Trie v -> [(Keys, v)]
fromList :: Eq v => [(Keys, v)] -> Trie v
filter :: Eq v => (v -> Bool) -> Trie v -> Trie v
unionWith :: Eq v => (Maybe v -> Maybe v -> Maybe v) -> Trie v -> Trie v -> Trie v
unionWith' :: (Maybe v -> Maybe v -> Maybe v3) -> Trie v -> Trie v -> Trie v3

Documentation

data Trie v Source #

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

Constructors

Trie
Fields tvar :: !(Maybe v) tmap :: !(HashMap Key (Trie v))

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.