[Haskell-cafe] Hierachical abstraction

[Andrew Coppin]

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
>> parse?
>>     
>
> 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.
>   

Hmm, OK.

> So you're interested in structures which are all similar in a way.
>   

Basically, yes.

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. ;-)