Luke Palmer wrote:
On Thu, Jan 28, 2010 at 12:42 PM, Andrew Coppin
<andrewcop...@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. ;-)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
