[Haskell-cafe] Hierachical abstraction
andrewcoppin at btinternet.com
Fri Jan 29 13:45:10 EST 2010
Luke Palmer wrote:
> 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 have no idea what Applicative is, but I understand that one of the
main ideas behind Arrows is the ability to analyse the finished computation.
(Also, not all arrows support using the result of an arrow as the
continuation - and those that do are isomorphic to monads. So it seems
to be just another example of how limiting what you can do allows you to
make bigger guarantees...)
> 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.
> So you're interested in structures which are all similar in a way.
Stuff like... a circle can be represented as a point and a radius. But
you can also represent it as a vast profusion of straight line segments.
Now I could design an algebraic data type that can represent circles and
lines, but then how do I guarantee that a particular expression contains
no circles, only lines? GADTs presumably.
But now suppose that I want not just circles, but *anything* that can
possibly be reduced to line segments. An algebraic data type,
generalised or not, has the property that it is "closed", and cannot be
added to once created. (I.e., you can't add new constructors later.)
Interestingly, you can write a class for "things that can be turned into
line segments", and an existential wrapper to type-cast any shape into a
universal type. But you can't cast it back again. You certainly can't do
pattern matching on it like you can with a case-expression over a
regular ADT. I've been pondering this today...
> 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.
Interesting... but vague. ;-)
More information about the Haskell-Cafe