On Thu, Jan 28, 2010 at 12:42 PM, Andrew Coppin
I wonder if you can make a parser combinator library which is *not* monadic? And, if you could, in what way would that limit the kinds of things you can parse?
Absolutely! I believe both Applicatives and Arrows were originally invented for parsers. I could be mistaken, but at least there are both Applicative and Arrow parser libraries. I don't know how to classify the language that they parse -- it is not strictly context-free. It corresponds roughly to context-free where certain types of infinite chains are allowed. Anyway they are less expressive than Parsec, but more efficient and optimizable, for reasons you correctly identified.
I'm basically looking at a problem which is like this. There are primitive constructs, and there are more sophisticated abstractions built from these, and I would like to come up with a system where abstractions are first-class, new abstractions can be added, and for any particular data structure, you can statically guarantee which abstractions are or aren't present.
So you're interested in structures which are all similar in a way. GHC converting between different representations has advantages *because* the representations are so different -- different optimization opportunities are apparent in each one that aren't available in the others. But at the very least for extensibility people want to have AST-like structures which have different features, and those features are statically guaranteed. I don't remember the name, but there is a technique where you compose the features you want and then take its fixed point to get your AST. You can make a typeclass for each feature that uses it on any data structure in which it is present. Not the prettiest thing ever, but fairly powerful. Luke