Scala中的类型安全完美二叉树

问题描述：

我想在Scala中实现类型安全perfect binary tree。换句话说以下应编译：Scala中的类型安全完美二叉树

Succ(Node(Leaf("a"), Leaf("b"))) 
Node(
    Succ(Node(Leaf("a"), Leaf("b"))), 
    Succ(Node(Leaf("c"), Leaf("d"))))

但以下不宜：

Node(
    Succ(Node(Leaf("a"), Leaf("b"))), 
    Leaf("c"))

我想出了下面满足上述但一个可以欺骗编译器的解决方案：

Node(
    Leaf("f"): PerfectBinaryTree, 
    Succ(Node(Leaf("a"), Leaf("b"))): PerfectBinaryTree)

有没有办法在Scala中避免这种情况？与Haskell（如果有的话）有什么不同？

trait PerfectBinaryTree { 
    type N <: PerfectBinaryTree 
    } 

    case class Succ[P <: PerfectBinaryTree](p: P) extends PerfectBinaryTree { 
    type N = Succ[P] 
    } 

    class Leaf[T] private (t: T) extends PerfectBinaryTree { 
    type N = Leaf[T] 
    } 

    object Leaf { 
    def apply[T](t: T): Leaf[T] = new Leaf(t) 
    } 

    case class Node[A <: PerfectBinaryTree, B <: PerfectBinaryTree](l: A, r: B)(implicit evidence: A =:= B) extends PerfectBinaryTree { 
    type N = A 
    }

您在问题中有两个问题。我建议你在这个问题中删除对Haskell的任何引用，并最终要求在Haskell中实现这个相关问题。 – Bakuriu

在Haskell中，这将是'data PerfectBinaryTree a = Zero a | Succ（PerfectBinaryTree（BinaryNode a））'和'数据BinaryNode a =节点a a'。你似乎已经搞乱了你的Scala代码中的这个结构。 “叶”应该是“零”吗？为什么他们都是同一班的情况？ – Bergi

很可能@Bergi，我搞砸了。是啊'叶=零'。如何安排回去？ ;）我会考虑这个@Bakuriu – mjaskowski

答

诀窍（就像在Haskell）是传递Node类型变量（polymorphic recursion）的内部。

类的定义，然后变得非常简单

case class Node[+A](left: A, right: A); 

sealed trait Tree[+A]; 
case class Succ[+A](subtree: Tree[Node[A]]) extends Tree[A]; 
case class Leaf[+A](value: A) extends Tree[A];

（当然你要新增功能折叠/遍历这种树等）

然后，创造价值的时候，构造函数的数量决定需要多少个Node。请注意，总是只有一片叶子，但它包含由给定数量的Node级别组成的二叉树：

val sample: Tree[String] = 
Succ(
    Succ(
    Leaf(
     Node(
     Node("a", "b"), 
     Node("c", "d") 
    ) 
    ) 
) 
);

哇！那里有没有这种知识的很好的来源？ – mjaskowski

@mjaskowski有关该主题的研究论文。例如，请参阅如何实施[Java中的类型安全红黑树]（http://www.cs.kent.ac.uk/people/staff/smk/redblack/rbj.pdf）。您可能还想要搜索Ralf Hinze关于“构建红黑树”主题的前一篇论文。 – chi

@mjaskowski我也建议阅读着名的冈崎的着作_Purely Functional Data Structures_（原始论文可在线获取）。特别是有一章“结构分解”谈到了这一点。一般来说，多态递归是一个很好的技巧，值得探索。另一个好的指针是研究自然数的表示和数据结构之间的对应关系，也在同一本书中。在这种情况下，我们将代表两个幂。 –

Scala中的类型安全完美二叉树

相关推荐