William Liu

Scala

#Summary

These are my notes from taking the Coursera course Functional Programming Principles in Scala taught by Martin Odersky himself. The course teaches you about functional programming and we just happen to use Scala.

Install

On Ubuntu, I’m using Scala 2.11, which needs Java 8 (not Java 10)

sudo add-apt-repository ppa:webupd8team/java
sudo apt-get update
sudo apt-get install oracle-java8-installer
sudo apt-get install oracle-java8-set-default

Test that these are installed correctly with:

java -version
java version "1.8.0_181"
Java(TM) SE Runtime Environment (build 1.8.0_181-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.181-b13, mixed mode)
    
scala -version
Scala code runner version 2.11.6 -- Copyright 2002-2013, LAMP/EPFL

Also install sbt version that matches your Scala version sudo apt-get install sbt=0.13.13

#Week 1 (Lesson 1)

##Programming Paradigms

There’s three main programming paradigms (these describe distinct concepts or thought patterns in programming). They are:

###What is Imperative Programming?

####Von Neumann Computer Wait, what? So most computers are under this model called the Von Neumann computer (aka Princeton Architecture); the idea is that we have a CPU connected to Memory via a Bus, where the width of the Bus is about one machine word (e.g. 32bit, 64bit). The CPU processes instructions while the Memory holds more instructions and/or data.

####Von Neumann Bottleneck With this architecture, computers can either read data that’s in memory OR pass the next instruction; they can’t do both at the same time and this is a bottleneck called the von Neumann bottleneck.

This setup has affected how we program.

With this setup, we’re conceptualizing programs word by word and that’s bad for performance (when we try to scale up). Instead we want to define high-level abstractions such as collections, shapes, documents, etc. What we need are theories.

####Theories What we want out of these theories is a way to create high-level abstractions for different data types. These theories consist of data types and the operations on these data types; a theory does NOT allow mutations (e.g. you can’t define a variable as a specific value, then change that variable’s value). Let’s think about it; if you do mutations, it destroys the point of having these high-level concepts. Here’s an example of imperative programming using classes (a way to abstract) doing mutations by assigning a coefficient to the Class.

class Polynomial { double[] coefficient; }
Polynomial p = ...;
p.coefficient[0] = 42;

###What is Functional Programming?

You can think of functional programming as a glass half full or half empty.

#Week 1 (Lesson 2 and 3)

##Scala REPL

Scala’s REPL (Read-Eval-Print-Loop) is an interactive shell that can be started with either one of the commands scala or sbt console (for the scala build tool).

##What are Functions?

Good question. We have a lot of primitive expressions that defines the simplest elements of the language (say this is a string, that is a number). Well, functions just wrap all of that together nicely.

##How functions are evaluated

One of the most important things with Scala is how you evaluate functions; think back in elementary school when you learned about PEMDOS and how it applies rules of precedence for Math, but this is for programming. Well, this is just like simple algebra. We call this the Substitution Model and we apply these steps one by one so that all evaluation does is reduce an expression to a value.

  1. Take the leftmost operator
  2. Evaluate its operands (left before right)
  3. Apply the operator to the operands.

##Parameters

You can define a Function with parameters. Notice how the variable type (e.g. Double) comes after the variable name (e.g. x)

def square(x: Double) = x * x
def sumOfSquares(x: Double, y: Double) = square(x) + square(y)

##Evaluation Strategies

There’s two ways you can evaluate functions, through call-by-value (CBV) and call-by-name (CBN). Both strategies end up reducing to the same final values, but its important because depending on the function, some may terminate (to get a final value) while others (when CBV is used) sometimes goes into an infinite loop! Performance is also different; CBV calls a function argument once, but sometimes some function arguments don’t need to be called; the reverse can be true and some CBN can evaluate the function argument multiple times.

###Call by Value (CBV)

CBV evaluates every function argument only once. Each function argument is reduced to a value before rewriting the function. Here’s an example:

sumOfSquares(3, 2+2)
square(3) + square(2+2) # keep right hand side, pass 2+2 as an expression
3 * 3 + square(2+2)
9 + square(2+2)
9 + (2+2) * (2+2)
25

###Call by Name (CBN)

CBN evaluates a function argument lazily (i.e. we’ll evaluate the code only when it’s called). Here’s an example:

def test(x: Int, y: Int) = x * x  # we pass in x, but y isn't needed so its not evaluated
test(3+4, 8)
(3+4) * (3+4)
7 * (3+4)
7 * 7
49

###Forcing Evaluation Strategies

By default, Scala uses Call by Value (CBV) because usually this is much more efficient. However, CBV also has the issue that sometimes using this evaluation method will result in an infinite loop (whereas using CBN might not get into an infinite loop). If you want Scala to force use CBN (the non default), then add in =>.

#Week 1 (Lesson 4)

##Conditionals and Value Definitions

Scala has conditional expressions like if-else to help choose between two things. Notice that we say expression instead of statement.

###Expressions versus Statements

There’s a key difference between these two; a statement is where you set a variable AND THEN return a variable. An expression (sometimes called predicates) is where you just return a value without needing to set a variable.

###Boolean Expressions

true, false # Constants
!x # Negation
b && b # Conjunction, i.e. AND
b || b # Disjunction, i.e. OR

###Value and Definition Forms

Definitions (i.e. def) in a sense are CBN (because the right hand of the definition is evaluated on each use) while Values (i.e. val) is CBV (because its a value).

#Week 1 (Lesson 5)

##Sample code doing Square Roots with Newtons Method

We want to create a function that calculates the square root of parameter x. The idea is to start with any positive initial estimate, then repeatedly improve our estimate by taking the mean of y and x/y.

def sqrtIter(guess: Double, x: Double): Double =
    if (isGoodEnough(guess, x)) guess
    else sqrtIter(improve(guess, x), x)

def isGoodEnough(guess: Double, x: Double) =
    abs(guess * guess - x) / x < 0.001

def improve(guess: Double, x: Double) =
    (guess + x / guess) / 2

def sqrt(x: Double) = sqrtIter(1.0, x)

#Week 1 (Lesson 6)

##Fight Name space pollution with Blocks

You can avoid name space pollution by using blocks, which means enclosing code with { and }. For example:

def sqrt(x: Double) = {
    def sqrtIter(...)
    def isGoodEnough(...)
    def improve(...)
}

###Block Rules

##Line Continuation

###Parenthesis Example (someLongExpression + someOtherLongExpression)

###Infix Operator Example someLongExpression + someOtherLongExpression

#Week 1 (Lesson 7)

##Sample code doing Recursion

Try to create the ‘Greatest Common Divisor’ of two numbers; use an implementation using Euclid’s algorithm.

###Attempt 1

While this works, you might get a Stackoverflow if the JVM keeps doing a deep recursive chain on a function that is not tail-recursive.

def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a %b)  # is a 'tail-recursive' call

def factorial(n: Int): Int =
    if (n==0) 1 else n * factorial(n-1)  # not a 'tail-recursive' call, still have to compute n

###Attempt 2 (Refactored)

We want to attempt this implementation as a tail-recursive call, meaning that a function calls itself as its last action so that the function’s stack frame can be reused. Now we won’t get a stackoverflow.

object exercise {
    def factorial(n: Int): Int = {
        def loop(acc: Int, n: Int) =
            if (n==0) acc
            else loop(acc * n, n-1)
        loop(1, n)
    }
}

#Additional Notes

#Week 2 (Lesson 1)

##Higher-Order Functions

