Parser for the ICFP 2016 competition written in purely functional style

OrigamiParser.scala

import cats.Id
import cats.data.StateT
import spire.math.Rational


/**
  *
  * This exercise should show you how you can combine parsers using `flatMap`.
  * We will parse one of standard ACM assignments...
  *
  * Each [[Problem]] consists of [[Silhouette]] and [[Skeleton]].
  *
  * [[Silhouette]] is a list of polygons.
  * [[Polygon]] is a list of points.
  * [[Point]] are just two <b>fractional</b> or <b>whole</b> numbers x,y.
  *
  * Similarly [[Skeleton]] is just a list of edges.
  * [[Edge]] is a is just a tuple of points.
  *
  * Each list starts with a number of elements it consists followed by the elements themselves.
  *
  * An [[Edge]] is a single line with two [[Point]]s separated by spaces.
  * A [[Point]] is represented as two numbers separated by a comma.
  *
  * The data classes mentioned above are defined at the bottom of the file.
  *
  * Example:
  * {{{
  *     val ex =
  * """2           < silhouette has two polygons
  *   |4           < first polygon has 4 points
  *   |0,0         < first point is Point(0,0)
  *   |1,0         < etc ...
  *   |1/2,1/2
  *   |0,1/2
  *   |4           < second polygon starts here
  *   |0,0
  *   |1,0
  *   |1/2,1/2
  *   |0,1/2
  *   |5           < skeleton has 5 edges
  *   |0,0 1,0     < first edge is Edge(Point(0,0),Point(1,0))
  *   |1,0 1/2,1/2 < etc ...
  *   |1/2,1/2 0,1/2
  *   |0,1/2 0,0
  *   |0,0 1/2,1/2
  * """.stripMargin
  *
  * }}}
  *
  */
object OrigamiParser {

  /**
    * F = Id            - identity
    * S = List[Strings] - not yet parsed tokens
    *
    * @tparam A output value of the parser
    */
  type Parse[A] = StateT[Id, List[String], A]

  object Parse {
    def apply[A](runF: List[String] => (List[String], A)): Parse[A] =
      StateT[Id, List[String], A](runF)
  }

  /**
    * The actual lines does not really matter.
    * Let's split the input text by all whitespaces and commas to get tokens to parse.
    */
  def tokenize(str: String): List[String] = str.split("""(\s|,)""").toList

  /** Reuse the implementation of replicate you implemented in lec4. */
  def replicate[A](n: Int)(parseA: Parse[A]): Parse[List[A]] = {
    import cats.implicits._

    List.fill(n)(parseA).sequence[Parse, A]
  }

  /**
    * EXAMPLE!
    *
    * The state is a list of tokens.
    * Number is obviously represented as a single token.
    * To parse it you just pop the head of the list, turn it to integer.
    * Than you return all the remaining tokens wrapped together with the parsed value.
    *
    * The types in the pattern mathing are specified just for the sa
    */
  lazy val parseNum: Parse[Int] = Parse {
    case head :: tail => (tail, head.toInt)
  }

  /**
    * Parse a rational number.
    * It might be defined as either single number `z` or fraction `x/y`.
    * Handle both cases.
    * <p>
    * Maybe you can use pattern matching with regex: http://stackoverflow.com/a/4636670
    */
  def parseRational(token: String): Rational = Rational(token)

  /** Use the method above. To define a state transition which parses rational numbers */
  lazy val parseRational: Parse[Rational] = Parse {
    case head :: tail => (tail, parseRational(head))
  }

  /** Use `Applicative#map2` to parse a [[Point]] - as in lec4 */
  lazy val parsePoint: Parse[Point] = for {
    x <- parseRational
    y <- parseRational
  } yield Point(x, y)

  /** Use `Applicative#map2` to parse an [[Edge]] - as in lec4 */
  lazy val parseEdge: Parse[Edge] = for {
    s <- parsePoint
    y <- parsePoint
  } yield Edge(s, y)

  /* You will need the `replicate` method to parse the following three cases. */

  def parseWrappedList[I, O](internalParser: Parse[I])(wrapper: List[I] => O): Parse[O] = for {
    n <- parseNum
    points <- replicate(n)(internalParser)
  } yield wrapper(points)

  lazy val parsePolygon: Parse[Polygon] = parseWrappedList(parsePoint)(Polygon)

  lazy val parseSilhouette: Parse[Silhouette] = parseWrappedList(parsePolygon)(Silhouette)

  lazy val parseSkeleton: Parse[Skeleton] = parseWrappedList(parseEdge)(Skeleton)

  /**
    * Try to use for comprehention instead of `flatMap`s to compose the result
    */
  lazy val parseProblem: Parse[Problem] = for {
    silhouette <- parseSilhouette
    skeleton <- parseSkeleton
  } yield Problem(silhouette, skeleton)

}

object OrigamiParseExample extends App {

  import OrigamiParser._

  val input =
    """2
      |4
      |0,0
      |1,0
      |1/2,1/2
      |0,1/2
      |4
      |0,0
      |1,0
      |1/2,1/2
      |0,1/2
      |5
      |0,0 1,0
      |1,0 1/2,1/2
      |1/2,1/2 0,1/2
      |0,1/2 0,0
      |0,0 1/2,1/2
    """.stripMargin


  val problem = parseProblem.runA(input.split(Array('\n', ',', ' ')).toList)
  println(problem)

}

case class Point(x: Rational, y: Rational)

case class Edge(s: Point, t: Point)

case class Polygon(points: List[Point])

case class Silhouette(polygons: List[Polygon])

case class Skeleton(segments: List[Edge])

case class Problem(silhouette: Silhouette, skeleton: Skeleton)