トポロジカルソート

前方参照できる型推論をするには依存関係を調べて順番に並べる必要があります。
どう調べたら良いのかと調べてたらトポロジカルソートをするのが基本みたいでした。

https://gist.github.com/ThiporKong/4399695

tsort.scalaで検索したら凄く短いけど、分からないので普段使わない関数は書き換えていつも使っている関数に書き直してみました。
それでもうまく説明が出来ないので、検索してみると以下のページが分かりやすかったです。

http://ameblo.jp/mingw/entry-10389158344.html

参照されていない物から取り除いて無くなるまで繰り返し、参照されていない物がないのに、まだ、残っていれば循環参照があるのでエラーにすればよいのです。

もしくは、逆に参照していない物から取り除けばよいのです。githubにあったソースは参照していない物から取り除く物でした。

以下ソースです。
余計なprintlnも書いてありますが、動きを把握するのに入れたので邪魔であれば消すと良いかと思います。

package tsort

object main extends App {

  // 参照してない物から取り除く
  def tsort[A](toPreds: Map[A, Set[A]], done: List[A]): Iterable[A] = {
    println("tsort "+toPreds+" done "+done)

    // 参照していないものと参照しているものを分ける
    val (noPreds, hasPreds) = toPreds.foldLeft((Map[A,Set[A]](),Map[A,Set[A]]())) {
      case ((no,has),(a1,a2)) =>
        if(a2.isEmpty) (no+(a1->a2),has) else (no,has+(a1->a2))
    }

    println("no  = "+noPreds)
    println("has = "+hasPreds)

    // 参照していない集合が空
    if (noPreds.isEmpty) {
      // 参照している集合も空なら終わり
      if (hasPreds.isEmpty) done
      // 参照をもっている物があれば循環参照があるのでエラー
      else sys.error(hasPreds.toString)
    } else {
      // 参照していない物を取り出す
      val found = noPreds.map { case (a1, a2) => a1 }
      println("found=" + found)
      // 参照している集合から、参照していない名前を取り除く
      val nextPreds = hasPreds.map{ case (p, a) => (p, a -- found) }
      // 再帰呼び出しする
      tsort(nextPreds, done ++ found)
    }
  }

  // 参照されてない人から取り除く
  def tsort2(src:Map[String,Set[String]], done: List[String]):List[String] = {
    // 参照されていないひとを探す

    // 参照されている人の集合を作る
    val finds = src.foldLeft(Set[String]()){
      case (s,(a1,a2)) => s ++ a2
    }
    println("finds="+finds)
    // 参照されてない人と、参照されている人を分ける
    val (no,has) = src.foldLeft(List[String](), Map[String,Set[String]]()) {
      case ((no,has),(a1,a2)) => if (finds.contains(a1)) (no,has+(a1->a2)) else (a1::no,has)
    }
    println("no ="+no)
    println("has="+has)
    // 参照されていない人がいない
    if(no.isEmpty) {
      // 参照されている人もいない
      if(has.isEmpty) {
        return done
      } else {
        throw new Exception("error "+has)
      }
    }
    // 参照されていない人がいる
    tsort2(has,no:::done)
  }

  val graph = Map(
   "ast" -> Set[String](),
   "ast1" -> Set[String](),
   "main" -> Set("parse", "type"),
   "parse" -> Set("ast", "type"),
   "type" -> Set("ast"))
  println(tsort(graph, List()))

  println(tsort2(graph,List()))
}