Functional languages treat functions as first-class values. This means that functions can be passed as a parameter and returned as a result. When a function takes other functions as parameters or return a function as a result, then they are higher order functions. This is similar to how other languages can pass around strings or numbers as parameters and results. Here’s some examples:

// Take the sum of the integers between a and b 
def sumInts(a: Int, b: Int): Int = 
    if (a > b) 0 else a + sumInts(a + 1, b)

// Take the sum of the cubes of all the integers between a and b
def cube(x: Int): Int = x * x * x
def sumCubes(a: Int, b: Int): Int = 
    if (a > b) 0 else cube(a) + sumCubes(a + 1, b)

// Take the sum of the factorials of all the integers between a and b
def sumFactorials(a: Int, b: Int): Int =
    if (a > b) 0 else fact(a) + sumFactorials(a + 1, b)

##Finding Patterns in Higher-Order Functions

Scala is a lot like Math (in particular Algebra). In Algebra, when you look at equations, you can do factoring. With the above examples, you can start seeing a pattern and find the common factor (i.e. what’s in all of these expressions). We can sumInts, sumCubes, sumFactorials, or really sum anything. We want to ask ourselves, what is this common factor between all of these functions?

// This sum method is our common factor
def sum(f: Int => Int, a: Int, b: Int): Int =
    if (a > b) 0
    else f(a) + sum(f, a + 1, b)

// We can now rewrite these methods like this
def sumInts(a: Int, b: Int) = sum(id, a, b)
def sumCubes(a: Int, b: Int) = sum(cube, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)

// We need some auxiliary functions
def id(x: Int): Int = x
def cube(x: Int): Int = x * x * x
def factorial(x: Int): Int = if ( x == 0) 1 else fact(x-1)

##Function Types

The type A => B is the type of a function that takes an argument type A and returns a result of type B. An example would be Int => Int is the type of functions that map a Integers to Integers.

##Anonymous Functions

Earlier we created some auxiliary functions (e.g. def id(x: Int): Int = x). Instead of auxiliary functions, we can create anonymous functions for us to avoid having to define and name functions using def. A common example is that we don’t need to define a string using def and then print it; we could just print the string.

// Rewriting our examples as anonymous functions where we can define x inside the function
def sumInts(a: Int, b: Int) = sum(x => x, a, b)
def sumCubes(a: Int, b: Int) = sum(x => x * x * x, a, b)
def sumFactorials(a: Int, b: Int) = sum(fact, a, b)

// No need to do this
def str = "abc"; println(str)

// Instead we can directly write because strings are literals
println("abc")

#Week 2 (Lesson 2)

##Currying

So now that we know about higher order functions, we want to look at currying, which is a special way of writing higher order functions. The idea is that your returned function might expect parameters, but they don’t need to be explicitly passed in; what this solves is getting rid of repetition in your parameter list. For example, in our functions above (e.g. Lesson 1’s Higher Order Functions, Anonymous Functions), we still need to pass in a, b into the parameter list.

We can rewrite sum as a function that returns another function. sum now only takes a single parameter f and it returns a function. The returned function sumF applies the given function parameter f and sums the results.

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

##Stepwise Applications

Now that sum is a function that returns another function, we can then define our sumInts, sumCubes, and sumFactorials using our new sum function.

def sumInts = sum(x=> x)
def sumCubes = sum(x => x * x * x)
def sumFactorials = sum(fact)

You can apply these functions in turn like this:

sumCubes(1, 10) + sumFactorials(10, 20)

##Consecutive Stepwise Applications

We can even avoid the sumInts, sumCubes, sumFactorials by writing consecutive stepwise applications, like this:

sum (cube) (1, 10)

What this does is:

##Multiple Parameter Lists

Functions that returns functions has a special syntax. These two are equivalent:

// Previous way of writing sum (as three parameters)
def sum(f: Int => Int): (Int, Int) => Int = {
    def sumF(a: Int, b: Int): Int =
        if (a > b) 0
        else f(a) + sumF(a +1, b)
    sumF
}

// sum as multiple parameter lists; you can then write: sum (cube) (parameter list)
def sum(f: Int => Int)(a: Int, b: Int): Int =
    if (a>b) 0 else f(a) + sum(f)(a+1, b)

###Expansion of Multiple Parameter Lists

These two are equivalent and is an example of currying.

def f (args 1) ... (args n-1) (args n) = E

// f has n nested anonymous functions
def f = (args 1 => (args 2 => ... (args n => E) ... ))

##Function Types

Function types associate to the right. Say we have this sum function:

def sum(f: Int => Int)(a: Int, b: Int): Int = ...

The type of sum is calculated like this:

(Int => Int) => (Int, Int) => Int
Int = > Int => Int
Int => (Int => Int)  // we put parenthesis for function types on the right

##Examples

object exercise {

    //product function that calculates the product of the values for the points on a given interval
    def product(f: Int => Int)(a: Int, b: Int): Int =
        if (a > b) 1
        else f(a) * product(f)(a +1, b)
     
     //Can test product with this, gets the product between 3 and 4
     product(x => x * x)(3, 4)  // Int = 144

     //factorial in terms of product; multiplication of all numbers been 1 and n
     def fact(n: Int) = product(x => x)(1, n)
     
     //Can test factorial with this, gets the factorial
     fact(5)  // Int = 120
     
     //a general function for product and sum
     def mapReduce(f: Int => Int, combine: (Int, Int) => Int, zero: Int)(a: Int, b: Int): Int =
         if (a > b) zero
         else combine( f(a), mapReduce(f, combine, zero)(a + 1, b))

     //mapReduce version of product
     def product(f: Int => Int)(a: Int, b: Int): Int = mapReduce(f, (x, y) => x * y, 1)(a, b)
     //Can test mapReduce version of product function with this
     product(x => x * x)(3, 4)  // Int = 144 
}

#Week 2 (Lesson 3)

##An example of Higher Order Function with Currying

We’re creating an example to calculate the ‘fixed point’ of a function; a number x is called a fixed point of a function f if f(x) = x. We then apply f in a repetitive way, like x, f(x), f(f(x)), f(f(f(x))). An example is x = 1 + x/2 where we keep applying the function in a way that as it approaches the value (2), there isn’t any significant change.

import math.abs

object exercise {
    val tolerance = 0.0001
    def isCloseEnough(x: Double, y: Double) = 
        abs((x - y) / x) /x < tolerance  // isCloseEnough (x: Double, y: Double) Boolean
    def fixedPoint(f: Double => Double)(firstGuess: Double) = {
        def iterate(guess: Double): Double = {
            val next = f(guess)
            if (isCloseEnough(guess, next)) next
            else iterate(next)
        }
        iterate(firstGuess)
    }
    fixedPoint(x => 1 + x/2)(1)  // Double = 1.99975

    // need averageDamp function or else will sqrt will oscillate between 1 and 2
    def averageDamp(f: Double => Double)(x: Double) = 
        (x + f(x))/2

    // averageDamp is a function that takes a function (square root) and returns another function
    def sqrt(x: Double) =
        fixedPoint(averageDamp(y => x / y))(1)

    sqrt(2) // Double = 1.4142
}

##Notes on abstraction

Functions are essential abstractions because they allow us to introduce general methods to perform computations. We’ve seen that these abstractions can be combined with higher-order functions to create new abstractions.

The highest level of abstraction is not always the best. Know when to use abstractions.

#Week 2 (Lesson 4)

##Scala Syntax in Extended Backus-Naur form (EBNF)

So far we’ve covered elements to express Types, Expressions, and Definitions.

##Types

So far we’ve seen two forms of types, Simple Type (e.g. Numeric Type, String Type, Boolean Type) and Function Type.

