Safe Haskell	None
Language	Haskell2010

Data.Trie

Description

Prefix trees on arbitrary keys.

Synopsis

data Trie k v = Trie {
- trieMap :: HashMap k (Trie k v)
- trieData :: Maybe v
}
empty :: Trie k v
singleton :: Hashable k => [k] -> v -> Trie k v
lookup :: (Eq k, Hashable k) => [k] -> Trie k v -> Maybe v
insert :: (Eq k, Hashable k) => [k] -> v -> Trie k v -> Trie k v
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> [k] -> v -> Trie k v -> Trie k v
elems :: Trie k v -> [v]

Documentation

data Trie k v Source #

Data structure for storing a value v keyed on a sequence of ks

Constructors

Trie
Fields trieMap :: HashMap k (Trie k v) trieData :: Maybe v

Instances

Instances details

(Eq k, Eq v) => Eq (Trie k v) Source #
Instance details Defined in Data.Trie Methods (==) :: Trie k v -> Trie k v -> Bool # (/=) :: Trie k v -> Trie k v -> Bool #
(Ord k, Ord v) => Ord (Trie k v) Source #
Instance details Defined in Data.Trie Methods compare :: Trie k v -> Trie k v -> Ordering # (<) :: Trie k v -> Trie k v -> Bool # (<=) :: Trie k v -> Trie k v -> Bool # (>) :: Trie k v -> Trie k v -> Bool # (>=) :: Trie k v -> Trie k v -> Bool # max :: Trie k v -> Trie k v -> Trie k v # min :: Trie k v -> Trie k v -> Trie k v #
(Show k, Show v) => Show (Trie k v) Source #
Instance details Defined in Data.Trie Methods showsPrec :: Int -> Trie k v -> ShowS # show :: Trie k v -> String # showList :: [Trie k v] -> ShowS #
Generic (Trie k v) Source #
Instance details Defined in Data.Trie Associated Types type Rep (Trie k v) :: Type -> Type # Methods from :: Trie k v -> Rep (Trie k v) x # to :: Rep (Trie k v) x -> Trie k v #
(Eq k, Hashable k, Semigroup v) => Semigroup (Trie k v) Source #	Semigroup via union. The resulting `Trie` will contain all paths present in either tries. If both tries contain a value at a given path, we use the value's semigroup instance to compute the resulting value.
Instance details Defined in Data.Trie Methods (<>) :: Trie k v -> Trie k v -> Trie k v # sconcat :: NonEmpty (Trie k v) -> Trie k v # stimes :: Integral b => b -> Trie k v -> Trie k v #
(Eq k, Hashable k, Semigroup v) => Monoid (Trie k v) Source #
Instance details Defined in Data.Trie Methods mempty :: Trie k v # mappend :: Trie k v -> Trie k v -> Trie k v # mconcat :: [Trie k v] -> Trie k v #
(ToJSONKey a, ToJSON v) => ToJSON (Trie a v) Source #
Instance details Defined in Data.Trie Methods toJSON :: Trie a v -> Value toEncoding :: Trie a v -> Encoding toJSONList :: [Trie a v] -> Value toEncodingList :: [Trie a v] -> Encoding
type Rep (Trie k v) Source #
Instance details Defined in Data.Trie type Rep (Trie k v) = D1 ('MetaData "Trie" "Data.Trie" "graphql-engine-1.0.0-inplace" 'False) (C1 ('MetaCons "Trie" 'PrefixI 'True) (S1 ('MetaSel ('Just "trieMap") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedStrict) (Rec0 (HashMap k (Trie k v))) :*: S1 ('MetaSel ('Just "trieData") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedStrict) (Rec0 (Maybe v))))

empty :: Trie k v Source #

Construct an empty trie.

singleton :: Hashable k => [k] -> v -> Trie k v Source #

Creates a trie from a path and a value

>>> singleton ["a", "b"] 5
Trie (fromList [("a", Trie (fromList [("b", Trie (fromList []) (Just 5))]) Nothing)]) Nothing

>>> singleton [] 5
Trie (fromList []) (Just 5)

lookup :: (Eq k, Hashable k) => [k] -> Trie k v -> Maybe v Source #

Find a value at the given path, if any.

insert :: (Eq k, Hashable k) => [k] -> v -> Trie k v -> Trie k v Source #

Insert the given value at the given path.

If there's already a value at the given path, it is replaced.

insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> [k] -> v -> Trie k v -> Trie k v Source #

Insert the value at the given path.

If there's already a value at the given path, the old value is replaced by the result of applying the given function to the new and old value.

elems :: Trie k v -> [v] Source #

Extract all values of the trie, discarding any path information.