Salak.Trie

A data structure for manipulating properties.

Documentation

data Trie v

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

Defined in Salak.Trie

Methods

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

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

Foldable Trie

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

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)

Defined in Salak.Trie

Methods

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

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

Show v => Show (Trie v)

Defined in Salak.Trie

Methods

showsPrec :: Int -> Trie v -> ShowS

show :: Trie v -> String

showList :: [Trie v] -> ShowS

Construction

empty :: Trie v

O(1). The empty trie.

singleton :: v -> Trie v

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

Basic interface

null :: Trie v -> Bool

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

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

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

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

subTries :: Keys -> Trie v -> Trie v

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

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

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

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

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

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

Lists

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

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

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

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

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

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

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