Parser combinators implemented in tagless-final style

Parsers.scala

import scala.language.higherKinds
import scalaz._
import scalaz.std.option._
import scalaz.syntax.monadPlus._

trait Parsers [Elem, C[+_], Repr[+_, _, _[_]]] {
  def cond (f: Elem => Boolean): Repr[Elem, Elem, C]
  def elem (e: Elem): Repr[Elem, Elem, C] = cond(_ == e)
  def success [T] (r: T): Repr[T, Elem, C]
  def failure (msg: String): Repr[Nothing, Elem, C]
}

trait ApplicativeParsers [Elem, C[+_], Repr[+_, _, _[_]]] extends Parsers[Elem, C, Repr] {
  def seq [T, U] (left: Repr[T, Elem, C], right: Repr[U, Elem, C]): Repr[(T, U), Elem, C]
  def alt [T] (left: Repr[T, Elem, C], right: Repr[T, Elem, C]): Repr[T, Elem, C]
  def map [T, U] (parser: Repr[T, Elem, C], f: T => U): Repr[U, Elem, C]
}

object ParserSyntax {
  implicit class ApplicativeParsersUtil [T, Elem, C[+_], Repr[+_, _, _[_]]] (parser: Repr[T, Elem, C])(implicit applicativeParsers: ApplicativeParsers[Elem, C, Repr]) {
    def ~ [U] (right: Repr[U, Elem, C]): Repr[(T, U), Elem, C] = applicativeParsers.seq(parser, right)
    def | [U <: T] (right: Repr[U, Elem, C]): Repr[T, Elem, C] = applicativeParsers.alt(parser, right)
    def ^^ [U] (f: T => U): Repr[U, Elem, C] = applicativeParsers.map(parser, f)

    def ~> [U] (right: Repr[U, Elem, C]): Repr[U, Elem, C] = parser ~ right ^^ (_._2)
    def <~ (right: Repr[Nothing, Elem, C]): Repr[T, Elem, C] = parser ~ right ^^ (_._1)
    def ^^^ [U] (f: => U): Repr[U, Elem, C] = ^^ { _ => f }
  }
}

trait Scanable [R, Elem] {
  def scan (c: R): Option[(Elem, R)]
}

object Scanable {
  implicit def string: Scanable[String, Char] = new Scanable[String, Char] {
    override def scan(c: String): Option[(Char, String)] = {
      if (c.isEmpty) None
      else Some(c.head -> c.tail)
    }
  }
}

trait Reader [Elem] {
  def scan: Option[(Elem, Reader[Elem])]
  def head: Option[Elem] = scan.map(_._1)
  def tail: Option[Reader[Elem]] = scan.map(_._2)
}

object Reader {
  def apply [R, Elem] (c: R)(implicit scanable: Scanable[R, Elem]): Reader[Elem] = new Reader[Elem] {
    override def scan: Option[(Elem, Reader[Elem])] = scanable.scan(c).map { case (e, r) => e -> apply(r) }
  }
  implicit def readerScanable [Elem]: Scanable[Reader[Elem], Elem] = new Scanable[Reader[Elem], Elem] {
    def scan (c: Reader[Elem]): Option[(Elem, Reader[Elem])] = c.scan
  }
}

object :#: {
  def unapply [R, Elem] (reader: R)(implicit scanable: Scanable[R, Elem]): Option[(Elem, R)] = {
    scanable.scan(reader)
  }
}

case class Parser [+T, Elem, C[+_]] (run: Reader[Elem] => C[(T, Reader[Elem])]) {
  def parse [R] (r: R)(implicit monadPlus: MonadPlus[C], scanable: Scanable[R, Elem]): C[T] = run(Reader[R, Elem](r)).map(_._1)
}

object BasicParsers {
  implicit def applicative[Elem, C[+_]] (implicit monadPlus: MonadPlus[C]): ApplicativeParsers[Elem, C, Parser] = new ApplicativeParsers[Elem, C, Parser] {
    import monadPlus.monadPlusSyntax._

    def cond (f: (Elem) => Boolean): Parser[Elem, Elem, C] = Parser {
      case h :#: t if f(h) => pure(h -> t)
      case _ => monadPlus.empty
    }
    def success[T](r: T): Parser[T, Elem, C] = Parser { s => pure(r -> s)}
    def failure(msg: String): Parser[Nothing, Elem, C] = Parser { s => monadPlus.empty }

    def seq[T, U](left: Parser[T, Elem, C], right: Parser[U, Elem, C]): Parser[(T, U), Elem, C] = Parser { s0 =>
      for {
        (t, s1) <- left.run(s0)
        (u, s2) <- right.run(s1)
      } yield (t, u) -> s2
    }
    def alt[T](left: Parser[T, Elem, C], right: Parser[T, Elem, C]): Parser[T, Elem, C] = Parser { s =>
      left.run(s) <+> right.run(s)
    }
    def map[T, U](parser: Parser[T, Elem, C], f: (T) => U): Parser[U, Elem, C] = Parser { s =>
      parser.run(s).map { case (t, r) => f(t) -> r }
    }
  }
}

class Syntax [C[+_], Repr[+_, _, _[_]]] (implicit app: ApplicativeParsers[Char, C, Repr]) {
  import app._
  import ParserSyntax._

  lazy val parser = abc | de
  lazy val abc = elem('a') ~ elem('b') ~ elem('c') ^^ { case ((a, b), c) => "" + a + b + c }
  lazy val de = elem('d') ~ elem('e') ^^ { case (d, e) => "" + d + e }
}

object Main {
  def main (args: Array[String]): Unit = {
    println(new Syntax()(BasicParsers.applicative[Char, Option]).parser.parse("de"))
  }
}