##Expressions

Categories of expressions can be:

##Definitions and Parameters

So far we’ve seen two types of definitions, a Function Definition and a Value Definition. We’ve also seen that parameters can be call-by-value parameter or call-by-name parameter.

#Week 2 (Lesson 5)

##Functions and Data

We’re going to introduce objects and classes, which means we’ll use functions to create and encapsulate data structures. An example is if we want to represent Rational Numbers (say two integers x and y where its represented by numerator x / denominator y).

###Example implementation of Rational Numbers (Bad)

We could implement Rational Numbers with what we know right now and it would look like this, but it’s really clunky trying to manage so many numerators and denominators.

# Ewww
def addRationalNumerator(n1: Int, d1: Int , n2: Int, d2: Int): Int
def addRationalDenominator(n1: Int, d1: Int, n2: Int, d2: Int): Int

##Classes

Instead of using functions for Rational Numbers, we can instead define a class to better encaspulate our data.

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

The class now introduces two entities:

###Types and Objects

A type is essentially a set of values. The values that belong to a class type is called an object. We create an object by prefixing with the keyword new.

val temp = new Rational(1, 2)
temp.numer // 1
temp.denom // 2

###Example: Rational class as a Pure Data Type with arithmetic methods outside class

One way we can implement Rational arithmetic is by keeping Rational as a pure data type. This gives us the data and we define functions outside of the class. Here’s how that could be done:

// Doing Rational arithmetic with Rational as a pure data type
def addRational(r: Rational, s: Rational): Rational = 
    new Rational(r.numer * s.denom + s.numer * r.denom, r.denom * s.denom)

// Helper Function to print Rational nicely; notice outside Rational class
def makeString(r: Rational) =
    r.numer + "/" + r.denom

makeString(addRational(new Rational(1, 2), new Rational(2, 3)))  // 7/6

###Example: Rational class with arithmetic methods defined inside the class

Another way of implementing Rational arithmetic is by putting the arithmetic functions inside the Rational class. Note that when a function is inside a class, its now called a method. This is helpful since you can look at a class and immediately see what methods are available (e.g. multiply, substract, add, neg)

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

    def add(that: Rational) = 
        new Rational(numer * that.denom + that.number * denom, denom * that.denom)

    def neg: Rational = new Rational(-numer, denom)

    def subtract(that: Rational) = add(that.neg)
    
    override def toString = numer + "/" + denom        
}

#Week 2 (Lesson 6)

##Data Abstraction

We’re going to talk about the idea of data abstraction, which is the ability to choose different implementations of data without affecting how the clients see the data. For example, we’ll go over a few ways of creating a Rational class that returns a simplified value.

###Data Abstraction with creating private methods and members (calls gcd calculation method just once during class construction)

We now want our rational numbers to be simplified. We could add a simplification step in each one of our methods (e.g. at the end of multiply, subtract, add, neg, etc), but the issue with that is it violates DRY (Don’t Repeat Yourself) and it would be easy to forget to add this step. Instead, let’s perform the simplification just once during the initialization of the object (i.e. when the object is constructed). Let’s see how we can do that:

class Rational(x: Int, y: Int) {
    private def gcd(a: Int, b: Int): Int = 
        if (b == 0) a else gcd(b, a % b)
    private val g = gcd(x, y)  // private member
    def numer = x / g
    def denom = y / g

    def add(that: Rational) =
        new Rational(numer * that.denom + that.numer * denom, denom * that.denom)
    // ... additional methods
}

What we’re doing is creating private members (e.g. private val g); they’re fields that can only be accessed from inside the Rational class. Notice that we’re calculating gcd immediately so that it can be re-used in the calculations of numer and denom without need to recalculate each time numer or denom is called.

###Data Abstraction with calculating gcd each time method is called

If we wanted to, we could change it so that gcd is calculated every time the function is called (in case this calculation changes based on other values). We also have one less variable g. The advantage to this is if numer and denom are not called frequently.

class Rational(x: Int, y: Int) {
    private def gcd(a: Int, b: Int): Int = 
        if (b == 0) a else gcd(b, a % b)
    def numer = x / gcd(x, y)
    def denom = y / gcd(x, y)
}

###Data Abstraction with values instead of methods

If we replaced numer and denom as a val instead of a def, this ensures that values are only computed once. The advantage to this is if the functions numer and denom are called often.

class Rational(x: Int, y: Int) {
    private def gcd(a: Int, b: Int): Int = 
        if (b == 0) a else gcd(b, a % b)
    def numer = x / gcd(x, y)
    def denom = y / gcd(x, y)
}

##Class this

In the inside of a class, the keyword this represents the current object. Note, some other object oriented languages call this self.

class Rational(x: Int, y: Int) {
    ...
    def less(that: Rational) = numer * that.denom < that.numer * denom
    def max(that: Rational) = if (this.less(that)) that else this
}

##Preconditions

We can set preconditions using either requirements or assertions. The difference between the two is the intent.

###Requirements with require

An example is if we tried to divide by zero on a Rational.

class Rational(x: Int, y: Int) {
    require(y > 0, "denominator must be positive")
    ...
}

The require function is a predefined function that takes a condition and an optional message. If the condition fails to pass, an IllegalArgumentException is thrown with the message. Here, if the denominator y is equal or less than 0, then the message “denominator must be positive” gets returned.

###Assertions with assert

Assertions are another precondition. If the condition fails to pass, an AssertionError is returned.

val x = sqrt(y)
assert(x >= 0)

##Constructors

A class automatically implicitly introduces a constructor called the primary constructor of the class. The primary constructor:

###Secondary Constructors

So what’s an example of a regular constructor (that isn’t the primary constructor)? We can create a Rational constructor that assumes a denominator of 1 if no second parameter (denominator) is passed in.

class Rational(x: Int, y: Int) {
    require(y !=0, "denominator must be positive")
    def this(x: Int) = this(x, 1)  // our second constructor if there is no y passed
}

We can then use our new constructor with new Rational(2) and it returns a Rational of 2.

#Week 2 (Lesson 7)

##Classes and Substitution Model

Previously we went over how functions are evaluated, now how does the Substitution Model work on Classes and Objects (instead of a function now)?

###Evaluating a new Class

Say we have a new class new C(e1, ... en). The expression e1 ... en are evaluated like the arguments of a normal function. The new resulting expression is then new C(v1 ... vn) where they are already values.

###Evaluating a new Class with methods

Say we have a new class like this:

class C(x1, ..., xn) {
    def f(y1, ..., yn) = ...
}

We would then do the following three substitutions:

The result would be:

[w1/y1, ..., wn/yn][v1/x1, ..., vn/xn][new C(v1, ..., vn)/this]b

###Example: Evaluating a new Class with methods

Let’s look at some examples of how Substitution works with Classes and methods.

####Example 1

class Rational(x, y){
    def numer = x
    def denom = y
    def less(that: Rational) = ...
} 

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

There’s three substitutions at play; the first part is the class parameter (1 replaces x, 2 replaces y), the second part is empty [] because the numer method doesn’t have any parameters, and the third part replaces this with a new occurrence of the object new Rational(1, 2) . The definition for numer is just x.

####Example 2

new Rational(1, 2).less(new Rational(2, 3))
// [1/x, 2/y][new Rational(2, 3)/that][new Rational(1, 2)/this]
// = this.numer * that.denom < that.numer * this.denom
// = new Rational(1, 2).numer * new Rational(2, 3).denom <
//     new Rational(2, 3).numer * new Rational(1, 2).denom
// = 1 * 3 < 2 * 2
// = true

