ex: JSON classes
{
"firstName": "John",
"lastName": "Smith",
"address": {
"streetAddress": "21 2nd Street",
"city": "New York",
"state": "NY",
"postalCode": "10021-3100"
},
"phoneNumbers": [
{
"type": "home",
"number": "212 555-1234"
},
{
"type": "office",
"number": "646 555-4567"
}
]
}Representing JSON in Scala using case classes. Memento: case classes are classes that export their constructor parameters and provide a recursive decomposition mechanism via pattern matching. Case classes don't require the new keyword when instantiated.
abstract class JSON
case class JSeq (elems: List[JSON]) extends JSON
case class JObj (bindings: Map[String, JSON]) extends JSON
case class JNum (num: Double) extends JSON
case class JStr (str: String) extends JSON
case class JBool (b: Boolean) extends JSON
case object JNull extends JSONExample of JSON data object:
val data = JObj(Map(
"firstName" -> JStr("John"),
"lastName" -> JStr("Smith"),
"address" -> JObj(Map(
"streetAddress" -> "JStr("21 2nd Street"),
"state" -> JStr("NY"),
"postalCode" -> JNum(10021)
)),
"phoneNumbers" -> JSeq(List(
JObj(Map(
"type" -> JStr("home"),
"number" -> JStr("212 555-1234")
)),
JObj(Map(
"type" -> JStr("office"),
"number" -> JStr("646 555-4567")
))
)Serializing the internal JSON structure:
def show(json: JSON): String = json match {
case JSeq(elems) => "[" + (elems map show mkString ", ") + "]"
case JObj(bindings) =>
val assocs = bindings map {
case (key, value) => "\"" + key + "\": " + show(value)
}
case JNum(num) => num.toString
case JStr(str) => "\"" + str + "\""
case JBool(b) => b.toString
case JNull => null
}Something like:
JBinding => Stringis just shorthand for:
scala.Function1[JBinding, String]where:
trait Function1[-A, +R] {
def apply(x: A): R
}The pattern matching block:
case (key, value) => key + ": " + valueexpands to:
new Function1[JBinding, String] {
def apply(x: JBinding): String = x match {
case(key, value) => key + ": " + value
}
}Because functions are traits we can subclass them:
trait Map[Key, Value] extends (Key => Value) ...
trait Seq[Elem] extends (Int => Elem)Another example:
val f: String => String = { case "ping" => "pong" }
f("ping") returns: "pong"
f("abc") returns: MatchError exceptionIn order to check if the function argument is valid, we can change the declaration as follows:
val f: PartialFunction[String, String] = { case "ping" => "pong" }
f("ping") returns: "pong"
f.isDefinedAt("abc") returns: falseThe PartialFunction trait is defined as follows:
trait PartialFunction[-A, +R] extends Function1[-A, +R] {
def apply(x: A): R
def isDefinedAt(x: A): Boolean
}How are the map, flatMap and filter methods implemented in the List class:
abstract class List[+T] {
def map[U](f: T => U): List[U] = this match {
case x :: xs => f(x) :: xs.map(f)
case Nil => Nil
}
...
def flatMap[U](f: T => List[U]): List[U] = this match {
case x :: xs => f(x) ++ xs.flatMap(f)
case Nil => Nil
}
...
def filter(p: T => Boolean): List[T] = this match {
case x :: xs => if(p(x)) x :: xs.filter(p) else xs.filter(p)
case Nil => Nil
}
}In practice, the implementation is different, because:
for-expressions are syntactically simplified replacements for combinations of: map, flatMap and filter. Instead of:
(1 until n) flatMap (
i => (1 until i) filter (j => isPrime(i + j)) map (j => (i, j)))we can write:
for {
i <- 1 until n
j <- 1 until i
if isPrime(i + j)
} yield (i, j)This is how the Scala compiler translates for-expressions into combinations of map**, flatMap and a lazy-version of filter***:
1) A simple for-expressions
for (x <- e1) yield e2 is translated to:
e1.map(x => e2) 2) A for-expression like:
for (x <- e1 if f; s) yield e2 where f is a filter and s is a potentially empty sequence of generators and filters, is translated to:
for (x <- e1.withFilter(x => f); s) yield e2 3) A for-expression like:
for (x <- e1; y <- e2; s) yield e3 where s is a potentially empty sequence of generators and filters, is translated to:
e1.flatMap(x => for (y <- e2; s) yield e3)The left-hand side of a generator can also be a pattern:
val data: List[JSON] = ...
for {
JObj(binding) <- data
JSeq(phones) = bindings("phoneNumbers")
JObj(phone) <- phones
JStr(digits) = phone("number")
if digits startsWith "212"
} yield (bindings("firstName"), bindings("lastName"))The for notation is equivalent with the common operations of a query language, like SQL or XQuery. Example:
case class Book(title: String, authors: List[String])
val books: List[Book] = List(
Book(title="Structure and Interpretation of Computer Programs",
authors = List("Abelson, Harald", "Sussman, Gerald J")),
Book(title="Introduction to Functional Programming",
authors = List("Bird, Richard", "Wadler, Phil")),
Book(title="Effective Java",
authors = List("Bloch, Joshua")),
Book(title="Java Puzzlers",
authors = List("Bloch, Joshua", "Gafter, Neal")),
Book(title="programming in Scala",
authors = List("Odersky, Martin", "Spoon, Lex", "Venners, Bill"))
)Find the title of the books whose author's name is Bird:
for {
book <- books
author <- book.authors
if author startsWith "Bird,"
} yield book.titleFind the title of the books who have the word "Program" in the title:
for {
book <- books
if book.title indexOf "Program" >= 0
} yield book.titleThe name of the authors who have written at least two books:
{
for {
b1 <- books
b2 <- books
if b1 != b2
a1 <- b1.authors
a2 <- b2.authors
if a1 == a2
} yield a1
}.distinctThe syntax of for is related to three high-order functions: map, flatMap and filter. Each of these functions can be defined by using for:
def mapFun[T, U](xs: List[T], f: T => U): List[U] =
for (x <- xs) yield f(x)
def flatMapFun[T, U](xs: List[T], f: T => Iterable[U]): List[U] =
for (x <- xs; y <- f(x)) yield y
def filterFun[T](xs: List[T], p: T => Boolean): List[T] =
for (x <- xs if p(x)) yield xfor expressions can be applied outside of collections, for any entities for which implementing the map, flatMap and filter functions makes sense. For instance, random generators:
trait Generator[T+] {
def generate: T
}
val integers = Generator[Int] {
val rand = new java.util.Random
def generate = rand.nextInt()
}
val booleans = Generator[Boolean] {
def generate = integers.generate > 0
}
val pairs = new Generator[(Int, Int)] {
def generate = (integers.generate, integers.generate)
}
We can use for trying to avoid the boilerplate:
val booleans = for (x <- integers) yield x > 0
def pairs[T, U](t: Generator[T], u: Generator[U]) = for {
x <- t
y <- u
} yield (x, y)How would map and flatMap be defined for the Generator trait:
trait Generator[T+] {
self => // an alias for this
def generate: T
def map[S](f: T => S): Generator[S] = new Generator[S] {
def generate = f(self.generate)
}
def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
def generate = f(self.generate).generate
}Monads are a class of a data structure + some algebraic laws that they should have (for instance: data structures with map and flatMap).
A monad is a parametric type M[T] with two operations, flatMap and unit, that have to satisfy some laws.
trait M[T] {
def flatMap[U](f: T => M[U]): M[U]
def unit[T](x: T): M[T]
}
flatMap is commonly called bind in the literature.
Examples:
unit(x) = List(x)
unit(x) = Set(x)
unit(x) = Some(x)
unit(x) = single(x)map can be defined for every monad as a combination of flatMap and unit:
m map f == m flatMap (x => unit(f(x)))
== m flatMap (f andThen unit)A monad has to satisfy three laws:
Associativity
m flatMap f flatMap g == m flatMap (x => f(x) flatMap g)Left unit
unit(x) flatMap f == f(x)Right unit
m flatMap unit == mThe monad laws for Option look like this:
abstract class Option[+T] {
def flatMap[U](f: T => Option[U]): Option[U] = this match {
case Some(x) => f(x)
case None => None
}
}
unit(x) is Some(x)Left unit law:
unit(x) flatMap f = f(x)
Some(x) flatMap f
Some(x) match {
case Some(x) => f(x)
case None => None
}
f(x)Right unit law:
opt flatMap Some == opt
opt match {
case Some(x) => Some(x)
case None => None
}
optAssociative law: Left unit law:
opt flatMap f flatMap g == opt flatMap(x => f(x) flatMap g)
opt flatMap f flatMap g
opt match {case Some(x) => f(x) case None => None}
match {case Some(y) => g(y) case None => None}
}
opt match {
case Some(x) => f(x) match {case Some(y) => g(y) case None => None}
case None => None match {case Some(y) => g(y) case None => None}
opt match {
case Some(x) => f(x) match {case Some(y) => g(y) case None => None}
case None => None
opt match {
case Some(x) => f(x) flatMap g
case None => None
opt flatMap (x => f(x) flatMap g)Significance of these laws:
1) associativity law: one can "inline" nested expressions
for (y <- for (x <- m; y <- f(x)) yield y
z <- g(y)) yield z
for (x <- m;
y <- f(x)
z <- g(y)) yield z
2) right unit law:
for (x <- m) yield x
mAnalysis: is Try a monad? Try resembles Option but instead of Some/None it has a Success case with a value or a Failure case with an exception.
abstract class Try[+T]
case class Success[T] (x: T) extends Try[T]
case class Failure(ex: Exception) extends Try[Nothing]You can wrap up a computation in a Try:
Try(expression) // gives Success(someValue) or Failure(someException)Here's an implementation of Try:
object Try {
def apply[T](expr: => T): Try[T] = {
try Success(expr)
catch {
case NonFatal(ex) => Failure(ex)
}
}
}The apply argument is passed by name because we want the computation to be performed inside the method, otherwise the computation would have been performed externally and only the result of the computation would have been passed.
Try-valued computations can be composed in for expressions.
for {
x <- computeX
y <- computeY
} yield f(x, y)If computeX and computeY succeed with results Success(x) and Success(y) then the yielded result will be Success(f(x, y)). If the computation fails, the result will be Failure(ex).
In order to support this, we will have to implement flatMap and map on the Try type:
abstract class Try[T] {
def flatMap[U](f: T => Try[U]): Try[U] = this match {
case Success(x) => try f(x) catch { case NonFatal(ex) => Failure(ex) }
case fail: Failure => fail
}
def map[U](f: T => U): Try[U] = this match {
case Success(x) => Try(f(x))
case fail: Failure => fail
}
}For a **Try** value t*:
t map f
t flatMap( x => Try(f(x)))
t flatMap f andThen TryThe Try type defined like this is not a monad, because the left unit law* fails:
Try(expr) flatMap f != f(expr)The left-hand side never throws a non-fatal exception, while the right-hand side might.