読者です 読者をやめる 読者になる 読者になる

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

前後の値も利用したシーケンス処理を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 
}