How to define Union polymorphic data structure's instance in Typed Racket?

Question

From The Typed Racket Guide, to define a Union Type, just use (define-type Some-Type (U Type1 Type2)).

To define Polymorphic Data Structures, use something like (define-type (Opt a) (U ...)).

I want to define a polymorphic binary tree

(define-type (Tree a) (U (Leaf a) Node))
(struct (a) Leaf ([val : a]))
(struct Node ([left : Tree] [right : Tree]))
(define t1 (Leaf 5))
(define t2 (Leaf 8))
(define t3 (Node t1 t2))

I was wondering why the type of t1 is Leaf not Tree, and how to make it be a Tree ?

> t1
- : (Leaf Positive-Byte)
#<Leaf>

Alex Knauth Alex Knauth · Accepted Answer · 2016-01-16T19:26:16

When you do this:

(define-type (Tree a) (U (Leaf a) Node))

You're defining Tree as a type constructor. You shouldn't think of Tree itself as a type, only (Tree Some-Concrete-Type) as a type. So rename it to Treeof:

(define-type (Treeof a) (U (Leaf a) Node))
(struct (a) Leaf ([val : a]))
(struct Node ([left : Treeof] [right : Treeof]))

Now the problem is clearer. The node struct expects a Treeof, but a tree of what? What you want is this:

(define-type (Treeof a) (U (Leaf a) (Node a)))
(struct (a) Leaf ([val : a]))
(struct (a) Node ([left : (Treeof a)] [right : (Treeof a)]))

Now your example works:

#lang typed/racket
(define-type (Treeof a) (U (Leaf a) (Node a)))
(struct (a) Leaf ([val : a]))
(struct (a) Node ([left : (Treeof a)] [right : (Treeof a)]))
(define t1 (Leaf 5))
(define t2 (Leaf 8))
(define t3 (Node t1 t2))

How to define Union polymorphic data structure's instance in Typed Racket?

2 Answers