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

Question

我正在尝试实现类型安全 perfect binary tree在斯卡拉。换句话说，应该编译以下内容:

 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
  }

Answer 1

技巧(就像在 Haskell 中一样)是在类型变量 ( polymorphic recursion ) 内传递 Node 。

类的定义就变得非常简单

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];

(当然你想添加折叠/遍历这样一棵树等的功能。)

然后，在创建值时，Succ 构造函数的数量决定了叶子需要多少个 Node。请注意，始终只有一个叶子，但它包含一个由给定数量的 Node 级别组成的二叉树:

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