CODEWITHSUNDEEP
scalaplayframework-2.0
Michał Jurczuk
Michał Jurczuk

Reputation: 3828

Get all child objects in Scala

I have a such model:

case class Product(id:String, nextVersion:Option[Product] = None)

Is it possible to get all versions of product? I can use while:

def getAllVersions(product: Product) = {

  var allVersions = List[Product]()
  var actualProduct = product
  while (actualProduct != null) {
    allVersions :+= actualProduct
    actualProduct = actualProduct.nextVersion.orNull
  }

  allVersions
}

but maybe there is some better way of doing this, more functional?

For example for:

Product("1", Some(Product("2", Some(Product("3", None)))))

I want to get list of three products "1", "2", "3".

Upvotes: 0

Views: 474

Answers (1)

AmigoNico
AmigoNico

Reputation: 6852

I am guessing you mean that you want to get a Seq of the IDs from a Product chain, like so:

scala> case class Product(id:String, nextVersion:Option[Product] = None)
defined class Product

scala> val p = Product("1", Some(Product("2", Some(Product("3", None)))))
p: Product = Product(1,Some(Product(2,Some(Product(3,None)))))

scala> def toList(p:Product): List[String] = p match {
         case Product(id, None)       => List(id)
         case Product(id, Some(next)) => id :: toList(next)
       }
toList: (p: Product)List[String]

scala> toList(p)
res2: List[String] = List(1, 2, 3)

A tail-recursive version would be more efficient and immune to stack overflows:

scala> def toList(p:Product) = {
         @tailrec def loop(p: Product, soFar: List[String]): List[String] =
           p match {
            case Product(id, None)       =>            id :: soFar
            case Product(id, Some(next)) => loop(next, id :: soFar)
           }
         loop(p, Nil).reverse
       }
toList: (p: Product)List[String]

scala> toList(p)
res4: List[String] = List(1, 2, 3)

Although we might be better off doing it with a Vector: fewer objects created, no need to reverse at the end, and much more efficient if the caller wants to access the result non-sequentially. But let's return a Seq so we can change the type later if we want to:

scala> def toList(p:Product): Seq[String] = {
         @tailrec def loop(p: Product, soFar: Vector[String]): Vector[String] =
           p match {
             case Product(id, None)       =>            soFar :+ id
             case Product(id, Some(next)) => loop(next, soFar :+ id)
           }
         loop(p, Vector())
       }
toList: (p: Product)Seq[String]

scala> toList(p)
res5: Seq[String] = Vector(1, 2, 3)

The following version is shorter and not explicitly recursive -- the call back to toList is done from within Option#map. However, this currently means that tail-call optimization will not be done on the recursion (the Scala compiler can't do it, and the JVM currently does not do it), so this could cause a stack overflow if the Product version chain is long enough. And it will be less efficient than the code above.

scala> def toList(p:Product): List[String] =
         p.id :: (p.nextVersion map toList getOrElse Nil)
toList: (p: Product)List[String]

scala> toList(p)
res1: List[String] = List(1, 2, 3)

You could define and use an Iterator[Product], like so:

scala> implicit def productIterator(firstP: Product) = new Iterator[Product] {
         private var optP = Option(firstP)
         def hasNext = optP.isDefined
         def next =
           if (hasNext) {
             val p = optP.get
             optP = p.nextVersion
             p
           } else {
             sys error "read past end of Iterator[Product]"
           }
       }
productIterator: (firstP: Product)Iterator[Product]

scala> (p map (_.id)).toList
res22: List[String] = List(1, 2, 3)

But since your data structure is recursive, the code to traverse it has to either be recursive (explicitly or implicitly) or use mutable variables (as the Iterator does).

Upvotes: 4

Related Questions