Wrapping a Monad into a parser - do I need Monad Transformers and how to do it?

Question

I have a monadic type Exp and I want to build a parser that parses into such a value. The following code works, but is there something nicer/cooler I can do?

def grid(x: Int, y: Int): Problem = ???
def expInt: Parser[Exp[Int]] = ???

def grid: Parser[Exp[Problem]] =
  for{
    ex ~ _ ~ ey <- "grid(" ~> expInt ~ "," ~ expInt <~ ")"
  } yield for{
    x <- ex
    y <- ey
  } yield grid(x,y)

I've heard of monad transformers, but still are a bit scared of Scalaz 7's wierd import system. Can someone answer whether

1. I can use monad transformers and
2. How this would look like in principle, using Scalaz 7 for a Scala combinator parser wrapping my own Exp Monad.

Answer 1

First for the easy part—the "weird" import system:

import scalaz._, Scalaz._

That's all. This will always work (barring name collisions, of course, but that's a possibility with any library and is easy to resolve), and nobody's going to look down on you for not using the new à la carte imports, which are mainly about documentation.

The basic pattern for monad transformers is that you have a WhateverT[F[_], ...] type class that has a method named runWhateverT (or just run) that returns an F[Whatever[...]].

In this case it looks like you want to end up with a Parser[Exp], which suggests that you need your own ExpT[F[_]] transformer. I won't start with details about how to implement this (which will depend on the semantics of your monad, of course), but will give an example using Scalaz's OptionT:

import scala.util.parsing.combinator._
import scalaz._, Scalaz._

object MyParser extends RegexParsers {
  implicit val monad = parserMonad(this)

  def oddNumber: OptionT[Parser, Int] = OptionT.optionT(
    "\\d+".r ^^ (_.toInt) ^^ (i => (i % 2 != 0) option i)
  )

  def pairOfOdds: OptionT[Parser, (Int, Int)] = for {
    _ <- literal("(").liftM[OptionT]
    x <- oddNumber
    _ <- literal(",").liftM[OptionT]
    y <- oddNumber
    _ <- literal(")").liftM[OptionT]
  } yield (x, y)

  def apply(s: String) = parse(pairOfOdds.run, s)
}

See my question here for some discussion about why we need the implicit val monad = ... line.

It works like this:

scala> MyParser("(13, 43)")
res0: MyParser.ParseResult[Option[(Int, Int)]] = [1.9] parsed: Some((13,43))

scala> MyParser("(13, 42)")
res1: MyParser.ParseResult[Option[(Int, Int)]] = [1.8] parsed: None

Note that oddNumber.run would give us a Parser[Option[Int]] that will parse a string of digits and return either a Some(i) (if they represent an odd number) or a None (if they're even).

We're not actually going to call oddNumber.run, though, in this case—the fact that we're using a monad transformer means that we can compose oddNumber with lifted Parser actions (the literal(...) here) in a single for comprehension.

The syntax here is ugly—we lose the nice ~ combinators and the implicit conversions from String to Parser[String], for example, but we could easily write lifted versions of those things if we wanted.