[Haskell-cafe] A very nontrivial parser

Jonathan Cast jcast at ou.edu
Wed Jul 4 16:53:21 EDT 2007


On Wednesday 04 July 2007, Andrew Coppin wrote:
> Well, I eventually got it to work correctly... (!)
>
> My goal is to be able to stack multiple parsers one on top of the other
> - but be able to *change* the stack half way through parsing if needed.
> This I eventually succeeded in doing. The external interface is fairly
> simple, but the type signatures are NOT. (!!)
>
>
>
> My basic idea was to abstract the data source that a parser gets its
> data from:
>
>   class Source s where
>     empty :: s x -> Bool
>     fetch :: s x -> (x, s x)
>
>   instance Source [] where   -- Nice syntax... :-S
>     empty = null
>     fetch xs = (head xs, tail xs)
>
> Now I can define a parser type. But... uh... there's a slight glitch.
> What I *want* to say is
>
>   Parser state in out = ...
>
> But what I ended up with is
>
>   newtype Parser state src x y = Parser ((state, src x) -> (state, src
> x, y))

<snip>

> One problem remains... That pesky source type. Every time I mention a
> parser, I have to say what kind of course object it reads from - even
> though all parsers work with *any* source object! (That's the whole
> point of the Source class.) I really want to get rid of this. (See, for
> example, the type signature for "stacked". Yuck!) Also, every time I
> write a simple parser, I get a compile-time error saying something about
> a "monomorphism restriction" or something... If I add an explicit type
> it goes away, but it's very annoying to keep typing things like
>
>   test7 :: (Source src) => Parser state src Int Int
>
> and so forth. And I can't help thinking if I could just get *rid* of
> that stupid source type in the signature, there wouldn't be a problem...
>
> Anybody have a solution to this?

newtype Parser state x y
  = Parser (forall src. Source src => (state, src x) -> (state, src x, y))

Definition of monad functions, etc, works exactly as for your version, but 
this way all your parsers have polymorphic implementation types, but none has 
a type that trips the monomorphism restriction.  There's some kind of 
argument here in the debate about the monomorphism restriction, but I'm not 
sure if it's for or against . . . [1]

Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs

[1] http://www.lysator.liu.se/c/duffs-device.html


More information about the Haskell-Cafe mailing list