[Haskell-cafe] ANNOUNCE: incremental-parser library package

[Gábor Lehel]

On Tue, Mar 22, 2011 at 3:14 PM, Mario Blažević <mblazevic at 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
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>



-- 
Work is punishment for failing to procrastinate effectively.