[plt-scheme] typed scheme vs. PLAI types

From: keydana at gmx.de (keydana at gmx.de)
Date: Mon Feb 8 15:03:00 EST 2010

Hi all,

I have a (naive and hopefully not too stupid :-;) question about defining algebraic data types in typed scheme.

I would like to define type aliases and algebraic data types for a  relational algebra. I don't know too much of Haskell, but I find algebraic data types helpful to think about data representation, so in order to find an "example" I could then follow in typed scheme,
I started out with the following (just as a first approximation):

type Relation = (Attlist, [Tuple])

type Attlist = [Attribute]
type Attribute = (String, String)

type Tuple = [String]

data Expr = Prop | RelExpr

data RelExpr = Project Relation Attlist 
             | Restrict Relation Prop
             | Join [Relation]

data Prop = Const Bool
          | Is Expr Expr
          | And Prop Prop
          | Or Prop Prop

When I try to do a similar thing in typed scheme, it looks fine for the type aliases, but regarding the algebraic types, it seems to me I have to define structures and then a type alias which defines a union of them:

(define-type-alias Relation (Pair Attlist (Listof Tuple)))

(define-type-alias Attlist (Listof Attribute))
(define-type-alias Attribute (Pair String String))

(define-type-alias Tuple (Listof String))

(define-struct: Project ((rel : Relation) (attl : Attlist)))
(define-struct: Restrict ((rel : Relation) (prop : Prop)))
(define-struct: Join ((rels : (Listof Relation))))

(define-type-alias RelExpr (U Project Restrict Join))

(define-type-alias Expr (U Prop RelExpr))

(define-struct: Is ((expr1 : Expr) (expr2 : Expr)))
(define-struct: And ((expr1 : Expr) (expr2 : Expr)))
(define-struct: Or ((expr1 : Expr) (expr2 : Expr)))

(define-type-alias Prop (U Boolean Is And Or))

This looks rather ugly, especially having structs for the Is, And and Or expressions... I guess this should  be done completely differently, but I don't see how. (So my first question would be, how can I do this better in typed scheme?)

What I would in fact like is a define-type like in PLAI, where it would look like this ( I'm leaving out the aliases, as I don't know how to define them in PLAI):

(define-type Prop
  (CONST (b boolean?))
  (IS (e1 Expr?) (e2 Expr?))
  (AND (p1 Prop?) (p2 Prop?))
  (OR (p1 Prop?) (p2 Prop?)))

(define-type RelExpr
  (Project (r Relation?) (a Attlist?))
  (Restrict (r Relation?) (p Prop?))
  (Join (r1 Relation?) (r2 Relation?)))

My second question is, why does typed scheme not have such a define-type? (I find it very appealing because it makes the algebraic type definition very concise.)

Many thanks in advance,

Posted on the users mailing list.