Scala Notes - Functional Programming Principles in Scala

Posted on | In , |

This is my personal notes for Functional Programming Principles in Scala at Coursera, which is considered one of the most popular introduction course to Scala.

Basics

Data Structure

Arrays

Arrays preserve order, can contain duplicates, and are mutable.

1
val numbers = Array(1, 2, 3, 4, 5, 1, 2, 3, 4, 5)

Lists

Lists preserve order, can contain duplicates, and are immutable.

1
val numbers = List(1, 2, 3, 4, 5, 1, 2, 3, 4, 5)

Sets

Sets do not preserve order and have no duplicates

1
val numbers = Set(1, 2, 3, 4, 5, 1, 2, 3, 4, 5)

Tuple

A tuple groups together simple logical collections of items without using a class.
Unlike case classes, they don’t have named accessors, instead they have accessors that are named by their position and is 1-based rather than 0-based.

1
2
3
val hostPort = ("localhost", 80)
hostPort._1
hostPort._2

Tuple has some special sauce for simply making Tuples of 2 values: ->

1
2
scala> 1 -> 2
res0: (Int, Int) = (1,2)

Maps

It can hold basic datatypes.

1
Map(1 -> Map("foo" -> "bar"))

Class + Constructor

1
2
3
4
5
6
7
8
9
10
11
12
13
class Calculator(brand: String){
  val color: String = if (brand == "TI"){
    "blue"
  } else if (brand == "HP") {
    "black"
  } else {
    "white"
  }
  def add(m:Int, n:Int): Int = m + note
}
val calc = new Calculator
calc.add(1,2)
calc.brand

Inheritance + Overloading Methods

1
2
3
4
5
6
7
class ScientificCalculator(brand: String) extends Calculator(brand) {
  def log(m: Double, base: Double) = math.log(m) / math.log(base)
}
class EvenMoreScientificCalculator(brand: String) extends ScientificCalculator(brand) {
  def log(m: Int): Double = log(m, math.exp(1))
}

Abstract Classes
Abstract class: a class that defines some methods but does not implement them. Instead, subclasses that extend the abstract class define these methods. You can’t create an instance of an abstract class.

1
2
3
4
5
6
abstract class Shape {
  def getArea():Int    // subclass should define this
}
class Circle(r: Int) extends Shape{
  def getArea(): Int = {r * r * 3}
}

Traits

Traits are collections of fields and behaviors that you can extend or mixin to your classes.

1
2
3
4
5
6
7
8
9
10
11
trait Car {
  val brand: String
}
trait Shiny {
  val shineRefraction: Int
}
class BMW extends Car with Shiny {
  val brand = "BMW"
  val shineRefraction = 12
}
val BMW_X5 = new BMW()

Option

Option is a container that may or may not hold something.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
trait Option[T] {
  def isDefined: Boolean
  def get: T
  def getOrElse(t: T): T
}
def bigger(o: Any): Any = {
  o match {
    case i: Int if i < 0 => i - 1
    case i: Int => i + 1
    case d: Double if d < 0.0 => d - 0.1
    case d: Double => d + 0.1
    case text: String => text + "s"
  }
}

Option itself is generic and has two subclasses: Some[T] or None
Let’s look at an example of how Option is used:
Map.get uses Option for its return type. Option tells you that the method might not return what you’re asking for

Apply Methods

Objects

Objects are used to hold single instances of a class. Often used for factories.

Pattern Matching

1
2
3
4
5
6
val times = 1
times match{
  case 1 => "one"
  case 2 => "two"
  case _ => "other number"
}

Case Classes

1
2
3
4
5
6
7
8
9
10
case class Calculator(brand: String, model: String)
val hp20b = Calculator("HP", "20B")
val hp30b = Calculator("HP", "30B")
def calcType(calc: Calculator) = calc match {
  case Calculator("HP", "20B") => "financial"
  case Calculator("HP", "48G") => "scientific"
  case Calculator("HP", "30B") => "business"
  case Calculator(ourBrand, ourModel) => "Calculator: %s %s is of unknown type".format(ourBrand, ourModel)
}

Exceptions

1
2
3
4
5
6
7
try {
  remoteCalculatorService.add(1, 2)
} catch {
  case e: ServerIsDownException => log.error(e, "the remote calculator service is unavailable. should have kept your trusty HP.")
} finally {
  remoteCalculatorService.close()
}

Collections

Week 1 - Fundaments

substitution model - reduce an expression to a value (lambda calculus)

evaluate the the function from left to right, replace the parameter from right to left.

