scala - 在 Scala 中表示为元组的树

Question

我正在尝试编写一个函数来计算表示为元组的树的节点。

object Main {
     def count[T](tree:Seq[T]):Int= {
        if (lst == ())
            0
        else
            count(tree(1)) + count(tree(2)) + 1
    }
     def main(args: Array[String]) {
        val lst3 = (2,(6,(8,(),()),(5,(),())),(4,(3,(),()),(10,(),())))
        println(count(lst3))
    }
}

我怎样才能在 Scala 中做到这一点？

Answer 1

Dan 的答案在实践意义上是正确的(我刚刚相应地投了赞成票)，但在另一种意义上，您的直觉是完全正确的:您已经选择了在 Scala 中表示二叉树的绝佳方式——如果只是代数数据类型(如丹的回答)甚至更好。

因此，我将非常直白地为您的问题提供一个不切实际但可能很有趣的答案。绝对可以将二叉树表示为嵌套的 3 元组，也可以编写 100% 类型安全的 count将计算此类树中所有节点的函数:

trait Counter[T] { def count: Int }

object Counter {
  implicit object UnitCounter extends Counter[Unit] {
    val count = 0
  }

  implicit def branchCounter[A, L, R](implicit
    lc: Counter[L],
    rc: Counter[R]
  ): Counter[(A, L, R)] = new Counter[(A, L, R)] {
    def count = 1 + lc.count + rc.count
  }
}

def count[T](t: T)(implicit c: Counter[T]) = c.count

这里我们定义了一个类型类 Counter这告诉我们某种类型中有多少节点 T .我们对定义的类型类实例非常有选择性，因此编译器将无法为任何旧的 T 提供实例。 —只是 T s 具有正确的形状。对于 t任何其他类型， count(t)不会编译。

我们可以试试:

val lst3 = (2, (6, (8, (), ()), (5, (), ())), (4, (3, (), ()), (10, (), ())))

进而:

scala> count(lst3)
res0: Int = 7

但:

scala> count("foo")
<console>:11: error: could not find implicit value for parameter c: Counter[String]
              count("foo")
                   ^

请注意，这是编译时的错误——我们没有放弃任何类型安全。

再次:出于任何实际目的，您应该在另一个答案中使用该方法，但您的错误没有您想象的那么大。