I have little experience with algebraic data types, because I work in a language without native support. Usually one can use continuation passing style to get a remotely similar experience, but the handling of CPS encoded types is less comfortable.
Considering this why would a library like Parsec use CPS?
newtype ParsecT s u m a
= ParsecT {unParser :: forall b .
State s u
-> (a -> State s u -> ParseError -> m b) -- consumed ok
-> (ParseError -> m b) -- consumed err
-> (a -> State s u -> ParseError -> m b) -- empty ok
-> (ParseError -> m b) -- empty err
-> m b
}
One clue would be the try parser, which rules out the consumed error case by passing the empty error continuation in both cases:
try :: ParsecT s u m a -> ParsecT s u m a
try p =
ParsecT $ \s cok _ eok eerr ->
unParser p s cok eerr eok eerr
-- ^^^^ ^^^^
This is possible, because both continuations cerr and eerr have the same type and only differ in their position, which reminds me of structural typing. While I think you cannot do this with ADTs, there is probably a way to implement the same behavior with them. Apart from this, a single combinator wouldn't justify the far-reachuing decision to rely on CPS. So why was this decision made?
This change was made March 2, 2009 in commit a98a3ccb by Antoine Latter. The commit comment was just:
commit a98a3ccbca9835fe749b8cd2d475a0494a84a460
Author: Antoine Latter <aslatter@gmail.com>
Date: Mon Mar 2 00:20:00 2009 +0000
move core data type over to CPS
and it replaced the original ADT for ParsecT:
data ParsecT s u m a
= ParsecT { runParsecT :: State s u -> m (Consumed (m (Reply s u a))) }
with the new version in your question, adding a runParsecT adapter to convert everything back:
runParsecT :: Monad m => ParsecT s u m a -> State s u -> m (Consumed (m (Reply s u a)))
runParsecT p s = unParser p s cok cerr eok eerr
where cok a s' err = return . Consumed . return $ Ok a s' err
cerr err = return . Consumed . return $ Error err
eok a s' err = return . Empty . return $ Ok a s' err
eerr err = return . Empty . return $ Error err
I see that he made a blog post in February 2009 where he wrote about finally understanding CPS style and wrote about a CPS version of MaybeT. He didn't talk about any performance advantages, but merely noted that the CPS style had the advantage that Monad and MonadPlus instances for MaybeT could be written without calling >>= or return on the underlying monad or doing explicit case analysis of Maybe values.
In a later December 2009 blog post, he writes about his "obsession with functionalizing monad transformers", gives an example of ErrorT and explicitly notes:
I haven't benchmarked whether or not this is faster for anything, but I find the whole thing a lot of fun.
However, he then goes on in the same blog post to talk about how adding functionality to Parsec 3 to make it a monad transformer instead of a plain old monad and parametrizing it over the input type led to poor performance (about 1.8x slower on some benchmarks). He discovered that converting over to CPS style made Parsec 3 as fast as Parsec 2, at least when those new abstractions (transformers) weren't being used.
Speculating about the timing, I think that Antoine thought CPS was "cool" and had stylistic advantages that appealed to him, so he had it top of mind when working on Parsec 3. When new abstractions in Parsec 3 led to a performance problem, he fortuitously discovered that converting it to CPS appeared to fix them, though he didn't do a detailed study of why (just some speculation in the blog post). However, it's a little unclear to me if he actually converted to CPS first, before discovering the performance advantage, or tried CPS with the expectation that it might help performance. The blog post reads like the conversion was done intentionally to address performance, but that might have just been for sake of simpler exposition in the blog post.