racket - 如何在Typed Racket中定义Union多态数据结构的实例？

Question

来自 Typed Racket Guide ，要定义联合类型，只需使用 (define-type Some-Type (U Type1 Type2))。

要定义多态数据结构，请使用类似 (define-type (Opt a) (U ...)) 的内容。

我想定义一个多态二叉树

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

我想知道为什么t1的类型是Leaf而不是Tree，以及如何使其成为Tree？

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

Answer 1

当你这样做时:

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

您将 Tree 定义为类型构造函数。您不应该将 Tree 本身视为一种类型，而仅将 (Tree Some-Concrete-Type) 视为一种类型。因此将其重命名为 Treeof:

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

现在问题更清楚了。节点结构需要一个 Treeof，但是什么树呢？你想要的是这样的:

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

现在您的示例可以运行了:

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