We have three substitutions at play again. The first part is the class parameter (1 replaces x, 2 replaces y) substitution. The second part is the substitition of the argument (new Rational(2, 3) for the that parameter in the less method). The third part is the substitition that replaces the this in the body with new Rational(1, 2).

##Operators

So what’s the difference between writing x + y (if x and y are integers), but then we’re writing r.add(s) if r and s are rational numbers? We should change that because we should be able to use operators like + on our Rational numbers.

###Step 1: Infix Notation

Scala allows any method with a parameter to be used like an infix operator.

r add s  // same as: r.add(s)
r less s // same as: r.less(s)
r max s // same as: r.max(s)

###Step 2: Relaxed Identifiers

Operators can be used as identifiers. An identifier can be:

###Example: Using Identifiers for class Rational

class Rational(x: Int, y: Int) {
    def < (that: Rational) = numer * that.denom < that.numer * denom
    def max (that: Rational) = if (this < that) that else this
    def + (that: Rational) = new Rational(
        numer * that.denom + that.numer * denom, denom * that.denom)
    def unary_- : Rational = new Rational(-numer, denom)  // prefix operator of - 
    def - (that: Rational) = this + -that  // infix operator of -
    
}

A few things to note is that we can replace most method names from a string to our relaxed identifiers (e.g. less is now <, add is now +). The main difference is that the prefix operator of - is much different than the infix operator of - so we need to add the keyword unary_ (followed by operator and a space).

##Precedence of Operator Rules

The precedence of an operator is determined by its first character. Here’s the lowest precedence to highest:

#Week 3 (Lesson 1) - Class Hierarchies

So far we’ve learned about instances of a single class so now we’re interested in how multiple classes work together. There’s class hierarchies, which means that classes can extend each other.

##Abstract Classes

Abstract Classes are notable because:

Here’s an example of an abstract class called IntSet, which will be a set of classes that implements sets of integers (both class Empty and class NonEmpty extends IntSet).

// since this is an abstract class, we don't need body for methods
abstract class IntSet {
    def incl(x: Int): IntSet
    def contains(x: Int): Boolean
}
... continued below

##Class Extensions

Let’s consider implementing sets as binary trees. There are two possible trees: 1.) A tree for the empty set, and 2.) a tree consisting of an integer and two sub-trees. Here’s their implementations:

... continued from above
// Class Extension Examples of Empty and NonEmpty extending IntSet

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

    override def toString = "."  // just showing as empty with a .
}

class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends 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 + "}"
}

object intsets {
    println("Testing our IntSet")
    val t1 = new NonEmpty(3, new Empty, new Empty)  // NonEmpty = {.3.}
    val t2 = t1 incl 4  // IntSet = {.3{.4.}}
}

##Base Classes and Subclasses

So with Class extensions, we now have superclass (IntSet) and subclass (e.g. Empty and NonEmpty)

###Implementation and Overriding

Here is another example of another Base Class and Subclass. Notice how if you try to override a method in a Subclass that does not exist in the Base Class you will get an error (because there is nothing to override).

object overrides {
    println("Welcome to the Scala worksheet")
}

abstract class Base {
    def foo = 1
    def bar: Int
}

class Sub extends Base {
    override def foo2 = 2  // When you write override, it'll return error because there was no foo2
    def bar = 3
}

##Object Definition vs Class Definition

Objects are just Classes except instead of a class, you specify access. For example, if we don’t need to create many instances, we don’t need a Class, but can instead just create a singleton object. For example, why will there be many instances of an Empty class? It’s just empty.

object Empty extends IntSet {
    def contains(x: Int): Boolean = false
    def incl(x: Int): IntSet = new NonEmpty(x, Empty, Empty)
}

##Standalone Programs

When we make programs, we can create standalone applications in Scala. Each application contains an object and a main method, like the below:

object Hello {
    def main(args: Array[String]) = println("hello world")
}

To run a program:

  1. You can create this as a ‘Scala Object’ in your editor
  2. Run it as a ‘Scala Application’
  3. On the console, you’ll see “hello world” printed out

##Dynamic Binding

Object Oriented Languages (including Scala) implements dynamic method dispatch. This means that the code invoked by a method call depends on the runtime type of the object that contains the method.

###Dynamic Binding Example

We apply our substitution rules.

// Empty contains 1
object Empty {
    def contains(y) = false
}

// (new NonEmpty(7, Empty, Empty)) contains 7
if (x < elem) this.left contains x
  else if (x > elem) this.right contains x else true

= if (7 < 7) new NonEmpty(7, Empty, Empty).left contains 7
    else if (7 > 7) new NonEmpty(7, Empty, Empty).right
      contains 7 else true

#Week 3 (Lesson 2)

#Class Hierarchies

Now that we know about Classes, we should consider how we organize many Classes together through packages.

##Packages

Classes and objects are organized into packages. To place a class or object inside a package, use a package clause at the top of your source file.

// Say this is in: progfun.examples file
package progfun.examples

object Hello { ... }

You can then run with > scala progfun.examples.Hello

###Example of making and using Packages

Assume we make a package called week3 using package

package week3

class Rational(x: Int, y: Int) {
    ...
}

###Imports

There’s a few ways you can import either the package or objects; the first two forms are named imports and the last form is a wildcard import:

import week3.Rational  // imports just Rational
import week3.{Rational, Hello} // imports both Rational and Hello
import week3._ // imports everything in package week3

###Automatic Imports

Some packages are imported automatically. These include:

##Traits

In Scala (and Java), a class can only have one superclass, this means its a single inheritance language. This is a bit constraining in that say you want to inherit behavior from multiple superclasses. Instead, you use traits, which are declared like an abstract class.

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

###Example: Traits

class Square extends Shape with Planar with Movable ...

Traits resemble interfaces in Java, but are more powerful because they can contain fields and concrete methods (opposed to interfaces that can only contain abstract methods).

###Traits vs Classes

The difference between Classes and Traits are that a Class can have value parameters while traits cannot. For example, in our Rational class, we ask for x:Int (numerator) and y:Int (denominator) as parameters. Traits can’t do this.

##Scala’s Class Hierarchy

###Scala Top Types

###Nothing Type

Nothing is at the bottom of Scala’s type hierarchity. It is a subtype of every other type. There is no value of type Nothing. Nothing is used to signal a couple of things:

###Exceptions

Scala and Java use the expression of throw Exc as a way to abort evaluation with the exception Exc.

import week3._

object scratch {
    new Rational(1, 2)

    def error(msg: String) = throw new Error(msg)  // error: (msg: String) Nothing

    error("test")  // would throw java.lang.Error
}

###Null

Every reference class type also has null as a value. The type of null is Null. Null is a subtype of every class that inherits from Object; it is incompatible with subtypes of AnyVal.

val x = null  // x : Null
val y: String = null  // y: String
val z: Int = null  // error: type mismatch

###Non matching types

Given this expression, whatever has more information will pick that data type.

if (true) 1 else false  // res1: AnyVal = 1

If true then will be int 1, else its false boolean. Both of these values are under the supertype (AnyVal has more info than Any) and then the type checker did AnyVal.

##Scaladoc

www.scala-lang.org/api/current

#Week 3 (Lesson 3) - Polymorphism

We’re going to talk about Types and Polymorphism. Types are how the compilers see functions and classes. The key is type parameterization, which means that classes and methos can can have types as parameters.

###Background info on Data Structure, the immutable list Cons-List (an immutable linked list)

A fundamental data structure in many functional languages is the immutable linked list. This is made up of two basic pieces:

  1. Nil, the empty list
  2. Cons a cell containing an element and the remainder of the list

