Transforming XML to a list of Elements in Scala

Question

This is a follow-up to my previous question. I would like to linearize an XML tree eagerly (not lazy). I assume for simplicity that an XML tree is a tree of Elem nodes, so I am transforming an XML to a sequence of Elem.

import scala.xml.{Elem, Node}
import PartialFunction._

def linearize(node: Node): List[Node] = {
  val children = node.child.filter(cond(_) {case _: Elem => true}).toList
  children match {
    case Nil => List(node)
    case list => node :: list.flatMap(linearize)
  }
}

It seems working but I don't like that val children = ... How would you suggest change/fix it?

score 2 · Accepted Answer · answered Aug 27 '14 at 12:36

2

Since you are already transforming node.child into List, you don't need to match on it, you can flatMap directly, since it will return Nil in case the child is empty. The following code yields the same result as your solution for a simple test case.

import scala.xml.{Elem, Node}
import PartialFunction._

def linearize(node: Node): List[Node] = {

  node :: node.child.flatMap {
    case e: Elem => linearize(e)
    case _ => Nil
  }.toList

}

answered Aug 27 '14 at 12:36

Johnny Everson

8,343
7
39
75

Thanks. What if `node.child` contains non-`Elem` node ? – Michael Aug 27 '14 at 13:34
Well, that is up to you to decide what you want to do with them. I just added the match to `Elem` so it behaves like the function posted on the question. PS. If this answers your question completely, can you please mark this as the answer instead of upvoting? If the answer is incomplete, I can complement it. – Johnny Everson Aug 27 '14 at 13:48

score 1 · Answer 2 · edited May 23 '17 at 11:52

You can traverse the tree in both depth-first and breath-first fashion. I've created functions for these two modes. Both are tail-recursive so you can save some stack frames at the expense of heap.

import scala.xml.{ Elem, Node }

def linearizeDepthFirst(node: Node): List[Node] = {
  @annotation.tailrec
  def loop(toVisit: Vector[Node], result: Vector[Node]): List[Node] = {
    if (toVisit.isEmpty) {
      result.toList
    } else {
      val children = toVisit.head.collect({ case e: Elem => e }).toVector
      loop(children ++ toVisit.tail, result ++ children)
    }
  }

  loop(Vector(node), Vector(node))
}

def linearizeBreadthFirst(node: Node): List[Node] = {
  @annotation.tailrec
  def loop(toVisit: Vector[Node], result: Vector[Node]): List[Node] = {
    if (toVisit.isEmpty) {
      result.toList
    } else {
      val children = toVisit.head.collect({ case e: Elem => e }).toVector
      loop(toVisit.tail ++ children, result ++ children)
    }
  }

  loop(Vector(node), Vector(node))
}

Transforming XML to a list of Elements in Scala

2 Answers2