[Haskell-cafe] monadic DSL for compile-time parser generator, not possible?

[Jacques Carette]

On 13-03-12 04:06 PM, Jeremy Shaw wrote:
> It would be pretty damn cool if you could create a data type for
> generically describing a monadic parser, and then use template haskell
> to generate a concrete parser from that data type. [...]
> I would like to suggest that while it would be cool, it is
> impossible.

Impossibility proofs are notoriously difficult.  You showed that this 
approach:

>> data ParserSpec a where
>>      AnyChar :: ParserSpec Char
>>      Return  :: a -> ParserSpec a
>>      Join    :: ParserSpec (ParserSpec a) -> ParserSpec a
>>      FMap    :: (a -> b) -> ParserSpec a -> ParserSpec b

does not work.  The flaw is indeed in FMap.  It should not take a 
function as first argument, but rather a *description* of a function 
(the same way ParserSpec gives you a description of a parser).  Then you 
can make it work, if your 'description' language is adequate.

For some strange reason, I am biased towards 'finally tagless' 
descriptions, but YMMV.

Jacques