###Example for Cons-List

// a simple list
List(1, 2, 3)
   1 
  / \
 1   1
    / \
   2   1
      / \
     3   Nil

// A list containing two nested lists
List(List(true, false), List(3))
          - 1 -
        /        \
      1            1
     / \          / \
  true  1        1   Nil
       /  \     / \
   false  Nil  3   Nil

How would we write these as Cons-Lists in Scala? We use type parameters to solve the problem of having to define lists of only type Int or type Double or type String, etc.

##Type Parameters

type parameters allow you to fill in a type instead of having to put in a specific type (e.g. Int, Double, String). All type parameters use brackets [].

###Example of a Cons-List

package week4

trait List[T]
class Cons[T](val head: T, val tail: List[T] extends List[T])
class Nil[T] extends List[T]

###Example Implementation of trait List[T]

package week4

trait List[T] {
    def isEmpty: Boolean
    def head: T
    def tail: List[T]
}

class Cons[T](val head: T, val tail: List[T] extends List[T]) {
    def isEmpty = false
}

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

###Generic Functions

Like classes, functions can also have type parameters. A function that creates a list consisting of a single element:

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

// we can then write
singleton[Int](1)  // list looks like: [1, Nil]
singleton[Boolean](true)  // list looks like: [true, Nil]

###Type Inference

Scala compiiler can usually tell the correct type parameters from the value parameters of a function call so in most cases, type parameters can be left out.

singleton(1)
singleton(true)

###Types and Evaluation

Type parameters do not affect evaluation in Scala because of type erasure, which removes all type parameters and type arguments before evaluating the program. A lot of other langauges use type erasure including Java and Haskell. Programs that keep type parameters at run time include C++, C#.

##Polymorphism

Polymorphism means that a function comes in many forms. This means that:

###Forms of Polymorphism

There are two principal forms of polymorphism:

  1. subtyping means instances of a subclass can be passed to a base class
  2. generics means instances of a function or class are created by type parameterization

###Exercise

Write a function nth that takes an integer n and a list and selects the n’th element of the list. Elements are numbered from 0. If index is outside the range from 0 up the length of the list minus one, an IndexOutOfBoundsException should be thrown.

import week4._

object nth {
    def nth[T](n: Int, xs: List[T]): T =
        if (xs.isEmpty) throw new IndexOutOfBoundsException
        if (n == 0) xs.head
        else nth(n - 1, xs.tail)
    
    val list = new Cons(1, new Cons(2, new Cons(3, new Nil)))

    nth(2, list)  // Int = 3 
    nth(4, list)  // IndexOutOfBoundsException
    nth(-1, list)  // IndexOutOfBoundsException
}

#Week 4 (Lesson 1) - Objects Everywhere (detail about Primitives)

Can you express everything we’ve talked about (primitives, functions, and instances of classes) as an object? Short answer, yes.

##Pure Object Orientation

In a pure object-oriented language, every value is an object. If the language is based on classes, this means that the type of each value is a class.

###Primitives as Objects

Scala’s numeric types and Boolean types can be implemented like normal classes.

#Week 4 (Lesson 2) - Objects Everywhere (detail about Functions)

###Functions as Objects

####Function Types (A => B)

In Scala, function values are treated as objects. The function type A => B is just an abbreviation for the class scala.Function1[A, B], which is roughly:

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

Basically, functions are just objects with apply methods.

####Function Values

An anonymous function looks like:

(x: Int) => x * x

This is expanded to:

class AnonFun extends Function1[Int, Int] {
    def apply(x: Int) = x * x
    new Anon
}

We can make an anonymous class syntax that looks even shorter:

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

####Function Calls

A function call looks like f(a, b) where f is a value of some class type. This can be expanded to f.apply(a, b). The object oriented translation looks like:

val f = (x: Int) => x * x
f(7)

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

####Functions and Methods

A method like def f(x: Int): Boolean = ... is not itself a function value. But if f is used in a place where a Function type is expected, it is converted automatically to the function value (x: Int) => f(x), or expanded to:

new Function1[Int, Boolean] {
    def apply(x: Int) = f(x)
}

###Example

package week4

trait List[T] {
    def isEmpty: Boolean
    def head: T
    def tail: List[T]
}

class Cons[T](val head: T, val tail: List[T]) extends List[T] {
    def isEmpty = false
}   

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

object List {
    // List(1, 2) = List.apply(1, 2)
    def apply[T](x1: T, x2: T): List[T] = new Cons(x1, new Cons(x2, new Nil))
    def apply[T]() = new Nil
}

#Week 4 (Lesson 3) - Subtyping and Generics

There are two principal forms of polymorphism:

In this session, we’ll look at their interactions:

##Type Bounds

Say you want to create a method assertAllPos which has the following criteria:

This might look like: def assertAllPos(s: IntSet): IntSet

###Upper Bound

A way to express that assertAllPos takes Empty setes to Empty sets and NonEmpty sets to NonEmpty sets. A way to express this is:

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

Here <: IntSet is an upper bound of the parameter S, meaning that S can be instantiated only to types that conform to IntSet. The notation is:

###Lower Bound

You can also use a lower bound for a type variable.

[S>: NonEmpty]

This example introduces a type parameter S that can range only over supertypes of NonEmpty. So S could be one of NonEmpty, IntSet, AnyRef, or Any.

###Mixed Bounds

You can mix upper bounds with lower bounds. For example, [S >: NonEmpty <: IntSet] would restrict S to any type on the interval between NonEmpty and IntSet (which for this interval its only these two).

##Covariance

Given NonEmpty <: IntSet, is List[NonEmpty] <: List[IntSet]? Yes, a list of non-empty sets is a special case of a list of arbitrary sets. We call types where this relationship holds covariant because their subtyping relationship varies with the type parameter. However, this doesn’t work for all types (e.g. Arrays don’t work for this in Java)

##The Liskov Substitution Principle

The Liskov Substitution Principle tells us when a type can be a subtype of another.

#Week 4 (Lesson 4) - Variance

#Week 4 (Lesson 5) - Decomposition

Let’s say you have a hierarchy of classes and you want to build tree-like data structures from these classes; how do you build a tree like this and find out what values are stored in these elements. This leads us to the topic of decomposition (aka factoring), where you break a complex problem or system into parts that are easier to understand, program, and maintain.

##Decomposition Idea

Say we want to write a small interpreter for arithmetic expressions.

##Decomposition Sample Code

trait Expr {
    def isNumber: Boolean  // Classification
    def isSum: Boolean  // Classification
    def numValue: Int  // Accessor
    def leftOp: Expr  // Accessor
    def rightOp: Expr  // Accessor
}

class Number(n: Int) extends Expr {
    def isNumber: Boolean = true
    def isSum: Boolean = false
    def numValue: Int = n
    def leftOp: Expr = throw new Error("Number.leftOp")  // Not applicable
    def rightOp: Expr = throw new Error("Number.rightOp")  // Not applicable
}

class Sum(e1: Expr, e2: Expr) extends Expr {
    def isNumber: Boolean = false
    def isSum: Boolean = true
    def numValue: Int = throw new Error("Sum.numValue")  // Not applicable
    def leftOp: Expr = e1
    def rightOp: Expr = e2
}

##Evaluation of Expressions

We can write an evaluation function, which is an expression that says what class to use. However, this becomes pretty tedious when we start adding more features.

def eval(e: Expr): Int = {
    if (e.isNumber) e.numValue
    else if (e.isSum) eval(e.leftOp) + eval(e.rightOp)
    else throw new Error("Unknown expression " + e)
}

