英文:
How to correctly implement a polymorphic functional Tree data structure in Scala?
问题
我正在尝试找出实现多态树的最佳方法：
trait Tree[A]
case object Void extends Tree[A] // 不能编译通过
case class Node[A](left: Tree[A], key: A, right: Tree[A]) extends Tree[A]
当然，我可以将Void从对象更改为类，或者让它扩展Tree[Any]，但我想知道在Scala中这种Tree的标准实现是什么。谢谢！
英文:
I am trying to figure out the best way to implement a polymorphic tree:
trait Tree[A]
case object Void extends Tree[A] // does not compile
case class Node[A](left: Tree[A], key: A, right: Tree[A]) extends Tree[A]
Surely I can change Void from an object to a class, or I can have it extend Tree[Any], but I was wondering what would be the textbook implementation of this Tree in Scala. Thank you!
答案1
得分: 2
- 要么你使
Tree具有协变性
trait Tree[+A]
case object Void extends Tree[Nothing]
(然后Void是Tree[A]的子类型，适用于任何A)
- 要么你将
Tree保持为不变，然后将Void变成一个类
trait Tree[A]
case class Void[A]() extends Tree[A]
在Scala（和JVM）中，对象（以及通常的值）无法具有多态性。
让Void扩展Tree[Any]是不正确的。然后Void不是Tree[A]的子类型。
原则上，如果你可以在编译时执行所有计算，那么你可以将你的代数数据类型提升到类型级别，使Tree成为一个类型类
trait Tree[A, T]
case object Void
type Void = Void.type
case class Node[A, L, R](left: L, key: A, right: R)
implicit def voidTree[A]: Tree[A, Void] = new Tree[A, Void] {}
implicit def nodeTree[A, L, R](implicit
leftTree: Tree[A, L],
rightTree: Tree[A, R]
): Tree[A, Node[A, L, R]] = new Tree[A, Node[A, L, R]] {}
英文:
- Either you make
Treecovariant
trait Tree[+A]
case object Void extends Tree[Nothing]
(then Void is a subtype of Tree[A] for any A)
- or you keep
Treeinvariant and then makeVoida class
trait Tree[A]
case class Void[A]() extends Tree[A]
Objects (and values generally) can't be polymorphic in Scala (and JVM).
Making Void extend Tree[Any] is incorrect. Then Void isn't a subtype of Tree[A].
In principle, if you can perform all calculations at compile time, then you can lift your algebraic data type to the type level making Tree a type class
trait Tree[A, T]
case object Void
type Void = Void.type
case class Node[A, L, R](left: L, key: A, right: R)
implicit def voidTree[A]: Tree[A, Void] = new Tree[A, Void] {}
implicit def nodeTree[A, L, R](implicit
leftTree: Tree[A, L],
rightTree: Tree[A, R]
): Tree[A, Node[A, L, R]] = new Tree[A, Node[A, L, R]] {}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论