[Haskell-cafe] Variants of a recursive data structure

[Niklas Broberg]

Oops again, not only am I addicted to flags, I also don't think before
I write. Sorry for spamming like this. :-(

The definition of the Or class I gave is incorrect. Of course it needs
a functional dependency to work correctly, like this:

class (TBool a, TBool b, TBool c) => Or a b c | a b -> c

instance Or TFalse TFalse TFalse
instance (TBool x) => Or TTrue x TTrue
instance Or TFalse TTrue TTrue

Still no flags needed as there is no overlap between the instances.
And this time I've actually verified that it works. ;-)

/Niklas

On 8/3/06, Niklas Broberg <niklas.broberg at gmail.com> wrote:
> Oops, sorry, I think I'm getting too addicted to flags. ;-)
> The module I wrote actually doesn't need neither overlapping nor
> undecidable instances, so just -fglasgow-exts will do just fine.
>
> /Niklas
>
> On 8/3/06, Niklas Broberg <niklas.broberg at gmail.com> wrote:
> > If you want the non-labelledness to be guaranteed by the type system,
> > you could combine a GADT with some type level hackery. Note the flags
> > to GHC - they're not that scary really. :-)
> >
> > In the following I've used the notion of type level booleans (TBool)
> > to flag whether or not an expression could contain a label or not. A
> > term of type Exp TFalse is guaranteed to not contain any labels, a
> > term of type Exp TTrue is guaranteed *to* contain at least one label
> > somewhere in the tree, and a term Exp a could contain a label, but
> > doesn't have to.
> >
> > ---------------------------------------------------------------------------
> > {-# OPTIONS_GHC -fglasgow-exts -fallow-overlapping-instances
> > -fallow-undecidable-instances #-}
> > module Exp where
> >
> > data TTrue
> > data TFalse
> >
> > class TBool a
> > instance TBool TTrue
> > instance TBool TFalse
> >
> > class (TBool a, TBool b, TBool c) => Or a b c
> >
> > instance Or TFalse TFalse TFalse
> > instance (TBool x, TBool y) => Or x y TTrue
> >
> > data TBool l => Exp l where
> >  Num :: Int -> Exp TFalse
> >  Add :: Or a b c => Exp a -> Exp b -> Exp c
> >  Label :: String -> Exp a -> Exp TTrue
> >
> > type SimpleExp = Exp TFalse
> >
> > unlabel :: Exp a -> SimpleExp
> > unlabel n@(Num _) = n
> > unlabel (Add x y) = Add (unlabel x) (unlabel y)
> > unlabel (Label _ x) = unlabel x
> > -------------------------------------------------------------------------------
> >
> > Cheers,
> >
> > /Niklas
> >
> > On 8/3/06, Klaus Ostermann <ostermann at informatik.tu-darmstadt.de> wrote:
> > > Hi all,
> > >
> > > I have a problem which is probably not a problem at all for Haskell experts,
> > > but I am struggling with it nevertheless.
> > >
> > > I want to model the following situation. I have ASTs for a language in two
> > > variatns: A "simple" form and a "labelled" form, e.g.
> > >
> > > data SimpleExp = Num Int | Add SimpleExp SimpleExp
> > >
> > > data LabelledExp = LNum Int String | LAdd LabelledExp LabelledExp String
> > >
> > > I wonder what would be the best way to model this situation without
> > > repeating the structure of the AST.
> > >
> > > I tried it using a fixed point operator for types like this:
> > >
> > > data Exp e = Num Int | Add e e
> > >
> > > data Labelled a = L String a
> > >
> > > newtype Mu f = Mu (f (Mu f))
> > >
> > > type SimpleExp = Mu Exp
> > >
> > > type LabelledExp = Mu Labelled Exp
> > >
> > > The "SimpleExp" definition works fine, but the LabeledExp definition doesn't
> > > because I would need something like "Mu (\a -> Labeled (Exp a))" where "\"
> > > is a type-level lambda.
> > >
> > > However, I don't know how to do this in Haskell. I'd need something like the
> > > "." operator on the type-level. I also wonder whether it is possible to
> > > curry type constructors.
> > >
> > > The icing on the cake would be if it would also be possible to have a
> > > function
> > >
> > > unlabel :: LabeledExp -> Exp
> > >
> > > that does *not* need to know about the full structure of expressions.
> > >
> > > So, what options do I have to address this problem in Haskell?
> > >
> > > Klaus
> > >
> > > _______________________________________________
> > > Haskell-Cafe mailing list
> > > Haskell-Cafe at haskell.org
> > > http://www.haskell.org/mailman/listinfo/haskell-cafe
> > >
> >
>