### Functional programming in Scala

The following set of sections represent the exercises contained in the book "Functional Programming in Scala", written by Paul Chiusano and Rúnar Bjarnason and published by Manning. This content library is meant to be used in tandem with the book. We use the same numeration for the exercises for you to follow them.

### Slicing and nonempty repetition

Exercise 9.1

First let's implement `map2` in our `Parser` type:

``````def map2[A, B, C](p: Parser[A], p2: Parser[B])(f: (A, B) => C): Parser[C] =
map(product(p, p2))(f.tupled)``````

With `map2` in our set of combinators, we can implement `many1`:

``````def many1[A](p: Parser[A]): Parser[List[A]] =
map2(p, many(p))(_ :: _)``````
``````val parser = run(
many1(char('a')))(_)

parser(res0) shouldBe Right(List('a'))
parser(res1) shouldBe Right(List('a', 'a', 'a'))``````

Exercise 9.2

Regarding laws that specify the behavior of `product` (`**`), let's start by stating that `product` is associative. These two expressions are "roughly" equal:

``````(a ** b) ** c
a ** (b ** c)``````

The only difference is how the pairs are nested. The `(a ** b) ** c` parser returns an `((A,B), C)`, whereas the `a ** (b ** c)` returns an `(A, (B,C))`. We can define functions `unbiasL` and `unbiasR` to convert these nested tuples to flat 3-tuples:

``````def unbiasL[A, B, C](p: ((A, B), C)): (A, B, C) = (p._1._1, p._1._2, p._2)
def unbiasR[A, B, C](p: (A, (B, C))): (A, B, C) = (p._1, p._2._1, p._2._2)``````

With these, we can now state the associativity property:

``(a ** b) ** c map (unbiasL) == a ** (b ** c) map (unbiasR)``

We'll sometimes just use `~=` when there is an obvious bijection between the two sides:

``(a ** b) ** c ~= a ** (b ** c)``

`map` and `product` also have an interesting relationship--we can `map` either before or after taking the product of two parsers, without affecting the behavior:

``a.map(f) ** b.map(g) == (a ** b) map { case (a, b) => (f(a), g(b)) }``

For instance, if `a` and `b` were both `Parser[String]`, and `f` and `g` both computed the length of a string, it doesn't matter if we map over the result of `a` to compute its length, or whether we do that after the product.

For more discussion of these laws, take a look at chapter 12 of "Functional Programming in Scala".

Exercise 9.3

Let's try to define `many` via `or`, `map2`, and `succeed`:

``````def many[A](p: Parser[A]): Parser[List[A]] =
map2(p, many(p))(_ :: _) or fpinscalalib.customlib.parsing.Reference.succeed(List())

val parser = run(
many(char('a')))(_)

parser("") shouldBe res0
parser("aaa") shouldBe res1``````

Exercise 9.4

Using `map2` and `succeed`, we can also implement `listOfN`:

``````def listOfN[A](n: Int, p: Parser[A]): Parser[List[A]] =
if (n <= res0) fpinscalalib.customlib.parsing.Reference.succeed(List())
else map2(p, listOfN(n - res1, p))(_ :: _)

val singleParser = char('a')
val listParser = listOfN(3, singleParser)
val parseFunction = run(listParser)(_)

parseFunction("aaa") shouldBe Right(List('a', 'a', 'a'))
parseFunction("a").isLeft shouldBe true``````

Exercise 9.5

One way we can deal with non-strictness, is by using a new combinator (`wrap`):

``def wrap[A](p: => Parser[A]): Parser[A]``

We can then define `many` as:

``````def many[A](p: Parser[A]): Parser[List[A]] =
map2(p, wrap(many(p)))(_ :: _) or succeed(List())``````

In the parallelism chapter, we were particularly interested in avoiding having `Par` objects that took as much time and space to build as the corresponding serial computation, and the `delay` combinator let us control this more carefully. Here, this isn't as much of a concern, and having to think carefully each time we `map2` to decide whether we need to call `wrap` seems like unnecessary friction for users of the API.

