OptionT and State stack used to traverse an xml tree keeping history of where it went wrong.

gistfile1.scala

import scalaz._
import std.option._
import syntax.monad._
import scala.xml.Node

object S {

  // We stack OptionT on top of state to keep track of our state regardless
  // of whether we find what we are looking for or not.
  // Using OptionT has the awesome property that the monad will stop traversing
  // once we can't find what we were looking for.
  type FinderState[+A] = State[List[String],A]
  type Finder[+A] = OptionT[FinderState,A]

  // Push a traversal onto the history that we are collecting.
  def logTraversal( nodeName: String ):Finder[Unit] = {
    OptionT.optionT[FinderState](State[List[String],Option[Unit]](
      s => (nodeName::s,Some(())) )
    )
  }

  // Traverse the xml, pushing the history on regardless of whether we find what
  // we are looking for or not.
  def traverse( nodeName:String )( node: Node ):Finder[Node] = {
    val newNode = (node \ nodeName).headOption
    logTraversal( nodeName ).flatMap( _ => OptionT(newNode.point[FinderState]) )
  }

  def main( args:Array[String] ) = {
    val xml = <a><b><c>Find me</c></b></a>
    val win = List("b","c").foldLeft[Finder[Node]]( xml.point[Finder] )(
      (finder,name) => finder.flatMap( traverse(name) )
    )
    val fail = List("c","d","e").foldLeft[Finder[Node]]( xml.point[Finder] )(
      (finder,name) => finder.flatMap( traverse(name) )
    )
    println( win.run( Nil ) )  // (List(List(c, b),Some(<c>Find me</c>))
    println( fail.run( Nil ) ) // (List(c),None)
    println( "DONE" )
  }

}