On Tue, Mar 22, 2011 at 3:14 PM, Mario Blažević <mblaze...@stilo.com> wrote: > The first version of incremental-parser has been released on Hackage > [1]. It's yet another parser combinator > library, providing the usual set of Applicative and Monad combinators. Apart > from this, it has three twists that make it > unique. > > First, the parser is incremental. That means it can be fed its input in > chunks, and in proper circumstances it can > also provide the parsed output in chunks. For this to be possible the result > type must be a Monoid. The complete parsing > result is then a concatenation of the partial results. > > In order to make the incremental parsing easier, the combinator set is > optimized for monoidal results. The usual > combinator many1, for example, assumes the result type is a monoid and > concatenates its components instead of > constructing a list. > > In Parsec: >> many1 :: Stream s m t => ParsecT s u m a -> ParsecT s u m [a] > > In incremental-parser: >> many1 :: (Monoid s, Monoid r) => Parser s r -> Parser s r > > > The second weirdness is that the the parser is generic in its input > stream type, but this type is parameterized in a > holistic way. There is no separate token type. Primitive parsers that need > to peek into the input require its type to be > an instance of a monoid subclass. > > In Parsec: >> string :: Stream s m Char => String -> ParsecT s u m String >> char :: Stream s m Char => Char -> ParsecT s u m Char >> anyToken :: (Stream s m t, Show t) => ParsecT s u m t > > In Attoparsec: >> string :: ByteString -> Parser ByteString >> word8 :: Word8 -> Parser Word8 >> anyWord8 :: Parser Word8 > > In incremental-parser: >> string :: (LeftCancellativeMonoid s, MonoidNull s) => s -> Parser s s >> token :: (Eq s, FactorialMonoid s) => s -> Parser s s >> anyToken :: FactorialMonoid s => Parser s s > > The monoid subclasses referenced above provide methods for analyzing and > subdividing the input stream. The classes > are not particularly demanding, and any reasonable input stream should be > able to accommodate them easily. The library > comes with instances for lists, ByteString, and Text. > >> class Monoid m => MonoidNull m where >> mnull :: m -> Bool > >> class Monoid m => LeftCancellativeMonoid m where >> mstripPrefix :: m -> m -> Maybe m > >> class Monoid m => FactorialMonoid m where >> factors :: m -> [m] >> primePrefix :: m -> m >> ... > > > Finally, the library being implemented on the basis of Brzozowski > derivatives, it can provide both the symmetric and > the left-biased choice, <|> and <<|>. This is the same design choice made by > Text.ParserCombinators.ReadP and > uu-parsinglib. Parsec and its progeny on the other hand provide only the > faster left-biased choice, at some cost to the > expressiveness of the combinator language. > > [1] http://hackage.haskell.org/package/incremental-parser-0.1
This seems very interesting. One question: > The MonadPlus and the Alternative instance differ: the former's mplus > combinator equals the asymmetric <<|> choice. Why? > > > _______________________________________________ > Libraries mailing list > librar...@haskell.org > http://www.haskell.org/mailman/listinfo/libraries > > -- Work is punishment for failing to procrastinate effectively. _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell