Functional Programming (FP) Scala, https://www.coursera.org/learn/progfun1/

1week.md

Week 1 (Functions & Evaluation)

Paradigms:

• imperative programming
• functional programming
• logical

no place for mutation in high-level concepts

FP:

• does not have mutable variables, assignments of imperative control structs
• funcs can be values – 1st class citizien

Books:

1. Structure and Interpretation of Computer Programs, 1996
2. Programming in Scala
3. Scala for Impatient
4. Scala (O'Relly)
5. Scala in Depth

Why FP?

• "Working Hard to Keep it Simple" (video, oscon, 2011)

Abstraction – introduce a name for expression

Definitions can have parameters

def pi = 3.14
def power(x: Double, y: Double): Double = ...

Substitution model – reduce an expression to a value. Formalised in the lambda-calculus.

def loop: Int = loop

loop → loop → loop

Call-by-name vs Call-by-name

• CBN – called once
• CBV – called every time

Scala normally uses CBN parameter started with => uses CBN

def constOne(x: Int, y: => Int) = 1

Conditional Expressions (1.4)

if-else is an expression (not a statement like in Java)

def abs(x: Int) = if (x >= 0) x else -x

"short-circuit evaluation" e.g. true && e –> e, false && e —> false

Value Definitions

CBV

val x = 2

def x = loop — OK val x = loop — Error

Write a function:

1. and(x, y) == x && y

def and(x: Boolean, y: =>Boolean): Boolean = if (x) y else false

2. or(x, y) == x || y

def or(x: Boolean, y: =>Boolean): Boolean = if (x) true else y

Scopes (1.6)

Blocks {} are expressions, e.g.

val result = { 
  val b = 1
  x * x
} + x

Semicolons

val y = x + 1; y * y

Tail Recursion (1.7)

def f(x1, .., xN) = B; ... f(v1, .., vN) → def f(x1, .., xN) = B; ... [v1/x1, .., vN/xN] B

[v1/x1, .., vN/xN] B – substitution – means:

the expression B in which all occurrences of xi have been replaced by vi.

def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1) —** not a tail call example**

Tail Recursion – a function which calls itself as a last action. The stack call can be reused.

@tailrec – require function to be a tail-recursive

Exercise: Design a tail recursive version of factorial.

2week.md

Week 2 (Higher Order Functions)

Function type

The type A ⇒ B is function type

• Int ⇒ Int – function which takes int and returns int

Anonymous Functions

(x: Int) ⇒ x * x * x

• (x: Int) – parameter of the function (the type might be omitted)
• x * x * x – body

(x: Int, y: Int) => x + y

(x: T1, ... xN: TN) ⇒ E → def f(x: T1, ... xN: TN) = E; f

def sum(f: Int ⇒ Int, a: Int, b: Int): Int = { ... }

def sumInts(a: Int, b: Int) = sum(x ⇒ x, a, b)
def sumCubes(a: Int, b: Int) = sum(x ⇒ x*x*x, a, b)

A tail recursive version of sum:

def sum(f: Int => Int)(a: Int, b: Int): Int = {
  def loop(a: Int, acc: Int): Int = {
    if (a > b) acc
    else loop(a + 1, f(a) + acc)
  }
  loop(a, 0)
}

Currying (2.2)

def sum(f: Int ⇒ Int): (Int, Int) ⇒ Int = {
  def f(a: Int, b: Int): Int { ... }
  f
}

def sum(f: Int ⇒ Int)(a: Int, b: Int): Int =
  if (a > b) 0 else f(a) + sum(f)(a + 1, b)

def f (arg1)...(argsN) = E

def f(arg1)...(argsN-1) = { def g(argsN) = E; g }
def f(arg1)...(argsN-1) = (argsN) => E

def f = (args1 ⇒ (args2 ⇒ ...(argsN ⇒ E)...))

Finding a fixed point of a function

f(x) = f

sqrt(x) = y, if y * y = x or y = x / y

Stabilising by averaging

averageDamp(f: Double ⇒ Double)(x: Double) = (x + f(x)) / 2

Scala Syntax Summary (2.4)

Function definition = def sqrt() {} Value definition = val y = 1

Functions and Data (2.5)

Classes

class Rational(x: Int, y: Int) {
  def numer = x
  def denom = y
}

• A new type
• A constructor Rational to create elements of the type

Names of types and values are kept in different namespaces.

Objects

An element of a type.

new Rational(1, 2)

Members of Object

val x = new Rations(1,2)
x.numer

Methods

Implementing Rational Arithmetic

Data Abstraction

Self Reference

this references the current object

Preconditions

require(cond: Bool, message: String)

assert(cond: Bool, message: String) throws AssertionError

Constructors

def this(x: Int) = this(x, 1) – second constructor

new Rational(2) == new Rational(2, 1)

Object Substitution (2.7)

new Rational(1, 2).numer → [1/x, 2/y] [] [new Rational(1, 2)/this] x = 1

Operators

we write x + y if x and y are integers

(step 1) Infix operators

r add s → r.add(s)

(step 2) Relaxed Identifiers

Operators can used as identifiers (in scala):

• x1 * +?& vector_++ conunter_=

class Rational(x: Int, y: Int) {
  def < (that: Rational) = ...

  def max(that: Rational) = ...

  def + (that: Rational) = new Rational(...)

  def unary_-  = ...
}

val a = new Rational(1, 2)
val b = new Rational(1, 2)

a < b
a max b
a + b
a + -b

3week.md

Week 3 (Data and Abstraction)

Class Abstraction (3.1)

abstract class IntSet {
  def contains(x: Int): Boolean
}

Class Extensions → Implementation and Overriding

Implementing sets as binary tree

class Empty extends InSet {
  def contains(x: Int): Boolean = false
  def incl(x: Int): InSet = new NonEmpty(x, new Empty, new Empty)

  override def toString = "..."
}

persistent data structures

Object definition

— creates a singletone

object Empty extends InSet {
  def contains(x: Int): Boolean = false
  ...
}

dynamic method dispatch

Example

Empty contains 1 → [1/x] [Empty/this] false

Organise Classes (3.2)

Classes and objects organised in packages.

package progfun.examples

object Hello { ... }

› scala progfun.examples.Hello

import week3.Rational
import week3.{Rational, Hello}
import weel3._ // import everything

Automatic Imports

[scala-lana.org/api/current] – "Predef"

Int, Boolean, Object, require, assert

Traits

A class can only one superclass (single inheritance).

trait Planar {
  def height: Int
  def width: Int
  def surface = height * width
}

Classes can inherit from many traits.

class Square extends Shape with Planar with Movable ...

• Traits resemble interfaces in Java, but can contains fields and implemented methods.
• Traits can't have parameters.

Scala's Class Hierarchy

scala.Any ← { scala.AnyVal, scala.AnyRef }

• AnyRef – alias of java.lang.Object.
• AnyVal – the base of primitives types.

scala.Nothing

There is no value of type Nothing.

Set[Nothing] – element of empty collection

Exceptions

throw new Error(msg)

scala.Null

The type of null is Null. Null is the subtype of every class the inherits from Object.

val x = null
val y: String = x

val z: Int = null // type missmatch

if (true) 1 else false // ← AnyVal

Polymorphism (3.3)

Type parameters variation.

Cons-List – immutable linked list, consists of 2 building blocks:

• Nill – an empty list
• Cons – a cell contains the rest of the list

List(1,2,3), List(List(true, false), List(3))

class Const(val head: Int, val tail: List) {}

vs

class Const(_head: Int, _tail: List) { val head = _head val tail = _tail }

Generalise the type

traits List[T] { .. }
class Cons[T](val head: T, val tail: List[T]) extends List[T] { .. }
class Nil[T] extends List[T] { .. }

Generic Functions

def singleton[T](elem: T) = new Cons[T](elem, new Nil[T])

singleton[Int](1) // or singleton(1) 
singleton[Boolean](true)

Scala compiler can deduce the correct type.

Type parameters do not affect evaluation in Scala – type erasure.

Forms of polymorphism:

• sybtyping
• generics

4week.md

Week 4 (Types and Pattern Matching)

Objects (4.1)

Standard Classes

For reasons of efficiency the Scala compiler represents the values of type scala as 32-bit [..]

Pure Boolean

The Boolean type maps to the JVM's primitive type boolean

abstract class Boolean {
  def ifThenElse[T](t: ⇒ T, e: ⇒ T): T

  def && (x: => Boolean): Boolean = ifThenElse(x, false)
  def || (x: => Boolean): Boolean = ifThenElse(true, x)
  def unary_!: Boolean = ifThenElse(false, true)

  def <(x: => Boolean): Boolean = ifThenElse(False, x)

  ...
}

Boolean Constants

object true extends Boolean {
  def isThenElse[T](t ⇒ T, e: ⇒ T) = t
}

object false extends Boolean {
  def isThenElse[T](t ⇒ T, e: ⇒ T) = e
}

The Class Int

Class overloading

class Int {
  def + (that: Double): Double
  def + (that: Float): Float
  def + (that: Long): Long

  ...
}

Peano numbers

Provide an implementation of the class Nat that represents non-negative integers.

abstract class Nat {
  def isZero: Boolean
  def predecessor: Nat
  def successor: Nat
}

Do not use standard classes in the implementation

object Zero extends Nat {}

class Succ(n: Nat) extends Nat {}

Functions as Object (4.2)

Can we implement functions as Objects? — Function values are treated as objects in Scala.

The A ⇒ B is an abbreviation for the class scala.Function1[A, B]

trait Function1[A, B] {
  def apply(x: A): B
}

Anonymous class syntax

val f = new Function1[Int, Int] {
  def apply(x: Int) = x * x
}
f.apply(7)

Functions and Methods

Method is not itself a function value – "eta-expansion".

object List {
 // List(1,2) = List.apply(1, 2)

 def apply[T](x: T): List[T] = ...

Type Bounds (4.3)

def assertAllPos[S <: InstSet](r: S): S = ...

• [S <: IntSet] is an "upper bound" of the type parameter S – ranges only suptypes
• [S >: NonEmpty] is an "lower bound" – ranges only supertypes
• [S >: NonEmpty <: IntSet] – mixed bound

Covariance

NonEmpty[] :< IstSet[]

Types for which this relationship holds is a "covariant".

The Liskov Substitution Principle

"If A <: B, then everything one can to do with A, could be done with B."

Variance (4.4)

Immutable types can be covariant, if some conditions are met.

class C[+A] { ... } – C is covariant class C[-A] { ... } – C is contravariant

if A1 <: A2 and B1 <: B2, then A1 ⇒ B1 <: A2 ⇒ B2

trait Function1[-T, +U] {
  def apply(x: T): U
}

trait List[+T] {
  ...
  // def prepend(elem: T): List[T] = new Cons(elem, this) // ← type error: `val xs: List[IntSet]; xs.prepend(Empty): List[IntSet]`
  def prepend[U >: T] (elem: U): List[U] = new Cons(elem, this)
}

object Nil extends List[Nothind] {
  def isEmpty = true
  def head: Nothing = throw new NoSuchElementException("Nil.head")
  def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}

object test {
  val x: List[String] = Nil
}

Decomposition (4.5)

def isInstanceOf[T]: Boolean // `x instanceof T`
def asInstanceOf[T]: T  // ← type casting in Java: `(T) x`

Pattern Matching (4.6)

Case Classes

trait Expr { .. }
case class Number(x: Int)  extends Expr { .. }
case class Sum(e1: Expr, e2: Expr) extends Expr { .. }

We can write Number(1) instead of new Number(1). But classes are empty.

"Pattern matching" is a generalisation of switch from C/Java to class hierarchies.

e match {
  case pat1 ⇒ expr1
    ...
  case patN ⇒ exprN
}

Patterns:

• constructors, e.g. Number, Sum
• variables, e.g. n, e1, `e2
• wildcard patterns _
• constants, e.g. 1, true

Names of constants begin with a capital letter, except true, nil, etc.

trait Expr {
  def eval: Int = this match {
    case Number(n) ⇒ n
    case Sum(e1, e3) ⇒ e1.eval() + e2.eval()
  }
}

"Expression Problem"

def show(e: Expr): String = e match {
  case Number(x) => x.toString
  case Sum(l, r) => show(l) + " + " + show(r)
}

Lists (4.7)

Lists as a part of collections.

to define a list: List(x1, .., xN)

Lists vs Arrays:

• lists are immutable
• list are recursive, arrays are flat.

val fruits: List[String] = List("apple", "orange")

Constructors of List

fruit = "apple" :: ("orange :: ("pears" :: Nil))
empty = Nill

A :: B :: C is interpreted as A :: (B :: C).

Operations on List

• head – the first element of the list
• till – the list composed of all els except the first
• isEmpty – true if the list is empty

List Patterns

• Nil – the Nil constant.
• p :: ps – a pattern that match a list with a head matching p and a tail matching ps.
• List(p1, ..., pN) – same as p :: .. :: pN :: Nil

x :: y :: List(xs, ys) :: zs, L >= 3

Sorting List

"Inserting Sort":

def isort(xs: List[Int]): List[Int] = xs match {
  case List() ⇒ List()
  case y :: ys ⇒ insert(y, isort(ys))
}

def insert(x: Int, xs: List[Int]): List[Int] = xs match {
  case List() ⇒ List(x)
  case y :: ys ⇒ if (x < y) x :: xs else y :: insert(x, ys)
}

5week.md

Week 5 (Lists)

List Methods (5.1)

xs.length
xs.last
xs.init

xs take n
xs drop n

xs(1)

Creating Lists

xs ++ ys

xs.reverse

xs.updated (n, x)

Searching

xs indexOf x
xs contains x

Implementing init

def init[T](xs: List[T]): List[T] = xs match {
  case List() ⇒  throw new Error("init of empty list")
  case List(x) ⇒ List()
  case y :: ys ⇒ y :: init(ys)
}

Lists Concatenation

// xs ::: ys

def concat[T](xs: List[T], ys: List[T]) = xs match {
  case List() ⇒ ys
  case z :: zs ⇒ z :: concat(zs, ys)
}

Lists Reversion

def reverse[T](xs: List[T]) = xs match {
  case List() ⇒ List()
  case y :: ys ⇒ reverse(ys) ++ List(y)
}

Implement removeAt

def removeAt[T](n: Int, xs: List[T]): List[T] = (xs take n) ::: (xs drop (n + 1))

Pairs and Tuples (5.2)

The pair in Scala consists of x and y and is written as (x, y)

val pair = ("answer", 42)
val (label, value) = pair

val (labe, value) = pair

or

val label = pait._1
val value = pait._2

Implicit Parameters (5.3)

def msort[T](...)(implicit ord: Ordering): List[T] = ...

Higher-Order List Functions (5.4)

Applying a Function to Elements of a List

Map Method

xs map (x ⇒ x * factor)

Filtering a List

def filter(p: T ⇒ Boolean): List[T] = this match {
  case Nil ⇒ this
  case x :: xs ⇒ if (p(x)) x :: xs.filter(p) else xs.filter(p)
}

xs filter (x ⇒ x > 0)

Variations of Filter

• xs filterNot p
• xs partition p → filter(p) ++ filterNot(p)
• xs takeWhile p
• xs dropWhile p
• xs span p → takeWhile(p) ++ dropWhile(p)

Reduction of Lists (5.5)

"Fold" or "reduce" or "combine" operations.

List(x1, ..., xN) reduceLeft op = ( ... (x1 op x2) op ...) op xN

A Shorter Way to Write Functions

(_ * _) – ((x, y) ⇒ x * y)

def sum = (0 :: xs) reduseLeft (_ + _)

foldLeft:

• a more generic version of reduceLeft
• takes an accumulator as an additional parameter

def foldLeft[U](z: U)(op: (U, T) ⇒ U): U = this match {
  case Nil ⇒ z
  case x :: xs ⇒ (xs foldLeft op(x, z))(op)
}

Reasoning about Concat (5.6)

Structual induction of lists referential transparency

6week.md

Week 6 (Collections)

Other Sequences (6.1)

Vectors

Lists are linear. Vector has more evenly balanced access patterns than List.

Operations on Vectors

val nums Verctor(1,2,3,-88)

• x :+ xs
• xs :+ x

Complexity – log32(N)

Ranges

val r: Range = 1 until 5 // 1,2,3,4
val s: Range = 1 to 5 // 1,2,3,4,5
1 to 10 by 3
6 to 1 by -2

def isPrime(n: Int): Boolean = (2 until n) forall (d ⇒ n % d != 0)

Combinatorial Search and For-Expressions (6.2)

Handling Nested Sequences

xs flatMap f = (xs map f).flatten

For-Expression Example

case class Person(name: String, age: Int)

for ( p ← persons if p.age > 20 ) yield p.name

Syntax of For

for (s) yield e

s is a sequence of generators and filters

• a generator is of the form p ← e, where p is a pattern and e an expression
• a filter if of form if f where f is a boolean expression

for {
  i ← 1 until n
  j ← 1 until j
  if isPrime(j)
} yield (i, j)

Combinatorial Search Example (6.3)

Sets

val fruits = Set("apple", "banana")
val s = (1 to 6).toSet

• Sets are unordered
• Sets do not have duplicates

The fundamental operation of sets is contains.

Example: N-Queens

Maps (6.4)

val romanNums = Map('I' → 1, 'V' → 5, 'X' → 10)

Maps are Functions

romanNums("X") 

romanNums get "L" // None

The Option Type

Sorted and GroupBy

val fruit = List(...)
fruit sortWith(_.length < _.length)
fruit.sorted

groupBy partitions a collection into a map of collections according to a discriminator function f

Default Values

val cap1 = someMap withDefaultValue "defaultValue"

k → v – binding

Putting the Pieces Together (6.5)

Phone keys have mnemonics assigned to them.

val mnem = Map(
  '2' → "ABC", '3' → "DEF", '4' → "GHI", '5' → "JKL",
  '6' → "MNO", '7' → "PQRS", '8' → "TUV", '9' → "WXYZ")

val charCode: Map[Char, Char] = 
  for ((digit, str) ← mnem; letter ← str) yield letter → digit

conclusion.md

Course Conclusion

Traits of Functional Programming

• "Scala School" by Twitter
• "Scala Exercises"