Here’s where we are now:

        Expr
      /      \
    Numbers  Sum (leftOp, rightOp)

##Adding New Forms of Expressions

If we want to add more features, we need to add more methods for classification and for access to all our classes above. Say we wanted:

class Prod(e1: Expr, e2: Expr) extends Expr  // e1 * e2
class Var(x: String) extends Expr  // Variable 'x'

Now we want these additional methods:

               Expr
         /    /   \     \
    Numbers  Sum Prod   Var

We get a quadriatic increase in number of methods! That’s way too many.

##Type Tests and Type Casts

You can use Type Tests and Type Casts to tell what expression to run, however this is a hacky solution.

def eval(e: Expr): Int =
  if (e.isInstanceOf[Number])
    e.asInstanceOf[Number].numValue
  else if (e.isInstanceOf[Sum])
    eval(e.asInstanceOf[Sum].leftOp) + 
    eval(e.asInstanceOf[Sum].rightOp)
  else throw new Error("Unknown expression " + e)

Type casting is unsafe (in general, at runtime it might throw an exception) even though we guarded against this here.

##Solution 1: Object-Oriented Decomposition

If you want to just evaluate expressions, this works great, but for showing and simplifying, it becomes an issue. Here’s the code:

trait Expr {
    def eval: Int
}

class Number(n: Int) extends Expr {
    def eval: Int = n
}

class Sum(e1: Expr, e2: Expr) extends Expr {
    def eval: Int = e1.eval + e2.eval
}

The issue with this solution is that we have to define new methods in all the subclasses whenever we want to do more than just evaluate expressions (e.g. display expressions). We would then need a def show method.

#Week 4 (Lesson 6) - Pattern Matching

We continue our decomposition problem earlier. When we did the type tests and type casts, we were really looking to see the reverse of the construction process. We were checking what subclass was used and what the arguments of the constructor; this idea of recovering this information is used so often that Scala has an automated solution called pattern matching.

##Case Classes

So how does pattern matching work? We need to look into a case class, which is similar to a normal class with the exception that its preceded by the modifier case.

trait Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr

This defines a trait Expr and two concrete subclasses Number and Sum.

##Automatic magic of Case Classes

Case Classes automatically creates companion objects with apply methods.

object Number {
    def apply(n: Int) = new Number(n)
}

object Sum {
    def apply(e1: Expr, e2: Expr) = new Sum(e1, e2)
}

##Pattern Matching

Pattern matching is a generalization of switch from C/Java to class hierarchies. We use the keyword match.

def eval(e: Expr): Int = e match {
    case Number(n) => n
    case Sum(e1, e2) => eval(e1) + eval(e2)
}

##Match Rules and Syntax

This is the general syntax of a match.

e match {
    case pattern => expression,
    case patternn => expressionn
}

##Patterns Rules and Syntax

Patterns are constructed from the following:

Patterns have the following rules:

##Evaluating Match Expressions

An expression of the form e match { case p1 => e1 .... case pn => en } matches e with the patterns p1 through pn in the order they’re written. What happens after a pattern is matched?

The whole match expression is rewritten to the right-hand side of the first case where the pattern matches the selector e. References to pattern variables are replaced by the corresponding parts in the selector.

Uhh what? What does it mean that a pattern matches an expression?

###Pattern Matching Rules

###Example of Pattern Matching

Our eval function from pattern matching above:

def eval(e: Expr): Int = e match {
    case Number(n) => n
    case Sum(e1, e2) => eval(e1) + eval(e2)
}

Let’s see how our eval function now fits into Pattern Matching:

// First thing we do is rewrite the application with the body of `eval`
// the actual argument replaces the paramters
eval(Sum(Number(1), Number(2)))

// The next step is to evaluate the `match` Expression
// The first one (Number) doesn't match; the second one (Sum) does match
// The whole expression then rewrites to `eval(e1) + eval(e2)`
Sum(Number(1), Number(2)) match {
    case Number(n) => n
    case Sum(e1, e2) => eval(e1) + eval(e2)
}

// Rewrite the function application on the left
Number(1) match {
    case Number(n) => n
    case Sum(e1, e2) => eval(e1) + eval(e2)
} + eval(Number(2))

// We then do the eval(Number(2))
1 + eval(Number(2))

// We get our result
3

###Pattern Matching and Methods

We can define the evaluation function as a method of the base trait (instead of as an outside function).

Example:

trait Expr {
    def eval: Int = this match {
        case Number(n) => n
        case Sum(e1, e2) => e1.eval + e2.eval  // we can now use e1.eval instead of eval(e1)
    }
}

So should you be creating evaluation functions as part of an outside method or as part of a base trait or class hierarchy? It depends. This is actually called the Expression Problem because there’s tradeoffs to each.

###Pattern Matching Example

package week4

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

#Week 4 (Lesson 7) - Lists

##Lists

A list having x1, ..., xn as elements is written List(x1, ..., xn). There are two important differences between lists and arrays.

So why Lists? Lists have more built-in operators than arrays.

###List Examples

val fruit = List("apples", "oranges", "pears")
val nums = List(1, 2, 3, 4)
val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty = List()

Fruit would look like:

      1
    /    \
"apples"  1
        /    \
  "oranges"   1
            /    \
         "pears"  Nil

diag3 would look like:

               1
           /         \
          1                1   
        /  \           /       \ 
       1    1         1              1
           /  \      /  \           /  \
          0    1    0    1         1    Nil
              /  \      /  \      /  \
             0   Nil   1    1    0    1
                           /  \      / \
                           0  Nil   0   1
                                       / \
                                      1   Nil

##List Rules

Like arrays, lists are homogeneous, the elements of a list must all have the same type.

You can write the type of a list with elements of type T as scala.List[T] or shorthand just write List[T].

Example:

val fruit: List[String] = List("apples", "oranges", "pears")
val nums: List[Int] = List(1, 2, 3, 4)
val diag3: List[List[Int]] = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
val empty: List[Nothing] = List()

##Constructors of Lists

All lists are constructed from:

Example:

fruit = "apples" :: ("oranges" :: ("pears" :: Nil))
nums = 1 :: (2 :: (3 :: (4:: Nil)))
empty = Nil

This is similar to what we wrote before as new Cons(x, xs).

##Right Associativity

By convention, operators ending in : associate to the right.

A :: B :: C is interpreted as A :: (B :: C) so we can omit the parenthesis.

Operators ending in : are also different in that they are seen as method calls of the right-hand operand (reversed than what we’re used to where all method calls are left-hand operands).

val nums = 1 :: 2 :: 3 :: 4 :: Nil
val nums = 1 :: (2 :: (3 :: (4 :: Nil)))

// Method calls are expanded out to this
Nil.::(4).::(3).::(2).::(1)  // equivalent as above

Each method call prepends ~ to the list.

##Operations on Lists

Uses:

fruit.head == "apples"
fruit.tail.head == "oranges"
diag3.head == List(1, 0, 0)
empty.head == throw new NoSuchElementException("head of empty list")

##List Patterns

You can decompose a list using pattern matching (preferred way).

Examples

##Sorting Lists

Say we need to create our own sort for a List. One way is to create an insertion sort, which does:

Code Example

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

#Week 5 (Lesson 1) - More Functions on Lists

##Useful List methods

##More Useful List methods

Creating new lists:

Finding elements:

#Week 5 (Lesson 2) - Pairs and Tuples

If you want to sort lists faster, we can use merge sort instead of insertion sort. Merge sort does the following:

