fixfile-0.4.0.0: File-backed recursive data structures.

Copyright(C) 2016 Rev. Johnny Healey
LicenseLGPL-3
MaintainerRev. Johnny Healey <rev.null@gmail.com>
Stabilityexperimental
Portabilityunknown
Safe HaskellNone
LanguageHaskell2010

Data.FixFile.Trie

Description

This is a Trie data type that can be used with FixFile. It can be used as a key-value store where the key is a ByteString of arbitrary size.

Synopsis

Documentation

data Trie v a Source #

Fixed (Trie v) is a trie mapping lazy ByteStrings to values of type v.

Instances

Functor (Trie v) Source # 

Methods

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

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

Foldable (Trie v) Source # 

Methods

fold :: Monoid m => Trie v m -> m #

foldMap :: Monoid m => (a -> m) -> Trie v a -> m #

foldr :: (a -> b -> b) -> b -> Trie v a -> b #

foldr' :: (a -> b -> b) -> b -> Trie v a -> b #

foldl :: (b -> a -> b) -> b -> Trie v a -> b #

foldl' :: (b -> a -> b) -> b -> Trie v a -> b #

foldr1 :: (a -> a -> a) -> Trie v a -> a #

foldl1 :: (a -> a -> a) -> Trie v a -> a #

toList :: Trie v a -> [a] #

null :: Trie v a -> Bool #

length :: Trie v a -> Int #

elem :: Eq a => a -> Trie v a -> Bool #

maximum :: Ord a => Trie v a -> a #

minimum :: Ord a => Trie v a -> a #

sum :: Num a => Trie v a -> a #

product :: Num a => Trie v a -> a #

Traversable (Trie v) Source # 

Methods

traverse :: Applicative f => (a -> f b) -> Trie v a -> f (Trie v b) #

sequenceA :: Applicative f => Trie v (f a) -> f (Trie v a) #

mapM :: Monad m => (a -> m b) -> Trie v a -> m (Trie v b) #

sequence :: Monad m => Trie v (m a) -> m (Trie v a) #

FixedTraversable (Trie v) Source # 

Methods

traverseF :: (Fixed g, Fixed g', Applicative h, (* ~ a) (Alg (Trie v))) => (a -> h b) -> g (Trie v) -> h (g' (Sub (Trie v) a b)) Source #

FixedFoldable (Trie v) Source # 

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (Trie v))) => (a -> m) -> g (Trie v) -> m Source #

FixedFunctor (Trie v) Source # 

Methods

fmapF :: (Fixed g, Fixed g', (* ~ a) (Alg (Trie v))) => (a -> b) -> g (Trie v) -> g' (Sub (Trie v) a b) Source #

FixedSub (Trie v) Source # 

Associated Types

type Sub (Trie v :: * -> *) v v' :: * -> * Source #

FixedAlg (Trie v) Source # 

Associated Types

type Alg (Trie v :: * -> *) :: * Source #

(Read v, Read a) => Read (Trie v a) Source # 

Methods

readsPrec :: Int -> ReadS (Trie v a) #

readList :: ReadS [Trie v a] #

readPrec :: ReadPrec (Trie v a) #

readListPrec :: ReadPrec [Trie v a] #

(Show v, Show a) => Show (Trie v a) Source # 

Methods

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

show :: Trie v a -> String #

showList :: [Trie v a] -> ShowS #

Generic (Trie v a) Source # 

Associated Types

type Rep (Trie v a) :: * -> * #

Methods

from :: Trie v a -> Rep (Trie v a) x #

to :: Rep (Trie v a) x -> Trie v a #

(Binary v, Binary a) => Binary (Trie v a) Source # 

Methods

put :: Trie v a -> Put #

get :: Get (Trie v a) #

putList :: [Trie v a] -> Put #

type Alg (Trie v) Source # 
type Alg (Trie v) = v
type Sub (Trie v) v v' Source # 
type Sub (Trie v) v v' = Trie v'
type Rep (Trie v a) Source # 
type Rep (Trie v a) = D1 (MetaData "Trie" "Data.FixFile.Trie" "fixfile-0.4.0.0-6Rx1TzJaeAW4euV9dndAsy" False) ((:+:) ((:+:) (C1 (MetaCons "Value" PrefixI False) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 v))) ((:+:) (C1 (MetaCons "Tail" PrefixI False) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Maybe a)))) (C1 (MetaCons "String" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Maybe a))) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 ByteString)) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 a))))))) ((:+:) (C1 (MetaCons "Small" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Maybe a))) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 [(Word8, a)])))) ((:+:) (C1 (MetaCons "Big" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Maybe a))) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Array Word8 (Maybe a)))))) (C1 (MetaCons "Mutable" PrefixI False) ((:*:) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Maybe a))) (S1 (MetaSel (Nothing Symbol) NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (Map Word8 a))))))))

empty :: Fixed g => g (Trie v) Source #

An empty Trie

freeze :: Fixed g => g (Trie v) -> g (Trie v) Source #

freeze takes a Trie that has been mutated and creates a copy of it that allows for faster lookups. This happens automatically for Tries that are serialized to a FixFile. A Trie will be automatically thawed on any node that is modified.

createTrieFile :: (Binary v, Typeable v) => FilePath -> IO (FixFile (Ref (Trie v))) Source #

Create a FixFile of (Trie v) data.

openTrieFile :: (Binary v, Typeable v) => FilePath -> IO (FixFile (Ref (Trie v))) Source #

Open a FixFile of (Trie v) data.

lookupTrie :: Fixed g => ByteString -> g (Trie v) -> Maybe v Source #

Lookup a possible value stored in a trie for a given ByteString key.

insertTrie :: Fixed g => ByteString -> v -> g (Trie v) -> g (Trie v) Source #

Insert a value into a trie for the given ByteString key.

deleteTrie :: Fixed g => ByteString -> g (Trie v) -> g (Trie v) Source #

Delete a value from a trie for a given ByteString key.

iterateTrie :: Fixed g => ByteString -> g (Trie v) -> [(ByteString, v)] Source #

Iterate over a Trie for all of the ByteString and value tuples for a given ByteString prefix.