[Haskell-cafe] Regular Expressions without GADTs

[Martin Sulzmann]

GADTs have the problem that they're not extensible,
but type classes are! Imagine if we add regular hedges.
So, I think Oleg has a point here. 

Oleg's solution may look rather cryptic. But if we recall that 
type class instances describe proof systems, then Oleg's solutions 
starts looking quite elegant. Note that the GADTs serve the same
purpose, i.e. encoding proof rules. An interesting question is whether
there's something GADTs can do "better" than type classes and vice
versa.

Here's an example, many regexp algorithms can be formulated
co-inductively. We'll have trouble to encode these algorithms
with "standard" type classes, unless we consider some type
class extensions (if this sounds interesting check out
the "co-induction type class" paper on my home-page).
I don't think this will cause trouble for GADTs.

Martin


Ralf Hinze writes:
 > > The code seems a bit simpler, too.
 > 
 > Do you really think so? To me replacing a GADT by class and
 > instance declarations seems the wrong way round. We should
 > not forget that the DT in GADT stands for `data type'. One
 > could certainly argue that the gist of functional programming
 > is to define a collection of data types and functions that
 > operate on these types. The fact that with GADTs constructors
 > can have more general types just allows us to use the functional
 > design pattern more often (freeing us from the need or temptation
 > to resort to type class hackery with multiple parameter type
 > classes, undecidable instances, functional dependencies etc).
 > 
 > Cheers, Ralf
 > _______________________________________________
 > Haskell-Cafe mailing list
 > Haskell-Cafe at haskell.org
 > http://www.haskell.org/mailman/listinfo/haskell-cafe