Breadth-First Traversal of a Rose Tree

rose-bft-test.scala

package rose

import org.scalacheck._
import scalaz._
import Scalaz._
import scalaz.scalacheck.ScalazArbitrary._

import rose.Rose._

object RoseTest extends Properties("RoseTest") {
  import Prop.forAll
  import EphemeralStream._

  property("bft") = forAll { (h: Int, l1: IList[Int], l2: IList[Int]) =>
    val rr: IList[RoseTree[Int]] = l1.zipL(l2).map {
      case (a1, a2) =>
        RoseTree(
          a1,
          fromStream(
            a2 match {
              case None => Stream.empty
              case Some(a) =>
                RoseTree(a, emptyEphemeralStream[RoseTree[Int]]) #:: Stream.empty
            }
          )
        )
    }
    val tr = RoseTree(h, rr.toEphemeralStream)

    breadthFirst(tr).toList ==
      (EphemeralStream(h) ++
        l1.toEphemeralStream ++
        l2.take(l1.length).toEphemeralStream).toList
  }
}

rose-bft.scala

package rose

import scalaz._
import Scalaz._

import EphemeralStream._
import Dequeue._
import Maybe._

// Following the algo in https://www.cs.tufts.edu/~nr/cs257/archive/chris-okasaki/breadth-first.pdf

object Rose {
  final case class RoseTree[A] ( root: A, forest: EphemeralStream[RoseTree[A]])
  // type Forest[A] = EphemeralStream[RoseTree[A]]

  def breadthFirst[A] : RoseTree[A] => EphemeralStream[A] = 
    ts => {
      def go : Dequeue[RoseTree[A]] => EphemeralStream[A] = 
        dts => dts.uncons match {
          case Empty() => emptyEphemeralStream
          case Just((RoseTree(a, xs), ys)) =>  
                      cons(a, go(ys ++ fromFoldable(xs)))
        }

      go(singleton(ts))
    }

  def singleton[A] : RoseTree[A] => Dequeue[RoseTree[A]] =
    a => Dequeue(a)
}