### Handling context sensitivity

Exercise 9.6

We're now going to try parse a single digit (i.e.: `4`), followed by `that many` `'a'` characters. For instance: `"0"`, `"1a"`, `"2aa"`, and so on. This is also called a context-sensitive grammar. It can't be expressed with `product` because what the second parser decides depends on the first parser's result. Similarly as we did in previous chapters, this problem calls for the use of a new primitive, `flatMap`:

``def flatMap[A, B](p: Parser[A])(f: A => Parser[B]): Parser[B]``

To parse the digits, we'll be using regular expressions. Note the use of the new primitive `regex` which converts any regular expression into a `Parser`. Complete the implementation with a regular expression to catch the digits in our parser's first step, and take a look on how we chain both operations:

``````val parser = for {
digit <- Reference.regex(res0.r)
n = digit.toInt
_ <- listOfN(n, char('a'))
} yield n

val parseFunction = run(parser)(_)
parseFunction("0") shouldBe Right(0)
parseFunction("1a") shouldBe Right(1)
parseFunction("2aa") shouldBe Right(2)``````

Exercise 9.7

We can also implement `product` and `map2` in terms of `flatMap`:

``````def product[A, B](p: Parser[A], p2: => Parser[B]): Parser[(A, B)] =
flatMap(p)(a => map(p2)(b => (a, b)))

def map2[A, B, C](p: Parser[A], p2: => Parser[B])(f: (A, B) => C): Parser[C] =
for { a <- p; b <- p2 } yield f(a, b)``````

Exercise 9.8

The same way as `map` can be implemented via `flatMap`:

``def map[A, B](p: Parser[A])(f: A => B): Parser[B] = p.flatMap(a => succeed(f(a)))``

Exercise 9.9

Let's see an example of how a `Parser[JSON]` could be implemented using the primitives we've defined:

``````trait JSON

object JSON {
case object JNull extends JSON
case class JNumber(get: Double) extends JSON
case class JString(get: String) extends JSON
case class JBool(get: Boolean) extends JSON
case class JArray(get: IndexedSeq[JSON]) extends JSON
case class JObject(get: Map[String, JSON]) extends JSON

def jsonParser[Parser[+_]](P: Parsers[Parser]): Parser[JSON] = {
import P.{ string => _, _ }
implicit def tok(s: String) = P.token(P.string(s))

def array = surround("[", "]")(
value sep "," map (vs => JArray(vs.toIndexedSeq))) scope "array"

def obj = surround("{", "}")(
keyval sep "," map (kvs => JObject(kvs.toMap))) scope "object"

def keyval = escapedQuoted ** (":" *> value)

def lit = scope("literal") {
"null".as(JNull) |
double.map(JNumber(_)) |
escapedQuoted.map(JString(_)) |
"true".as(JBool(true)) |
"false".as(JBool(false))
}

def value: Parser[JSON] = lit | obj | array
root(whitespace *> (obj | array))
}
}``````

### Error reporting

Exercise 9.11

Some useful primitives that could be useful to let programmers specify what error(s) get reported in an `or` chain could be:

``````/** In the event of an error, returns the error that occurred after consuming the most number of characters. */
def furthest[A](p: Parser[A]): Parser[A]

/** In the event of an error, returns the error that occurred most recently. */
def latest[A](p: Parser[A]): Parser[A]``````

### One possible implementation

Explore 9.13

We'll be exploring an actual representation of `Parser`. Let's begin by implementing some of its methods, starting with `string`:

``````def string(w: String): Parser[String] = {
val msg = "'" + w + "'"
s => {
val i = firstNonmatchingIndex(s.loc.input, w, s.loc.offset)
if (i == -1) // they matched
Success(w, w.length)
else
}
}

val parseFunction = run(
string("42"))(_)

parseFunction(res0) shouldBe Right("42")``````

Let's continue by implementing `regex`:

``````def regex(r: Regex): Parser[String] = {
val msg = "regex " + r
s =>
r.findPrefixOf(s.input) match {
case None => Failure(s.loc.toError(msg), false)
case Some(m) => Success(m, m.length)
}
}

