ScalaでKnuth-Morris-Pratt

文字列探索のアルゴリズムに KMP (Knuth-Morris-Pratt) 法 [1] というのがあるのだけど、ドラゴンブックとかネット上とかにある命令的に書かれた KMP の実装例のテーブル生成部分が腑に落ちなくて困った。
もうちょっと抽象レベルの高いコード例はないかなと思って探してみたら Haskell 版の KMP [2] を見つけた。Scala に直したらちょっと見通しが良くなったのでここに載せる。

class State[T](xs: List[T], var failure: T => State[T]) {
  val done = (xs == Nil)
  def next(c: T) = if (c == xs.head) success else failure(c)
  lazy val success: State[T] = new State[T](xs.tail, failure(xs.head).next)
}

object KMP {
  def find[T](keyword: List[T], text: List[T]) = {
    def f(state: State[T], text:List[T]): Boolean = text match {
      case Nil => state.done
      case x::xs => state.done || f(state.next(x), xs)
    }
    val start = new State(keyword, null)
    start.failure = (x => start) // tied the knot
    f(start, text)
  }
  def find(keyword: String, text: String): Boolean = find(keyword.toList, text.toList)
}

以前 Scala で Packrat parser [3] を書いたときにも思ったけど Haskell のフィールドラベルを使ったデータ型を Scala でクラスを使って書き直すと分かりやすさが向上すると思う。主に文法上の問題（Haskell のセレクタよりメソッド呼び出しの文法のほうがわかりやすい）だろうけど。

[1] http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%8C%E3%83%BC%E3%82%B9-%E3%83%A2%E3%83%AA%E3%82%B9-%E3%83%97%E3%83%A9%E3%83%83%E3%83%88%E6%B3%95
[2] http://twan.home.fmf.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell.details
[3] http://blog.so-net.ne.jp/rainyday/2007-09-09