「こんなプログラムを書いてみよう」 in Scala

http://d.hatena.ne.jp/nowokay/20080717#1216294670

とりあえず、こんな感じかな(k文字版)。効率は度外視して、サクっと書ける書き方で書いてみた。

object S {
  def strings(list: List[String]): List[String] = {
    def g(prefix: String, list: List[String]): List[String] = {
      list match {
        case Nil => List(prefix)
        case _ =>
          for(s <- list if (s indexOf prefix) == 0; 
              r <- g(s substring 1, list - s)) yield s(0) + r
      }
    }
    g("", list)
  }
}

実行結果。

scala> :load strings.scala
Loading strings.scala...
defined module S

scala> import S._
import S._

scala> strings(List("ABA", "BAB", "ABC", "BCA", "CAB", "CAA", "AAB"))
res0: List[String] = List(CABABCAAB, CABCAABAB, CAABABCAB, CAABCABAB)