Cyclic Type-synonyms

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Cyclic Type-synonyms

Christophe Poucet
Hello,

I use the Indirect Composite pattern a lot, and this means that typically, especially with recursive types (such as an AST), you end up with a lot of data-constructors.  I understand that it is not possible to have pure cyclic types (because haskell requires iso-recursive and not equi-recursive types).  However I wonder why certain cases can not be allowed. 

For instance, assume the following somewhat simplified AST:

data Exp e =
    ELet String e e    -- let x = a in b
  | ECond e e e       -- If then else construct

Now if I wanted to decorate this structure, I would use something like:

data AnnotExp a = AE {
  unAE :: Exp (AnnotExp a),
  note :: a
}

However, and this example might be slightly too trivial to motivate it, however it does exemplify what can be done, one might not want to annotate at all and just have a recursive data AST.  At this point, one either uses AnnotExp () or creates a new data type.  It would be nice if instead one could use cyclic type-declarations, with the knowledge that we're going through a data-constructor and hence the type iso-recursive and not equi-recursive:

type AST = Exp AST  -- This is iso-recursive as it goes through the data constructors ELet and ECond

Sadly this is not possible with the current GHC (I'm using 6..4.2).  Is this possible with 6.6?  Is there any reason why this is not possible.  Feedback regarding this is welcome.  A more motivating example can be seen below.

Cheers,
Christophe

-----------------------------
data Exp var ident func exp stm =
    ELit Lit                -- ^ Literals
  | EVar ident              -- ^ Identifiers
  | EData Const [exp]       -- ^ Data Constructors
  | ECall func              -- ^ Function Calls
  | ELet var stm stm        -- ^ Scoping
  | ECond exp stm stm       -- ^ Conditional
  | ELoop exp stm           -- ^ Looping
  deriving (Eq, Show)

data AExp exp annot = AExp {
  unAExp    :: exp,
  aexpNote  :: annot,
  aexpLoc   :: Location
}

type UnCorExp var annot =
  Exp
    var                                   -- ^ Let-binders
    var                                   -- ^ Named identifiers
    (Ident, [AExp UnCorExp var annot])    -- ^ Function calls
    (AExp UnCorExp var annot)             -- ^ Expressions
    (AExp UnCorExp var annot)             -- ^ Statements

-- Flattened AST: function parameters can only be variables, similar for while- and if- conditions
type UnSimExp var annot 
  Exp
    var                                   -- ^ Let-binders
    var                                   -- ^ Named identifiers
    (Ident, [var])                        -- ^ Function calls
    (var)                                 -- ^ Expressions
    (AExp UnSimExp var annot)             -- ^ Statements


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Cyclic Type-synonyms

Christophe Poucet
Addendum:
(18:19:50) vincenz: anyways the haskell-cafe post is orthogonal to this safety issue
(18:20:46) vincenz: it's about the inability to use a generic annotation data-type with any generic indirect composite ADT without introducing a third data constructor if one wants recursion
(18:21:33) vincenz: data Foo a = A a; date Note a n = Note { data :: a, info :: n} ; type RecNoteFoo = Note (Foo RecNoteFoo) Int
(18:25:53) audreyt: vincenz: that is a good summary.
(18:26:17) audreyt: sugar selectors, smart constructors, SYB, etc.
(18:26:24) audreyt: but the core problem seems like a real limitation

On 7/5/06, Christophe Poucet <[hidden email]> wrote:
Hello,

I use the Indirect Composite pattern a lot, and this means that typically, especially with recursive types (such as an AST), you end up with a lot of data-constructors.  I understand that it is not possible to have pure cyclic types (because haskell requires iso-recursive and not equi-recursive types).  However I wonder why certain cases can not be allowed. 

For instance, assume the following somewhat simplified AST:

data Exp e =
    ELet String e e    -- let x = a in b
  | ECond e e e       -- If then else construct

Now if I wanted to decorate this structure, I would use something like:

data AnnotExp a = AE {
  unAE :: Exp (AnnotExp a),
  note :: a
}

However, and this example might be slightly too trivial to motivate it, however it does exemplify what can be done, one might not want to annotate at all and just have a recursive data AST.  At this point, one either uses AnnotExp () or creates a new data type.  It would be nice if instead one could use cyclic type-declarations, with the knowledge that we're going through a data-constructor and hence the type iso-recursive and not equi-recursive:

type AST = Exp AST  -- This is iso-recursive as it goes through the data constructors ELet and ECond

Sadly this is not possible with the current GHC (I'm using 6..4.2).  Is this possible with 6.6?  Is there any reason why this is not possible.  Feedback regarding this is welcome.  A more motivating example can be seen below.

Cheers,
Christophe

-----------------------------
data Exp var ident func exp stm =
    ELit Lit                -- ^ Literals
  | EVar ident              -- ^ Identifiers
  | EData Const [exp]       -- ^ Data Constructors
  | ECall func              -- ^ Function Calls
  | ELet var stm stm        -- ^ Scoping
  | ECond exp stm stm       -- ^ Conditional
  | ELoop exp stm           -- ^ Looping
  deriving (Eq, Show)

data AExp exp annot = AExp {
  unAExp    :: exp,
  aexpNote  :: annot,
  aexpLoc   :: Location
}

type UnCorExp var annot =
  Exp
    var                                   -- ^ Let-binders
    var                                   -- ^ Named identifiers
    (Ident, [AExp UnCorExp var annot])    -- ^ Function calls
    (AExp UnCorExp var annot)             -- ^ Expressions
    (AExp UnCorExp var annot)             -- ^ Statements

-- Flattened AST: function parameters can only be variables, similar for while- and if- conditions
type UnSimExp var annot 
  Exp
    var                                   -- ^ Let-binders
    var                                   -- ^ Named identifiers
    (Ident, [var])                        -- ^ Function calls
    (var)                                 -- ^ Expressions
    (AExp UnSimExp var annot)             -- ^ Statements



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe