Data.RadixTree

Documentation

data RadixTree

A radixtree. Construct with fromFoldable, and use with parse.

Constructors

RadixAccept !Text !(Vector RadixNode)

Can terminate a parser successfully, returning the Text value given.

RadixSkip !(Vector RadixNode)

Instances

Eq RadixTree

Methods

(==) :: RadixTree -> RadixTree -> Bool

(/=) :: RadixTree -> RadixTree -> Bool

Data RadixTree

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> RadixTree -> c RadixTree

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c RadixTree

toConstr :: RadixTree -> Constr

dataTypeOf :: RadixTree -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c RadixTree)

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c RadixTree)

gmapT :: (forall b. Data b => b -> b) -> RadixTree -> RadixTree

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> RadixTree -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> RadixTree -> r

gmapQ :: (forall d. Data d => d -> u) -> RadixTree -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> RadixTree -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> RadixTree -> m RadixTree

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> RadixTree -> m RadixTree

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> RadixTree -> m RadixTree

Show RadixTree

Methods

showsPrec :: Int -> RadixTree -> ShowS

show :: RadixTree -> String

showList :: [RadixTree] -> ShowS

NFData RadixTree

Methods

rnf :: RadixTree -> ()

Store RadixTree

Methods

size :: Size RadixTree

poke :: RadixTree -> Poke ()

peek :: Peek RadixTree

RadixParsing RadixTree

Methods

parse :: CharParsing m => RadixTree -> m Text

data RadixNode

A node in a radixtree. To advance from here a parser must parse the Text (i.e., the prefix) value at this node.

Constructors

RadixNode !Text !RadixTree

Instances

Eq RadixNode

Methods

(==) :: RadixNode -> RadixNode -> Bool

(/=) :: RadixNode -> RadixNode -> Bool

Data RadixNode

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> RadixNode -> c RadixNode

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c RadixNode

toConstr :: RadixNode -> Constr

dataTypeOf :: RadixNode -> DataType

dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c RadixNode)

dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c RadixNode)

gmapT :: (forall b. Data b => b -> b) -> RadixNode -> RadixNode

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> RadixNode -> r

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> RadixNode -> r

gmapQ :: (forall d. Data d => d -> u) -> RadixNode -> [u]

gmapQi :: Int -> (forall d. Data d => d -> u) -> RadixNode -> u

gmapM :: Monad m => (forall d. Data d => d -> m d) -> RadixNode -> m RadixNode

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> RadixNode -> m RadixNode

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> RadixNode -> m RadixNode

Show RadixNode

Methods

showsPrec :: Int -> RadixNode -> ShowS

show :: RadixNode -> String

showList :: [RadixNode] -> ShowS

NFData RadixNode

Methods

rnf :: RadixNode -> ()

Store RadixNode

Methods

size :: Size RadixNode

poke :: RadixNode -> Poke ()

peek :: Peek RadixNode

data CompressedRadixTree

A normal RadixTree stores a new Text at every node. In contrast, a CompressedRadixTree takes a single corpus Text which is indexed into by nodes. This can save a lot of memory (e.g., using the radix trees from the parsing benchmarks in this package, the CompressedRadixTree version is 254032 bytes, whereas the ordinary RadixTree is a rotund 709904 bytes) at no runtime cost.

Instances

NFData CompressedRadixTree

Methods

rnf :: CompressedRadixTree -> ()

RadixParsing CompressedRadixTree

Methods

parse :: CharParsing m => CompressedRadixTree -> m Text

Construction

fromFoldable :: Foldable f => f Text -> RadixTree

• Slow*

compressBy :: Text -> RadixTree -> Maybe CompressedRadixTree

Compress a RadixTree given a corpus. All values in the tree be findable within the corpus, though the corpus does not have to necessarily be the direct source of the tree

Parsing with radix trees

class RadixParsing radixtree where

Minimal complete definition

parse

Methods

parse :: CharParsing m => radixtree -> m Text

Instances

RadixParsing CompressedRadixTree

Methods

parse :: CharParsing m => CompressedRadixTree -> m Text

RadixParsing RadixTree

Methods

parse :: CharParsing m => RadixTree -> m Text

search :: (Monad m, CharParsing m, RadixParsing radixtree) => radixtree -> m [Text]

Find all occurences of the terms in a RadixTree from this point on. This will consume the entire remaining input. Can lazily produce results (but this depends on your parser).