Pairs are two lists combined together (e.g. using zip).

Tuples are a fixed number of items together (with the difference over arrays and lists) being that tuples can hold objects with different types. Also immutable just like arrays and lists.

#Week 5 (Lesson 3) - Implicit Parameters

You can parameterize functions like the above merge sort. Make use of the keyword implicit so that we have implicit parameters, which means you can leave out the parameter (e.g. default argument for a function with an argument for Ordering), it’ll still automatically use the default argument instead of erroring.

#Week 5 (Lesson 4) - Higher-Order List Functions

So far all our lists were first order, meaning that functions took lists of primitive types as arguments and returned them as results.

##Map

With the map method of the List class, we can apply a function to each element of the List.

def scaleList(xs: List[Double], factor: Double) = 
  xs map (x => x * factor)

##Filter

With the filter method of the List class, we can return only specific elements.

def posElems(xs: List[Int]): List[Int] = 
  xs filter (x => x > 0)

#Week 5 (Lesson 5) - Reducing (aka Folding) of Lists

You can combine the elements of a list using a given operator; this might be getting the sum or product of a List.

def sum(xs: List[Int]): Int = xs match {
    case Nil => 0
    case y :: yx => y + sum(ys)
}

##ReduceLeft, ReduceRight

With the reduceLeft and reduceRight methods, we can insert a binary operator between adjacent elements of a list.

def sum(xs: List[Int]) = (0 :: xs) reduceLeft ((x, y) => x + y)
def product(xs: List[Int]) = (1 :: xs) reduceLeft ((x, y) = > x * y)

##Underscores (shortcut writing)

You can use an underscore _ to write functions shorter. Every _ represents a new parameter, going from left to right. The parameters are defined at the next outer pair of parentheses (or the whole expression if there are no enclosing parenthesis).

((x, y) => x * y)
(_ * _)  // same as above

Using underscores to write the above functions:

def sum(xs: List[Int]) = (0 :: xs) reduceLeft(_ + _)
def product(xs: List[Int]) = (1 :: xs) reduceLeft (_ * _)

##FoldLeft, FoldRight

With the foldLeft and foldRight method of the List class, we have similar functionality to reduceLeft and reduceRight, except it also takes an accumulator as an additional parameter.

##Notes about Left and Right Operators

Usually the foldLeft, foldRight and reduceLeft, reduceRight are the same (with maybe minor differences in efficency).

#Week 5 (Lesson 6) - Proving Laws

##Laws of Concat

We want to verify that concatenation is associative. To prove this, we’ll need to know about these proof principles:

##Referential Transparency

We have a principle called referential transparency that basically says that pure functional languages, an expression always evaluates to the same result in any context.

#Week 5 (Lesson 7) - Proving Laws (Continued)

More examples.

#Week 6 (Lesson 1) - Other Collections

Lists are linear (access to the first element is much faster than access to later elements).

##Vectors

There’s an alternative sequence implementation called Vectors. Vectors have more evenly balanced access patterns than Lists. Otherwise, they’re very similar (both are immutable).

###How do Vectors work?

Think of Vectors like this; basically we start with a 32 element array. When we need more elements than 32, one of the original elements is now an index:

                         [32 element array]
      [32 element array] [32 element array] [32 element array] ...
   [32 element array] ...

###Why use Lists then?

Simple access patterns (e.g. head, tail) are easier to access in Lists. If you use operations like map, then Vectors are better.

###Vectory Operations

val nums = Vector(1, 2, 3, -88)
val people = Vector("Bob", "James", "Peter")

Vectors support the same operations as lists, with the exception of ::. Instead of ::, we have:

##Collection Hierarchy

A common base class of List and Vector is Seq, the class of all sequences. Seq itself is a subclass of Iterable.

          Iterable
        /     |       \
      Seq    Set       Map
    /   |
List  Vectors

##Range

Another sequence is the range, which represents a sequence of evenly spaced integers. There are three operators:

Code Examples:

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  // 1, 4, 7, 10
6 to 1 by -2  // 6, 4, 2

Ranges aren’t represented as many elements; instead they’re a single object with three fields (lower bound, upper bound, step value).

###More Sequence Operations

####Sequence Code Examples:

package week6

object test {
    val xs = Array(1, 2, 3, 44)  // xs: Array[Int] = Array(1, 2, 3, 44)
    xs map (x => x * 2)  // res0: Array[Int] = Array(2, 4, 6, 88)
    
    val s = "Hello World"  // s: java.lang.String = Hello World
    s filter (c => c.isUpper)  // res1: String = HW
    s exists (c => c.isUpper)  // res2: Boolean = true
    s forall (c => c.isUpper)  // res3: Boolean = false

    val pairs = List(1, 2, 3) zip s  
    // pairs: List[(Int, Char)] = List((1,H), (2,e), (3,l))
    pairs.unzip
    // res4: (List[Int], List[Char]) = (List(1, 2, 3), List(H,e,l))

    s flatMap (c => List('.', c))  // Add a period in front of each char
    // res5: String = .H.e.l.l.o. .W.o.r.l.d
    
    xs.sum  // res6: Int = 50
    xs.max  // res7: Int = 44
}

####Sequence Code Examples (cont. 1):

To list all combinations of numbers x and y where x is drawn from 1 .. M and y is drawn from 1 .. N

(1 to M) flatMap (x => (1 .. N) map (y => (x, y)))

####Sequence Code Examples (cont. 2)

To compute the scalar product of two vectors

def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
  (xs zip ys).map(xy => xy._1 * xy._2).sum

// same as above, but with pattern matching
def scalarProduct(xs: Vector[Double], ys: Vector[Double]): Double =
  (xs zip ys).map{ case (x, y) => x * y }.sum

###Case and Match

Generally these two are equivalent:

{ case p1 => e1 ... case pn => en }

// equivalent to:
x => x match { case p1 => e1 ... case pn => en }

####Sequence Code Examples (cont. 3)

Given a number n is prime if the only divisors of n are 1 and itself. What is a high level way to write a test for primality of numbers?

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

#Week 6 (Lesson 2) - Combinatorial Search and For-Expressions

We’re going to look at how to handle nested sequences in combinatorial search problems.

##Nested Loop - Example

Say given a positive integer n, find all pairs of positive integers i and j with 1 <= j < i < n such that i + j is prime. For example, if n=7, the sought pairs are:

i  | 2 3 4 4 5 6 6
j  | 1 2 1 3 2 1 5
-----------------
i+j| 3 5 5 7 7 7 11

###Nested Loop Algorithm

What we want:

If we were programming in a non-functional language, we would probably create two for loops (one nested inside the other). But we’re not going to do that since we’re learning about functional programming. Instead, we will:

###Nested Loop Functional Code Example

We can combine until and map to solve this functionally (Note: we haven’t done the filtering yet)

object pairs = {
    val n = 7
    (1 until n) map (i => 
      (1 until i) map (j => (i, j)))
    // res0: scala.collection.immutable.IndexedSeq.... = Vector(Vector(), Vector((2,1)), Vector((3,1), (3,2)), ... (6,2), (6,3), (6,4), (6,5)))
}

Note: We got back an IndexedSeq, which is a type of Seq

This doesn’t look right (and I’m not talking about just the filtering yet). We want a Sequence, not a Sequence of Sequences.

###Generate Pairs (with flatten)

We can take a collection of collections and return a single collection (tldr; use the built-in method flatten for this). This can be done a couple ways (assuming our previous sequence of sequences returned xss).

(xss foldRight Seq[Int]())(_ ++ _)

// equivalent to using method `flatten`
xss.flatten

