Push-Based(non-blocking) Parser Combinator

Parsers.scala

import scalaz._
import scalaz.iteratee.Iteratee._
import scalaz.iteratee._
import scalaz.iteratee.StepT.{Done, Cont}
import Scalaz._

import scala.util.{Try, Success, Failure}

case class ~[A, B](a: A, b: B)

object Parsers {

  def main(args: Array[String]): Unit = {

    val p0 = (string("AB") | string("BA")) ~ (string("CD") | string("DC")) ~ string("EF")
    val p1 = enum("AB".toList, p0)
    val p2 = enum("DC".toList, p1)

    showResult(enum("EF".toList, p2)) // ==> ~(~(List(A, B),List(D, C)),List(E, F))
  }

  implicit def seqSemigroup[A]: Semigroup[Seq[A]] = new Semigroup[Seq[A]] {
    def append(f1: Seq[A], f2: => Seq[A]): Seq[A] = f1 ++ f2
  }

  implicit def streamMonad: Monad[Stream] = new Monad[Stream] {
    def bind[A, B](fa: Stream[A])(f: (A) => Stream[B]): Stream[B] = fa.flatMap(f)
    def point[A](a: => A): Stream[A] = Stream(a)
  }

  implicit def writerMonad: Monad[LogWriter] = new Monad[LogWriter] {
    def bind[A, B](fa: LogWriter[A])(f: (A) => LogWriter[B]): LogWriter[B] = fa flatMap f
    def point[A](a: => A): LogWriter[A] = Writer(Seq(), a)
  }

  implicit def streamTWriterMonad
  (implicit ev: Semigroup[Seq[Throwable]]): Monad[StreamTWriter] = new Monad[StreamTWriter] {
    def bind[A, B](fa: StreamTWriter[A])(f: (A) => StreamTWriter[B]): StreamTWriter[B] = fa flatMap f
    def point[A](a: => A): StreamTWriter[A] =
    StreamT[LogWriter, A] {
      Writer(Seq(), StreamT.Yield(a, StreamT.empty[LogWriter, A]))
    }
  }

  type LogWriter[a] = Writer[Seq[Throwable], a]

  type StreamTWriter[a] = StreamT[LogWriter, a]

  type Parse[E, O] = IterateeT[E, StreamTWriter, O]

  implicit class ParseOps[E, O1](val lhs: Parse[E, O1]) extends AnyVal {

    def ~>[O2](rhs: Parse[E, O2]): Parse[E, O2] = for {
      a <- lhs
      b <- rhs
    } yield b

    def <~[O2](rhs: Parse[E, O2]): Parse[E, O1] = for {
      a <- lhs
      b <- rhs
    } yield a

    def ~[O2](rhs: Parse[E, O2]): Parse[E, O1~O2] = for {
      a <- lhs
      b <- rhs
    } yield new `~`[O1, O2](a, b)

    def |(rhs: Parse[E, O1]): Parse[E, O1] = disj(lhs, rhs)

  }

  def fail[E, A](): Parse[E, A] = {
    def empty[A]: StreamTWriter[A] = StreamT[LogWriter, A] {
      WriterT.tell(Seq[Throwable]()).map { _ => StreamT.Done }
    }
    IterateeT[E, StreamTWriter, A] { empty }
  }

  def fail[E, A](ex: Throwable): Parse[E, A] =
    IterateeT[E, StreamTWriter, A] { tell(ex) }

  def tell[A](ex: Throwable): StreamTWriter[A] =
    StreamT[LogWriter, A] {
      WriterT.tell(Seq(ex)).map { _ => StreamT.Done }
    }

  def none[E]: Parse[E, Seq[E]] = done(Seq())

  def done[E, A](a: A): Parse[E, A] = Iteratee.done(a, Input.emptyInput)

  def elem[E](e: E): Parse[E, E] =
    Iteratee.head[E, StreamTWriter].flatMap {
      case Some(`e`) => IterateeT.done(e, emptyInput[E])
      case _ =>
        fail(new Exception(s"'$e' expected, but not found."))
    }

  def string[E](e: Seq[E]): Parse[E, Seq[E]] =
    e.foldLeft(none[E]) { (acc, e) => acc.flatMap(l => elem(e).map(l :+ _)) }

  def disj[E, A](a: Parse[E, A] *): Parse[E, A] =
    IterateeT[E, StreamTWriter, A] {
      a.foldLeft(fail[E, A].value) { (acc, e) => acc ++ e.value }
    }

  def showResult[E, A](p: Parse[E, A]): Unit = {
    val w = p.value.toStream
    if (w.value.isEmpty) {
      println("error: "+ w)
    }
    else {
      println("result: "+ w.value.head.doneValue.getOrElse("none"))
    }
  }

  def enum[E, M[_]: Monad, A](l: List[E], it: IterateeT[E, M, A]): IterateeT[E, M, A] = {
    l match {
      case List() => it
      case h::tl  => enum(tl, feed(it, h))
    }
  }

  def feed[E, M[_], A](p: IterateeT[E, M, A], e: E)(implicit M: Monad[M]): IterateeT[E, M, A] =
    IterateeT[E, M, A] {
      p.value.flatMap {
        case Cont(k) => k(Input(e)).value
        case s       => M.point(s)
      }
    }
}