CODEWITHSUNDEEP
rackettyped-racket
alwaysday1
alwaysday1

Reputation: 1783

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

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>

Upvotes: 2

Views: 453

Answers (2)

Alex Knauth
Alex Knauth

Reputation: 8373

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))

Upvotes: 4

Sorawee Porncharoenwase
Sorawee Porncharoenwase

Reputation: 6502

Please see the reference about subtyping (https://docs.racket-lang.org/ts-guide/types.html#%28part._.Subtyping%29). Basically, when you use the union type, Racket doesn't destruct old types. For example, you could define a type (U String Number), but String and Number would still be usable. 1 would still be recognized as Number, but you can use it in any places that expects (U String Number) because Number is a subtype of (U String Number).

Similarly, t1 is a Leaf, so there's nothing wrong that Racket reports that t1 is a Leaf. However, Leaf is a subtype of Tree, so t1 could be used in places where Tree is expected.

Upvotes: 1

Related Questions