[Haskell-cafe] Hierachical abstraction
lrpalmer at gmail.com
Thu Jan 28 15:31:39 EST 2010
On Thu, Jan 28, 2010 at 12:42 PM, Andrew Coppin
<andrewcoppin at btinternet.com> 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
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
> 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
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
More information about the Haskell-Cafe