AjitChahal AjitChahal - 11 days ago 6
Scala Question

How to count number of total items where a class references itself

I am new to scala. I need to count Number of categories in the List, and I am trying to build a tail recursive function, without any success.

case class Category(name:String, children: List[Category])

val lists = List(
Category("1",
List(Category("1.1",
List(Category("1.2", Nil))
))
)
,Category("2", Nil),
Category("3",
List(Category("3.1", Nil))
)
)

Answer

Nyavro's solution can be made much faster (by several orders of magnitude) if you use Lists instead of Streams and also append elements at the front. That's because x.children is usually a lot shorter than xs and Scala's List is an immutable singly linked list making prepend operations a lot faster than append operations. Here is an example

import scala.annotation.tailrec

case class Category(name:String, children: List[Category])

@tailrec
def childCount(cats:Stream[Category], acc:Int):Int =
  cats match {
    case Stream.Empty => acc
    case x #:: xs => childCount(xs ++ x.children, acc+1)
  }

@tailrec
def childCount2(cats: List[Category], acc:Int): Int =
  cats match {
    case Nil => acc
    case x :: xs => childCount2(x.children ++ xs, acc + 1)
  }

def generate(depth: Int, children: Int): List[Category] = {
  if(depth == 0) Nil
  else (0 until children).map(i => Category("abc", generate(depth - 1, children))).toList
}

val list = generate(8, 3)

var start = System.nanoTime
var count = childCount(list.toStream, 0)
var end = System.nanoTime
println("count: " + count)
println("time: " + ((end - start)/1e6) + "ms")

start = System.nanoTime
count = childCount2(list, 0)
end = System.nanoTime
println("count: " + count)
println("time: " + ((end - start)/1e6) + "ms")

output:

count: 9840
time: 2226.761485ms
count: 9840
time: 3.90171ms