前後の値も利用したシーケンス処理をScalaのパーザコンビネータで解いてみた

シーケンス中で連続して同じ値が入っている各箇所について，2 個目以降は削除したシーケンスが欲しい，という問題．

http://d.hatena.ne.jp/NyaRuRu/20090311/p1

パーザコンビネータというと、とかく、文字列のパーズのためだけのものと思われがちですが、こういう問題にも(一応)使えるんですよ、という例として(NyaRuRuさんの日記で言及されている、boost.xpressiveと似たようなものですね)。

import scala.util.parsing.combinator._
import scala.util.parsing.input._
class ListParsers[T] extends Parsers {
  type Elem = T
  def same(v: T): Parser[T] = elem("", _ == v).* ^^ {_ => v}
  lazy val seq: Parser[List[T]] = elem("", _ != null).flatMap{same(_)}.*
}

一応解説しておくと、sameというのが、引数vを受け取って、「vと同じ値が0個以上続く列」をパーズして、vを解析結果とするParserを返すメソッド。seqがそれを使って、同じ値が2個続く列を削除したリストを解析結果とするParserを返すParser。問題を解くプログラム自体はたったこれだけ。ただ、使う方は多少面倒。というのは、Scalaでは、Parser[T]はReader[T]を受け取って、ParseResult[T]を返す関数のサブクラスとして実装されているのだが、標準ライブラリでは、文字列や文字ストリームをReaderに変換する方法は提供されているものの、任意の型のシーケンスをReaderに変換するための方法は用意されておらず、自前で作ってやる必要がある。たとえば、以下のような、List[T}を受け取ってReader[T]を返すメソッドを定義してやる必要がある。

def reader[T](list: List[T]): Reader[T] = new Reader[T] {
  def atEnd: Boolean = list.isEmpty
  def first: T = if(list.isEmpty) null.asInstanceOf[T] else list.head
  def pos: Position = NoPosition
  def rest: Reader[T] = if(list.isEmpty) this else reader(list.tail)
}
val parser = new ListParsers[Int]
parser.seq(reader(List(1, 2, 3, 3, 4, 4, 5, 6))) match {
  case parser.Success(v, r) => println(v)
  case _ => println("error!")
}

ちなみに、同じ問題を普通にScalaで解くと…

def uniq[T](lst: List[T]) = lst.foldLeft[List[T]](Nil){ 
  case (Nil, b) => List(b) 
  case (a@(h::t), b) => if(h == b) a else b::a 
} reverse

となります。この程度の問題だと、foldLeftなどを使った方が簡単ですね。ただ、パーザコンビネータ版の方が、問題の意図を、より直接的に表現できている、と言えそうな気はします。

追記：
ちょっと冗長だったので、ListParsersクラスのコードをもうちょっと簡潔なものに修正。

追記2：
さらにListParsersクラスのコードを修正(無名関数をリテラルで書く代わりに_を書くようにした)。

追記3:
考えてみれば、この問題なら、foldLeftよりもfoldRightを使って以下のようにした方が若干簡単ですね。

def uniq[T](lst: List[T]) = lst.foldRight[List[T]](Nil){ 
  case (b, Nil) => List(b) 
  case (b, a@(h::t)) => if(h == b) a else b::a 
}