gistfile1.scala

class Digraph {
  def postOrder(s: Int) = {
    val visited = Array[Boolean].fill(n(false))
    val ordered = Queue[Int]()
   
    def _postOrder(s: Int) = {
      visited[s] = true
      adj(s).filterNot(visited).forEach(_postOrder(_))
      ordered.enqueue(s)
      }

      _postOrder(s)
      ordered
  }

  def postOrderPure(s: Int) = {
    def _postOrder(s: Int, state: (List[Int], Vector[Boolean])): (List[Int], Vector[Boolean]) = {
      val (ordered, visited) = state
      val newVisited = visited.updated(s, true)
      val reachable = adj(s).filterNot(newVisited).foldLeft((ordered, newVisited)){(acc, v) => _postOrder(v, acc)}
      (s::reachable._1, reachable._2)
    }
    _postOrder(s, (List[Int](), Vector.fill(n)(false)))._1
  }

  def postOrderMonadic(s: Int): (List[Int], Vector[Boolean]) = {
      type S[A] = State[Vector[Boolean], A]

      def _postOrder(s: Int, ordered: List[Int]): S[List[Int]] =
        for {
          visited   <- init[Vector[Boolean]]
          newVisited = visited.updated(s, true)
          toVisit    = adj(s).filterNot(newVisited)
          _         <- put(newVisited)
          reachable <- toVisit.foldLeftM(ordered){(acc, v) => _postOrder(v, acc)}
        }
        yield s::reachable

      val (a, b) = _postOrder(s, List[Int]()).run(Vector.fill(n)(false))
      (b, a)
  }
}