Re:What the heck is a parser-combinator?
by Mehdi2277 on Wednesday June 21, 2017 @05:08AM
(#14602163)
Yeah that type is enough to make a monad. In slightly fancy language the type you just wrote is just StateT Input Maybe. Monadic mostly makes me think of bind which is just about chaining (technically also return is needed, but here return is just always succeed and give that value) and parsers have a natural notion of run one after the other.
It's only a monad if you define it to be. It's also "just" an applicative if you like. The monadic part arises when people actually _use_ bind and then you lose some information that might be nice for optimizations.
Re:What the heck is a parser-combinator?
by lomnakkus on Wednesday June 21, 2017 @07:39AM
(#14602798)
> In slightly fancy language the type you just wrote is just StateT Input Maybe.
Except the newtype -- which was kind of my point :).
Re:What the heck is a parser-combinator?
by chombier on Wednesday June 21, 2017 @06:13AM
(#14602451)
I realize I misread parent comment functions:
always<A>(x: A): Parser<A>
thenDependent<A, B>(a: Parser<A>, b: A -> Parser<B>): Parser<(A, B)>
always<A>(x: A): Parser<A>
thenDependent<A, B>(a: Parser<A>, b: A -> Parser<B>): Parser<B>
Of course you don't have to write parser combinators that way, but I found it pretty practical compared to dealing with nested tuples for the sequence parser. Check out Hutton and Meijer's article for more details.
The problem with monadic parsers is that they are too powerful. If you have two options
string "foo" <|> string "for"
string "fo" >> (char 'o' <|> char 'r')
Applicative parsers are less powerful so we can left factor them automatically. There were some attempts to combine applicative and monadic parsers which resulted in arrow syntax but that kind of feels like the worst of both worlds for many cases.
For anyone following along at home: think function which takes input + current position and may return: "Nothing" if the parser doesn't match, or "a value of type t along with the rest of the unparsed input".
(Obviously it'd have to be expanded to support errors properly, etc.)
EDIT: Of course, I guess you could argue that they just are monadic by definition since chaining using function composition and parameter passing is the essence of a monad... Maybe that's what you were driving at?