如何在 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

请参阅有关子类型的参考资料 (https://docs.racket-lang.org/ts-guide/types.html#%28part._.Subtyping%29)。基本上，当您使用联合类型时，Racket 不会破坏旧类型。例如，您可以定义类型 (U String Number)，但 String 和 Number 仍然可用。 1 仍会被识别为 Number，但您可以在任何需要 (U String Number) 的地方使用它，因为 Number 是 (U String Number).[=27 的子类型=]

同样，t1 是 Leaf，因此 Racket 报告 t1 是 Leaf 并没有错。但是，Leaf 是 Tree 的子类型，因此 t1 可以用在需要 Tree 的地方。

Answer 2

当你这样做时：

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

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

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

racket

typed-racket