// this gives us
((1 until n) map (i =>
    (1 until i) map (j => (i, j)))).flatten

##flatMap and flatten

This is a useful law for flatMap and flatten:

xs flatMap f = (xs map f).flatten

Our above function can be simplified to this:

(1 until n) flatMap (i =>
  (1 until i) map (j => (i, j)))

We can continue to add to our function by filtering:

(1 until n) flatMap (i =>
  (1 until i) map (j => (i, j))) filter (pair =>
    isPrime(pair._1 + pair._2))
// res0: scala.collection.immutable.IndexedSeq....
// ... (4,1), (4,3), (5,2), (6,1), (6,5))

##For-Expressions

Scala’s higher-order functions map, flatMap, filter are really powerful in manipulating lists, but they can get complicated quickly.

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

// to get the names of persons over 20 years old
for (p <- persons if p.age > 20) yield p.name

// equivalent to:
persons filter (p => p.age > 20) map (p => pname)

The for-expression is similar to for-loops in imperative languages, but there’s one main difference: a for-loop has a side effect (changes something) while a for-expression produces a new result (with the yield) and doesn’t modify anything.

###Syntax of For-Expressions

The form is for (s) yield e.

Instead of (s), braces {s} can also be used, and then the sequence of generators and filters can be written on multiple lines without requiring semicolons.

###Use of For

Let’s solve again for the same problem: Say given a positive integer n, find all pairs of positive integers i and j with 1 <= j < i < n such that i + j is prime.

for {
    i <- 1 until n
    j <- 1 until i
    if isPrime(i + j)
} yield (i, j)

In the case of the scalarProduct function, we can now rewrite that using for:

def scalarProduct(xs: List[Double], ys: List[Double]): Double =
    (for((x,y) <- xs zip ys) yield x * y).sum

#Week 6 (Lesson 3) - Cominatorial Search and Sets

Sets are another basic abstraction in the Scala collections (same level as Sequences, Map). A set is written analogously to a sequence:

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

Most operations on sequences are also available on sets:

s map (_ + 2)  // Set(3, 4, 5, 6, 7, 8)
fruit filter (_.startsWith == "app") // Set("apple")
s.nonEmpty

##Sets vs Sequences

The principal differences between sets and sequences are:

Code Examples:

val s = (1 to 6).toSet
s map (_ / 2)  // Set(2, 0, 3, 1)
s contains 3  // true

#Week 6 (Lesson 4) - Maps

##Maps

Along with Sequences and Sets, another often used data type are Maps. Maps are are a little bit different because they’re both iterables and functions.

Maps have two parameters so it looks like: Map[Key, Value] is a data structure that associates keys of type Key with values of type Value.

###Map Example

val romanNumbers = Map("I" -> 1, "V" -> 5, "X" -> 10)  // Map[String, Int]
val capitalOfCountry = Map("US" -> "Washington DC", "Switzerland" -> "Bern")  // Map[String, String]

###Maps are also Functions

Class Map[Key, Value] also extends the function type Key => Value so maps can be used anywhere functions can. In particular, maps can be applied to key arguments in order to the value of the key.

capitalOfCountry("US")  // "Washington DC"

###Querying Maps with get

If you try to apply a key that isn’t there, you’ll get an exception. Use get to avoid throwing a NoSuchElementException.

capitalOfCountry("Andorra")  // java.util.NoSuchElementException: key not found

// to solve this, you can use `get`
capitalOfCountry get "Andorra"  // res0: Option[java.lang.String] = None
capitalOfCountry get "US"  // res1: Option[java.lang.String] = Some(Washington DC)

##Option Type

The Option type is defined as:

trait Option[+A]
case class Some[+A](value: A) extends Option[A]
object None extends Option[Nothing]

The expression map get key returns:

###Decomposing Option

Since options are defined as case classes, they can be decomposed using pattern matching:

def showCapital(country: String) = capitalOfCountry.get(country) match {
    case Some(capital) => capital
    case None => "missing data"
}

showCapital("US")  // "Washington DC"
showCapital("Andorra")  // "missing data"

##Sorted (orderBy) and GroupBy

groupBy and orderBy are two useful SQL operations that can be used to query alongside for-expressions. The Scala equivalent of orderBy is sortWith and sorted.

Code Example of sorting based off the word length or by alphabetical

val fruit = List("apple", "pear", "orange", "pineapple")
fruit sortWith (_.length < _.length)  // List("pear", "apple", "orange", "pineapple")
fruit.sorted  // List("apple", "orange", "pear", "pineapple")

###groupBy

groupBy is available on any Scala collections; it breaks down a collection into a map of collections according to a discriminator function f

fruit groupBy (_.head)  // > Map(p -> List(pear, pineapple),
                                 a -> List(apple),
                                 o -> List(orange))

###Map Example

A polynomial can be seen as a map from exponents to coefficients. For instance x^3 - 2x + 5 can be represented as a map.

object polynomials {
  class Poly(val terms: Map[Int, Double]) {
    def + (other: Poly) = new Poly(terms ++ other.terms map adjust))
    def adjust(term: (Int, Double)): (Int, Double) = {
      val (exp, coeff) = term
      terms get exp match {
        case Some(coeff1) => exp -> (coeff + coeff1)
        case None => exp -> coeff
      }
    } 
    override def toString = 
      for ((exp, coeff) <- terms.toList.sorted.reverse) yield coeff+"x^"+exp) mkString " + "
  }
  
  val p1 = new Poly(Map(1 -> 2.0, 3 -> 4.0, 5 -> 6.2))  // 6.2x^5 + 4.0x^3 + 2.0x^1
  val p2 = new Poly(Map(0 -> 3.0, 3 -> 7.0))  // 7.0x^3 + 3.0x^0
  p1 + p2
}

##Map Default Values

So far our maps were partial functions, meaning that when we apply a map to a key value, this could lead to an exception if the key was not found.

What we could do is use the operation withDefaultValue that turns a map into a total function.

val cap1 = capitalOfCountry withDefaultValue "<unknown>"
cap1("Andorra")  // "<unknown>"

#Week 6 (Lesson 5) - Large Example

Phone keys that translate(phoneNumber), e.g. translate(7225247386) should have the mnemonics returned as Scala is fun.

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

Code Solution:

package week6

import scala.io.Source

object x {
    val in = Source.fromURL("http://lamp.epfl.ch/files/content/sites/lamp/files/teaching/progfun/linuxwords")
    val words = in.getLines.toList filter(word => word forall (chr => chr.isLetter))

    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; ltr <- str) yield ltr -> digit
      // charCode: Map[Char, Char] = Map(E -> 3, X-> 9 ...)

    def wordCode(word: String): String =
      word.toUpperCase map charCode

    wordCode("Java")  // wordCode: (word: String) String

    // group lists of words that have the same code
    def wordsForNum: Map[String, Seq[String]] = {
      words groupBy wordCode withDefaultValue Seq()
    }
    
    def encode(number: String): Set[List[String]] = 
      if (number.isEmpty) Set(List())
      else {
        for {
          split <- 1 to number.length
          word <- wordsForNum(number take split)
          rest <- encode(number drop split)
        } yield word :: rest  
      }.toSet  // encode: (number: String)Set[List[String]]

    encode("7225247386")  // res0: Setp[List[String]] = Set(List(Scala, is, fun)...)

    // takes encode makes phrases by adding spaces
    def translate(number: String): Set[String] =
      encode(number) map (_ mkString " ")
    translate("7225247386")  // Set[String] = Set(Scala is Fun ...)
}

William Liu

github.com/williamqliu