val parserFunction = run(
regex(res0.r))(_)

parserFunction("12345") shouldBe Right("12345")
parserFunction("abcde").isLeft shouldBe true``````

Implementation of `succeed` is pretty straightforward:

``def succeed[A](a: A): Parser[A] = s => Success(a, 0)``

Finally let's implement `slice` for our new representation:

``````def slice[A](p: Parser[A]): Parser[String] =
s =>
p(s) match {
case Success(_, n) => Success(s.slice(n), n)
case f @ Failure(_, _) => f
}

val parserFunction = run(
slice(many1(string("a"))))(_)

parserFunction("a") shouldBe Right("a")
parserFunction("ab") shouldBe Right("a")
parserFunction("b").isLeft shouldBe res0``````

Exercise 9.15

It's time to implement the `run` primitive:

``````def run[A](p: Parser[A])(s: String): Either[ParseError, A] = {
val s0 = ParseState(Location(s))
p(s0).extract
}``````

Exercise 9.16

`ParseError` can be improved by better formatting it for human consumption. Let's see how this could work:

``````case class ParseError(stack: List[(Location,String)] = List()) {
def push(loc: Location, msg: String): ParseError =
copy(stack = (loc,msg) :: stack)

def label[A](s: String): ParseError =
ParseError(latestLoc.map((_,s)).toList)

def latest: Option[(Location,String)] = stack.lastOption

def latestLoc: Option[Location] = latest map (_._1)

// Display collapsed error stack - any adjacent stack elements with the same location are combined on one line.
// For the bottommost error, we display the full line, with a caret pointing to the column of the error.
override def toString =
if (stack.isEmpty) "no error message"
else {
val collapsed = collapseStack(stack)
val context =
collapsed.lastOption.map("\n\n" + _._1.currentLine).getOrElse("") +
collapsed.lastOption.map("\n" + _._1.columnCaret).getOrElse("")
collapsed.map { case (loc,msg) => loc.line.toString + "." + loc.col + " " + msg }.mkString("\n") + context
}

// Builds a collapsed version of the given error stack - messages at the same location have their messages
// merged, separated by semicolons.
def collapseStack(s: List[(Location,String)]): List[(Location,String)] =
s.groupBy(_._1).
mapValues(_.map(_._2).mkString("; ")).
toList.sortBy(_._1.offset)

def formatLoc(l: Location): String = l.line + "." + l.col``````

Exercise 9.17

In order to make the `slice` combinator more efficient (i.e.: `many(char('a')).slice` will still create a `List[Char]`, only to discard it) we can create a different representation of the `Parser` type. The main change is to add another piece of state to `ParseState`, an `isSliced` flag, and an additional `Slice` constructor to `Result`. If the `isSliced` flag is set, parsers avoid building a meaningful result. You can take a look at the complete implementation here.

Exercise 9.18

Right now, we're missing error information when we combine several parsers with the `or` combinator. For instance, when both parsers fail we only take into account errors from the second parser. Maybe we could show both error messages, or choose the error from the branch that got furthest without failing. Let's sketch a way of doing that:

``````// We'll just give a sketch here. The basic idea is to add an additional field to `ParseError`
case class ParseError(
stack: List[(Location, String)] = List(),
otherFailures: List[ParseError] = List()) {

this.copy(otherFailures = e :: this.otherFailures)
// ...
}

// We then need to make sure we populate this in the implementation of `or`
def or[A](p: Parser[A], p2: => Parser[A]): Parser[A] =
s => p(s) match {
Of course, we have to decide how to print a `ParseError` for human consumption. We also can expose combinators for selecting which error(s) get reported in the event that a chain of `a | b | c` fails--we might choose to collect up all the errors for each of the three parsers, or perhaps only show the parser that got the furthest in the input before failing, etc.
To wrap this section up, here's a small exercise for you to test the aforementioned `JSON` parser with your own entries. Source code for this parser can be found here or in the source code of this section.
``````val json: Parser[JSON] = JSON.jsonParser(Reference)