| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.Trie.Map
Synopsis
- data TMap c a
- match :: Ord c => [c] -> TMap c a -> (Maybe a, TMap c a)
- lookup :: Ord c => [c] -> TMap c a -> Maybe a
- lookupPrefixes :: Ord c => [c] -> TMap c a -> [([c], a)]
- member :: Ord c => [c] -> TMap c a -> Bool
- notMember :: Ord c => [c] -> TMap c a -> Bool
- null :: TMap c a -> Bool
- count :: TMap c a -> Int
- keys :: TMap c a -> [[c]]
- elems :: TMap c a -> [a]
- empty :: TMap c a
- just :: a -> TMap c a
- singleton :: [c] -> a -> TMap c a
- insertWith :: Ord c => (a -> a -> a) -> [c] -> a -> TMap c a -> TMap c a
- insert :: Ord c => [c] -> a -> TMap c a -> TMap c a
- deleteWith :: Ord c => (b -> a -> Maybe a) -> [c] -> b -> TMap c a -> TMap c a
- delete :: Ord c => [c] -> TMap c a -> TMap c a
- adjust :: Ord c => (a -> a) -> [c] -> TMap c a -> TMap c a
- revise :: Ord c => (Maybe a -> a) -> [c] -> TMap c a -> TMap c a
- update :: Ord c => (a -> Maybe a) -> [c] -> TMap c a -> TMap c a
- alter :: Ord c => (Maybe a -> Maybe a) -> [c] -> TMap c a -> TMap c a
- union :: Ord c => TMap c a -> TMap c a -> TMap c a
- unionWith :: Ord c => (a -> a -> a) -> TMap c a -> TMap c a -> TMap c a
- intersection :: Ord c => TMap c a -> TMap c b -> TMap c a
- intersectionWith :: Ord c => (a -> b -> Maybe r) -> TMap c a -> TMap c b -> TMap c r
- difference :: Ord c => TMap c a -> TMap c b -> TMap c a
- differenceWith :: Ord c => (a -> b -> Maybe a) -> TMap c a -> TMap c b -> TMap c a
- appendWith :: (Ord c, Semigroup z) => (x -> y -> z) -> TMap c x -> TMap c y -> TMap c z
- toList :: TMap c a -> [([c], a)]
- fromList :: Ord c => [([c], a)] -> TMap c a
- fromListWith :: Ord c => (a -> a -> a) -> [([c], a)] -> TMap c a
- toAscList :: TMap c a -> [([c], a)]
- fromAscList :: Eq c => [([c], a)] -> TMap c a
- fromAscListWith :: Ord c => (a -> a -> a) -> [([c], a)] -> TMap c a
- toMap :: TMap c a -> Map [c] a
- fromMap :: Eq c => Map [c] a -> TMap c a
- keysTSet :: TMap c a -> TSet c
- fromTSet :: ([c] -> a) -> TSet c -> TMap c a
- toParser :: Alternative f => (c -> f c') -> f eot -> TMap c a -> f ([c'], a)
- toParser_ :: Alternative f => (c -> f c') -> f eot -> TMap c a -> f a
- toParser__ :: Alternative f => (c -> f c') -> f eot -> TMap c a -> f ()
- traverseWithKey :: Applicative f => ([c] -> a -> f b) -> TMap c a -> f (TMap c b)
- mapWithKey :: ([c] -> a -> b) -> TMap c a -> TMap c b
- foldMapWithKey :: Monoid r => ([c] -> a -> r) -> TMap c a -> r
- foldrWithKey :: ([c] -> a -> r -> r) -> r -> TMap c a -> r
Type
Mapping from [c] to a implemented as a trie.
This type serves the almost same purpose of Map [c] a,
but can be looked up more efficiently.
Instances
Queries
match :: Ord c => [c] -> TMap c a -> (Maybe a, TMap c a) Source #
Perform partial matching against a TMap.
match xs tmap returns two values. The first value is the result of
lookup. The second is another TMap for all keys which contain xs as their prefix.
The keys of the returned map do not contain the common prefix xs.
Example
>>>let x = fromList [("ham", 1), ("bacon", 2), ("hamburger", 3)]>>>match "ham" x(Just 1,fromList [("",1),("burger",3)])
lookup :: Ord c => [c] -> TMap c a -> Maybe a Source #
lookup xs tmap returns Just a if tmap contains mapping
from xs to a, and returns Nothing if not.
lookupPrefixes :: Ord c => [c] -> TMap c a -> [([c], a)] Source #
lookupPrefixes xs tmap performs lookup for every prefixes of the input string xs
and returns list of every pair of prefix and value exising in tmap.
Example
>>>let x = fromList [("ham", 1), ("bacon", 2), ("hamburger", 3)]>>>lookupPrefixes "hamburger and bacon" x[("ham",1),("hamburger",3)]
count :: TMap c a -> Int Source #
Returns number of entries.
Note that this operation takes O(number of nodes),
unlike O(1) of size.
Construction
singleton :: [c] -> a -> TMap c a Source #
singleton xs a is a TMap which contains only one entry
from xs to a.
Single item modification
insertWith :: Ord c => (a -> a -> a) -> [c] -> a -> TMap c a -> TMap c a Source #
insertWith op xs a tmap inserts an entry of key-value pair (cs,a)
to the tmap. If tmap already has an entry with key equals to
xs, its value b is replaced with op a b.
insertWith op cs a = 'revise' (maybe a (op a)) cs
insert :: Ord c => [c] -> a -> TMap c a -> TMap c a Source #
Inserts an entry of key and value pair.
Already existing value will be overwritten.
insert = 'insertWith' (const a)
deleteWith :: Ord c => (b -> a -> Maybe a) -> [c] -> b -> TMap c a -> TMap c a Source #
Deletes an entry with given key, conditionally.
deleteWith f xs b looks up an entry with key xs, and if such entry
is found, evaluate f b a with its value a. If it returned Nothing,
the entry is deleted. Otherwise, if it returned Just a', the value of
the entry is replaced with a'.
deleteWith f cs b = 'update' (f b) cs
delete :: Ord c => [c] -> TMap c a -> TMap c a Source #
Deletes an entry with given key.
delete = 'update' (const Nothing)
adjust :: Ord c => (a -> a) -> [c] -> TMap c a -> TMap c a Source #
Apply a function to the entry with given key.
revise :: Ord c => (Maybe a -> a) -> [c] -> TMap c a -> TMap c a Source #
Apply a function f to the entry with the given key. If there is no such
entry, insert an entry with value f Nothing.
update :: Ord c => (a -> Maybe a) -> [c] -> TMap c a -> TMap c a Source #
Apply a function f to the entry with given key. If f returns
Nothing, that entry is deleted.
alter :: Ord c => (Maybe a -> Maybe a) -> [c] -> TMap c a -> TMap c a Source #
Apply a function f to the entry with given key. This function alter
is the most generic version of adjust, revise, update.
- You can insert new entry by returning
Just afromf Nothing. - You can delete existing entry by returning
Nothingfromf (Just a).
This function always evaluates f Nothing in addition to determine
operation applied to the given key.
If you're not going to use alter on missing keys, consider using update instead.
Combine
appendWith :: (Ord c, Semigroup z) => (x -> y -> z) -> TMap c x -> TMap c y -> TMap c z Source #
Creates a new TMap from two TMaps. The keys of the new map
are concatenations of one key from the first map and another one from the second map.
Corresponding values for these keys are calculated with the given function
of type (x -> y -> z). If two different concatenations yield
the same key, the calculated values for these keys are combined with the Semigroup operation <>.
The behavior of appendWith is equivalent to the following implementation.
appendWith :: (Ord c, Semigroup z) => (x -> y -> z) -> TMap c x -> TMap c y -> TMap c z appendWith f x y =fromListWith(flip (<>)) [ (kx ++ ky, f valx valy) | (kx, valx) <-toAscListx , (ky, valy) <- toAscList y ]
In other words, a set of colliding key-valur pairs is combined in increasing order of the left key.
For example, suppose x, y are TMap with these key-value pairs,
and kx1 ++ ky3, kx2 ++ ky2, kx3 ++ ky1 are all equal to the same key kz.
x = fromAscList [ (kx1, x1), (kx2, x2), (kx3, x3) ] -- kx1 < kx2 < kx3
y = fromAscList [ (ky1, y1), (ky2, y2), (ky3, y3) ]
On these maps, appendWith combines the values for these colliding keys
in the order of kx*.
lookup kz (appendWith f x y) == Just (f x1 y3 <> f x2 y2 <> f x3 y1)
Example
let x = fromList [("a", 1), ("aa", 2)] :: TMap Char Int
y = fromList [("aa", 10), ("aaa", 20)] :: TMap Char Int
appendWith (\a b -> show (a,b)) x y ==
fromList [ ("aaa", "(1,10)")
, ("aaaa", "(1,20)" <> "(2,10)")
, ("aaaaa", "(2,20)") ]Conversion
fromListWith :: Ord c => (a -> a -> a) -> [([c], a)] -> TMap c a Source #
fromAscList :: Eq c => [([c], a)] -> TMap c a Source #
fromAscListWith :: Ord c => (a -> a -> a) -> [([c], a)] -> TMap c a Source #
Parsing
Arguments
| :: Alternative f | |
| => (c -> f c') | char |
| -> f eot | eot |
| -> TMap c a | |
| -> f ([c'], a) |
Arguments
| :: Alternative f | |
| => (c -> f c') | char |
| -> f eot | eot |
| -> TMap c a | |
| -> f a |
Arguments
| :: Alternative f | |
| => (c -> f c') | char |
| -> f eot | eot |
| -> TMap c a | |
| -> f () |
Traversing with keys
traverseWithKey :: Applicative f => ([c] -> a -> f b) -> TMap c a -> f (TMap c b) Source #
Same semantics to following defintion, but have more efficient implementation.
traverseWithKey f = fmap fromAscList .
traverse (\(cs,a) -> (,) cs <$> f cs a) .
toAscListmapWithKey :: ([c] -> a -> b) -> TMap c a -> TMap c b Source #
Same semantics to following defintion, but have more efficient implementation.
mapWithKey f = fromAscList .
map (\(cs,a) -> (cs, f cs a)) .
toAscListfoldMapWithKey :: Monoid r => ([c] -> a -> r) -> TMap c a -> r Source #
Same semantics to following defintion, but have more efficient implementation.
foldMapWithKey f = foldMap (uncurry f) . toAscList
foldrWithKey :: ([c] -> a -> r -> r) -> r -> TMap c a -> r Source #
Same semantics to following defintion, but have more efficient implementation.
foldrWithKey f z = foldr (uncurry f) z . toAscList