On Thu, Jan 28, 2010 at 12:42 PM, Andrew Coppin <[email protected]> wrote: > 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