Lists
Lists preserve order, can contain duplicates, and are immutable.

  • Call-by-value (more efficient)
    • evaluate function argument only once
  • Call-by-name (more easy to terminate)
    • function argument is not evaluated if the corresponding parameter is unused in the evaluation of the function body

abstract expression introduces a name for an expression by which it can be then referred to.

  • linear recursion
  • tail recursion
    to avoid too-deep recursion chain

Week 2

Anonymous function

An anonymous function (x_1:T_1, …, x_n:T_n) => E can always be expressed using def as follows

1
def f(x_1:T_1, ..., x_n:T_n) = E;f

Function types

The type A => B is the type of a function that takes an argument of type A and returns a result of B.
e.g. Int => Int is the type of functions that map integers to integers

Curry

By repeating the process n times

1
2
def f(args_1)...(args_n-1)(arg_n) = E      
def f = (args_1 => (arg_2 => ...(args_n => E) ...))

Week 3

Abstract Classes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
object intsets {
  val t1 = new NonEmpty(3, new Empty, new Empty)
  val t2 = t1 incl 4
}
class Empty extends Intset{
  //subclass of IntSet
  def contains(x: Int): Boolean = False
  def incl(x: Int): Intset = new NonEmpty(x, new Empty, new Empty)
  override def toString = '.'
  def union(other: IntSet): IntSet = other
}
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet{
  // subclass of IntSet
  def contains(x: Int): Boolean =
    if (x<elem) left contains x
    else if (x>elem) right contains x
    else true
  def incl(x: Int): IntSet =
    if (x<elem) new NonEmpty(elem, left incl x, right)
    else if (x>elem) new NonEmpty(elem, left, right incl x)
    else this
  override def toString = "{" + left + elem + right + "}"
  def union(other: IntSet) Intset =
    ((left union right) union other) incl elem
}
abstract class IntSet {
  // super class of Empty and NonEmpty
  def incl(x:Int): Intset
  def contains(x: Int): Boolean
}

Super class to class C (all objects and classes) is base class.

How classes are organized

Class and objects are organized in packages.

Import packages:

  • Name Import import week3.Rational ; import week3.{Rational, Hello}
  • Wildcard Import import week3._

Some entities are automatically imported in any Scala program.

  • All members of package scala
  • All members of package java.lang
  • All members of the singleton object scala.Predef.

e.g.
Int, Boolean, Object, require, assert

Week5

Definition of Merge

1
2
3
4
5
6
7
8
9
10
11
12
def merge(xs: List[Int], ys: List[Int]) = 
 xs match {
  case Nil => ys
  case x::xs1 => 
    ys match {
      case Nil => xs
      case y::ys1 => {
        if (x < y) x :: merge(xs1, ys)
        else y:: merge(xs, ys1)
      }
    }
 }

better use of pattern matching

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
object mergesortGeneral{
  def msort[T](xs: List[T])(lt: (T,T) => Boolean): List[T] = {
    val n = xs.length /2
    if (n == 0) xs
    else {
      def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
        case (Nil, ys) => ys
        case (xs, Nil) => xs
        case (x :: xs1, y::ys1) => {
          if (lt(x,y)) x :: merge(xs1, ys)
          else y :: merge(xs, ys1)
        }
      }
      val (fst, snd) = xs splitAt n
      merge(msort(fst)(lt), msort(snd)(lt))
    }
  }
  val nums = List(2, -4, 5, 7, 1)
  val fruits = List( "apple", "pineapple", "orange", "banana")
  msort(nums)((x, y) => x < y)
  msort(fruits)((x: String, y: String) => x.compareTo(y) < 0)
}

Rules for Implicit Parameters

Say, a function takes an implicit parameter of type T.
The compiler will search an implicit definition that

  • is marked implicit
  • has a type compatible with T
  • is visible at the point of the function call, or is defined with a companion object associated with T

Natural Induction

n -> n + 1

Structure Induction

Some more sequence operations

  • xs exists p: true if there is an element x of xs such that p(x) holds, false otherwise
  • xs forall p: true if p(x) holds for all elements x of xs, false otherwise
  • xs zip ys: a sequence of pairs drawn from corresponding elements of sequences xs and ys
  • xs.unzip: Splits a sequence of pairs xs into two sequences consisting of the first, respectively second halves of all pairs
  • xs.flapMap f: applies collection-valued function f to all elements of xs and concatenates the results
  • xs.sum the sum of all elements of this numeric collection
  • xs.product: the product of all elements of this numeric collection
  • xs.max: the maximum of all elements of this collection (an Ordering must exist)
  • xs.min: the minimum of all elements of this collection

    Reference

    https://twitter.github.io/scala_school/collections.html
    http://blog.tmorris.net/posts/scalaoption-cheat-sheet/