tree represented as a tuple in scala

Question

I am trying to write a function that counts the nodes of a tree represented as a tuple.

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

How can I accomplish this in scala?

Answer 1

Dan's answer is in a practical sense the correct one (and I've just upvoted accordingly), but in another sense your intuitions were exactly right: you've picked what would be an excellent way to represent a binary tree in Scala—if only an algebraic data type (as in Dan's answer) weren't even better.

So I'm going to be very literal and give your question an answer that isn't practical but may be interesting. It's definitely possible to represent a binary tree as nested 3-tuples, and it's also possible to write a 100% type-safe count function that will count all the nodes in such a tree:

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

Here we've defined a type class Counter that tells us how many nodes are in some type T. We've been very selective about what type class instances we've defined, so the compiler won't be able to come up with instances for any old T—just Ts that have the right shape. For a t of any other type, count(t) won't compile.

We can try it out:

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

And then:

scala> count(lst3)
res0: Int = 7

But:

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

Note that this is an error at compile-time—we haven't given up any type safety.

Again: for any practical purposes you should use the approach in the other answer, but you were less wrong than you may have thought.

Answer 2

That is not the right way to use tuples. Scala is a statically-typed language, so tuples should not be used a generic containers for arbitrary objects.

Trees should be represented with classes like:

trait Tree { def value: Int }
case class Branch(value: Int, children: Seq[Tree]) extends Tree
case class Leaf(value: Int) extends Tree

Then you can do:

def count(t: Tree): Int = t match {
  case Branch(v, children) => 1 + children.map(count).sum
  case Leaf(v) => 1
}

So:

val x = Branch(7, Seq(Branch(8, Seq(Leaf(1), Leaf(2))), Leaf(3)))
count(x)  // 5