Learning Scala

learningScala.md

SBT

> sbt
> console
> import packageName._ // imports a package from the working directory

https://docs.scala-lang.org/tour/tour-of-scala.html

Basics

printing:

println(1) // 1
println(1 + 1) // 2
println("Hello!") // Hello!
println("Hello," + " world!") // Hello, world!

immutable value

val x = 1 + 1 // infered
println(x) // 2
val x: Int = 1 + 1 // explicit

mutable assigned value

var x = 1 + 1
x = 3 // This compiles because "x" is declared with the "var" keyword.
println(x * x) // 9

Blocks

You can combine expressions by surrounding them with {}. We call this a block.

The result of the last expression in the block is the result of the overall block, too.

println({
  val x = 1 + 1
  x + 1
}) //

Functions

Functions are expressions that take parameters.

You can define an anonymous function (i.e. no name) that returns a given integer plus one:

(x: Int) => x + 1

On the left of => is a list of parameters. On the right is an expression involving the parameters.

You can also name functions.

val addOne = (x: Int) => x + 1
println(addOne(1)) // 2

Functions may take multiple parameters.

val add = (x: Int, y: Int) => x + y
println(add(1, 2)) // 3

Or it can take no parameters.

val getTheAnswer = () => 42
println(getTheAnswer()) // 42

Methods

Methods look and behave very similar to functions, but there are a few key differences between them.

Methods are defined with the def keyword. def is followed by a name, parameter lists, a return type, and a body.

def add(x: Int, y: Int): Int = x + y
println(add(1, 2)) // 3

Notice how the return type is declared after the parameter list and a colon : Int.

Methods can take multiple parameter lists.

def addThenMultiply(x: Int, y: Int)(multiplier: Int): Int = (x + y) * multiplier
println(addThenMultiply(1, 2)(3)) // 9

Or no parameter lists at all.

def name: String = System.getProperty("name")
println("Hello, " + name + "!")

There are some other differences, but for now, you can think of them as something similar to functions.

Methods can have multi-line expressions as well.

def getSquareString(input: Double): String = {
  val square = input * input
  square.toString
}

The last expression in the body is the method’s return value. (Scala does have a return keyword, but it’s rarely used.)

Classes

You can define classes with the class keyword followed by its name and constructor parameters.

class Greeter(prefix: String, suffix: String) {
  def greet(name: String): Unit =
    println(prefix + name + suffix)
}

The return type of the method greet is Unit, which says there’s nothing meaningful to return. It’s used similarly to void in Java and C. (A difference is that because every Scala expression must have some value, there is actually a singleton value of type Unit, written (). It carries no information.)

You can make an instance of a class with the new keyword.

val greeter = new Greeter("Hello, ", "!")
greeter.greet("Scala developer") // Hello, Scala developer!

Case Classes (similar to enum in swift)

Scala has a special type of class called a “case” class. By default, case classes are immutable and compared by value. You can define case classes with the case class keywords.

case class Point(x: Int, y: Int)

You can instantiate case classes without new keyword.

val point = Point(1, 2)
val anotherPoint = Point(1, 2)
val yetAnotherPoint = Point(2, 2)

And they are compared by value.

if (point == anotherPoint) {
  println(point + " and " + anotherPoint + " are the same.")
} else {
  println(point + " and " + anotherPoint + " are different.")
}
// Point(1,2) and Point(1,2) are the same.

if (point == yetAnotherPoint) {
  println(point + " and " + yetAnotherPoint + " are the same.")
} else {
  println(point + " and " + yetAnotherPoint + " are different.")
}
// Point(1,2) and Point(2,2) are different.

Objects (like singletons)

Objects are single instances of their own definitions. You can think of them as singletons of their own classes.

You can define objects with the object keyword.

object IdFactory {
  private var counter = 0
  def create(): Int = {
    counter += 1
    counter
  }
}

You can access an object by referring to its name.

val newId: Int = IdFactory.create()
println(newId) // 1
val newerId: Int = IdFactory.create()
println(newerId) // 2

Traits (like protocol in swift or objective-c)

Traits are types containing certain fields and methods. Multiple traits can be combined.

You can define traits with trait keyword.

trait Greeter {
  def greet(name: String): Unit
}

Traits can also have default implementations.

trait Greeter {
  def greet(name: String): Unit =
    println("Hello, " + name + "!")
}

You can extend traits with the extends keyword and override an implementation with the override keyword.

class DefaultGreeter extends Greeter

class CustomizableGreeter(prefix: String, postfix: String) extends Greeter {
  override def greet(name: String): Unit = {
    println(prefix + name + postfix)
  }
}

val greeter = new DefaultGreeter()
greeter.greet("Scala developer") // Hello, Scala developer!

val customGreeter = new CustomizableGreeter("How are you, ", "?")
customGreeter.greet("Scala developer") // How are you, Scala developer?

Here, DefaultGreeter extends only a single trait, but it could extend multiple traits.

Main Method

The main method is an entry point of a program. The Java Virtual Machine requires a main method to be named main and take one argument, an array of strings.

Using an object, you can define a main method as follows:

object Main {
  def main(args: Array[String]): Unit =
    println("Hello, Scala developer!")
}

singletons

Singletons are created by using the object keyword Methods and values that aren’t associated with individual instances of a class belong in singleton objects, denoted by using the keyword object instead of class

package test

object Blah {
  def sum(l: List[Int]): Int = l.sum
}

Companions (AKA "category" , "extension")

Like a category in Objective-C or an extension in Swift

class IntPair(val x: Int, val y: Int)
// this is the "Category" on the class
object IntPair {
  import math.Ordering

  implicit def ipord: Ordering[IntPair] =
    Ordering.by(ip => (ip.x, ip.y))
}

Functional

Call by value -> The operands are evaluated before the function is called Call by name -> The operands are evaluated when they are used

Scala normally uses call by value But if the type of a function starts with => is uses call by name

Example:

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

def loop : Int = loop

constOne(1,loop) // will complete
constOne(loop,1) // will infinite recurse

A defination
def loop : Bool = loop
A defination
def x = lopp
val x = loop // BOOM!

Coursera

Higher order functions

Functions are first class types. Functions can take functions as parameters and can return functions as return values

Examples:

assume we want to define a sum function in the form of SUM(function,a,b) === Sigma(function(x)) |   a <= x  <= b & a,b INTS

def sum(f: Int => Int, a : Int, b: Int): Int = 
  if (a > b) 0
  else f(a) + sum(f,a,b)
  
define transformaing functions:
  def id(x : Int) = x
  def cube(x : Int) = x * x * x
  def fact(x : Int): Int = if (x == 0) 1 else x*fact(x-1)
  
define accumulating functions:
  def sumInts(a: Int, b: Int) = sum(id,a,b)
  def sumCubes(a : Int, b: Int) = sum(cube,a,b)
  def sumFact(a: Int, b: Int) = sum(fact,a,b)
  

Function type

The type A => B is the type of a function that takes an argument of type A and returns an argument of type B

So, Int => Int is the type of functions that map integers to integers

Anonymous functions syntax

No need to give a name to a function

(x : Int) => x*x*x // raises x to a cube

The type of the parameter can be ommited if it can be inferred by the compiler from the context

If there are several parameters they are seperated by commas.

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

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

Currying

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 // the return value
}


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

In the previous example we can avoid the sumInts, sumCubes ,... middlemen

sum(cube)(1,10)

Generally, function application associates to the left:

sum(cube)(1,10) === (sum(cube)) (1,10)

The definition of functions that return functions is so useful in functional programming that in Scala there is a special syntax for it

For example, the folliwng deination of sum is equivalent to the one with the nested sumF function, but shorter:

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 (sugar)

In general, a defination of a function with multiple parameter lists:

Defined: def f(args1)(args2)....(argsn) = E

where n > 1 is equivalent to:

def f(args1)...(argsn-1) = {def g(argsn) = E ; g}

where g is a fresh identifier, Or for short:

def f(args1)...(argsn-1) = (argsn => E)

By repeating the process n times:

def f(args₁)

Abstract classes

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

Abstract classes can contain members which are missing an implementation

You can't create an instance of an abstract class

To implement the abstact class

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 = "."
}

class NonEmpty(elem : Int, left : IntSet, right : Intset) extends IntSet {
  def contains(x :Int) : Boolean = {
    if (x < elem) left contains x // this means that "elem" is this.elem and using infix notation on the caller
    if (x > elem) right contains x // like saying if (x > this.elem) return 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 + "}"
}

IntSet is called the superclass of Empty and NonEmpty

Empty and NonEmpty are subclasses of IntSet

It is also possible to redefine an existing non-abstract definition in a subclass by using the override keyword

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

class Sub extends Base {
  override def foo = 2 // because there is a concrete definition in the super class you need to use the override keyword
  def bar = 3 // don't need override since it isn't implemented in the base class
}

// adding "union"
abstract class IntSet {
  def union(other : IntSet) : IntSet
}

object Empty extends IntSet {
  def union(other : IntSet) = other
}

class NonEmpty(elem : Int, left : IntSet, right : IntSet) extends IntSet {
  def union(other : IntSet) : IntSet = 
    (((left union right) union other) incl elem) // this.left.union(this.right).union(other).incl(this.elem)
}

Packages

Class and objects are organized in packages

TO place a class or object inside a package use a package clause at the top of your source file

package progfun.examples

object Hello {...}

This would place Hello in the package of profgun.examples

You can ther refer to Hello by its fully qualified name

progfun.examples.Hello. For instance to run this Hello program:

> scala progfun.examples.Hello

you can import a package

import package_nme.thing_to_use

or you can import everything in the package using the _ keyword

import week3._

Imports come in several forms:

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

The first two forms are called named imports The last form is called a wildcard import You can import for either a package or an object

Automatic imports

Some entities are automatically imported in any Scala program.

These are:

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

Here are the fully qualiifed names of some types and functions which you have seens so far:

Int	scala.Int
Boolean	scala.Boolean
Object	java.lang.Object
require	scala.Predef.require
assert	scala.Predef.assert

Scala standard library www.scala-lang.org/api/current

Traits

In java as well as in scala a class can only have one superclass

But what if a class has several natural supertypes to which it conforms or from which it wants to injherit code?

Here you could use traits.

A trait is declared like an abstract class just with a trait instead of abstract class

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

Classes , objects and traits can inherit from at most one class but arbitrary many traits.

Example (notice the use of the "with" keyword) :

class Square extends Shape with Planar with Movable

Traits resemble interfaces in Java but are more powerful because they can contains fields and concrete methods.

On the other hand, traits cannot have (value) parameters. Only classes can

Top types

Type	Description
Any	the base type fo all types ; methods : '==' ,'!='
AnyRef	The base type of all reference types: Alias of 'java.lang.Object;
AnyVal	The base type of all primitive types

The Nothing Type

Nothing is at the bottom of scalas type hierarchy. It is a subtype of every other type.

There is no value of type Nothing.

Why is that useful?

• To signal abnormal termination
• As an element type of empty collections

Exeption

Scala's exception handling is similar to Java's.

The expression:

throw Exc aborts evalutation with the exception Exc.

The type of this expression is Nothing

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

error("test")

The NUll type

Every reference class type also has a 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

In other words you can not assign "null" to a value type such as a number

val x = null // x: Null = null
val y:String = null // y: String = null
val z: Int = null // error: type mismatch! - Not object

cons lists in scala ( an immutable list)

trait IntList
class Cons(val head: Int, val tail: IntList) extends IntList ... // Notice that when using the syntax class blah(val x: Something,...) the "x" becomes a parameter of the class and a field of a class
class Nil extends IntList...

In this case a list is either:

• an empty list new Nil or
• a list new Cons(x,xs) consisting of a head element x and a tail list xs

Value parameters

Note the abbreviation (val head: Int, val tail: Intlist) in the definaition of the class

The defines at the same time parameters and fields of a class

It is equivalent to:

class Cons(_head : Int, _tail: IntList) extends IntList {
  val head = _head
  val tail = _tail
}

Type parameters

It seems too narrow to define only lists with Int elements

We'd need another class hierarchy for Double lists and so on, on for each possible element type

We can generalize the defintion using a type parameter:

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

Type parameters are written in square brackets, e.t. [T]

Generic list

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 = throw NoSuchElementException("Nil.head") // type Nothing which is a subtype of all other types
  def tail = throw NoSuchElementException("Nil.tail")
}

Generic Functions

Like classes, function can have type parameters For instance , here is a function that creates a list consiting of a single element.

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

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

Type inference In fact the scala compiler can usually defuce the correct type parameters form the value arguments of a function call.

So in most cases type parameters can be left out. You could also write:

singleton(1) // type Int
singleton(true) // type Boolean

Types and evaluation

Type parameters do not affect evaluation in scala

We can assume that all type parameters and type arguments are removed before evaluating the program

This is also called type erasure

Functions as Objects

We have seen that sclalas numeric types and the boolean type can be implemented like normal classes.

But what about functions?

In fact function valies are treated as objects in Scala

The function type A => B is just an abbreviation for the class Scala.Function[A,B] which is roughly defined as follows.

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

So function are object with apply methods.

There are also traits Function2, Function3, ... for function which take more parameters (currently up to 22)

An anonymous function such as

(x : Int) => x*x

is expanded to:

{ class AnonFun extends Function1[Int,Int] {
  def apply(x: Int) = x*x
  }
  new AnonFun // it assumed AnnonFun name isn't used yet
}

or, shorter using anonymous class syntax:

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

Expanion of Function calls

A function call such as f(a,b) where f is a a value of some class type is expanded to

f.apply(a,b)

So the OO-translation of

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

would be

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

Methods themselves are not Function values (else we would have an infinite recursion on "apply")

Not that a method such as

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:

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

Lets say we wanted to have a shorthand for a function that could create a list of lengths 0, 1 , or 2

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
}

Polymorphism

Two prinicipal forms of polymorphism

• subtyping - passing an instance of a subtype when a base type was required
• generics - parameterise types with other types

Two main areas of interactions:

• bounds - subject type parameters to subtype constraints
• variance - defines how paramterised types behave under subtyping

Type bounds

Consider the method assertAllPos which

• takes an IntSet
• returns the IntSet itself if all its elements are positve
• throws an exception otherwise

What would be the best type you can give to assertAllPos? Maybe:

def assertAllPos(s: IntSet) : IntSet

In most situations this is fine but can we be more precise

One might want to express that assertAllPos takes Empty sets to Empty sets and NonEmpty sets to NonEmpty sets

A way to express this is:

(Notice the <: keyword which means "inherits from") def assertAllPos[S <: IntSet](r: S): S = ...

Here, "<: IntSet" ios an upper bound of the type parameter S:

It means that S can be instantiated only to types that conform to IntSet

Generally the notation:

• S <: T means S is a subtype of T , and
• S >: T means: S is a supertype of T, or T is a subtype of S

Mixed bounds

Finally it is possible to mix a lower bound with an upper bound:

For instance:

[S >: NonEmpty <: IntSet] would restrict S any type on the interval between NonEmpty and IntSet

Covariance

There's another interaction between subtypeing and type parameters we need to consider Given:

Nonempty <: IntSet

is

List[NonEmpty] <: List[IntSet] ?

Intuitively this makes sense. A list of non-empty sets is a special case of alist of arbitrary sets.

We call types for which this relationship holds covariant because their subtypign relationship varies with the type parameter.

Does covariance make sense for all types, not just for List? (Short answer NO - skipping explination but imagine reassigning the fist value of the array to a basetype and then move back to the original type - Everything you can do with type A you should be able to do with Type B - but the reassignment of the value fucks this relationship up)

val a: Array[NonEmpty] = Array(new NonEmpty(1,Empty,Empty))
val b: Array[IntSet] = a
b(0) = Empty
val s: NonEmpty = a(0) // BOOM - you can't do operations of NonEmpty on the 0th element because it is a Empty instead!

Advanced (Variance) (Variance (optional) 4.4

Say C[T] is a parameterised type A,B are type such that A<:B

In general there are three possible relationships between C[A] and C[B]:

C[A] <: C[B]	C is covariant
C[A] >: C[B]	C is contravariant
neither C[A] nor C[B] is a subtype of the other	C is nonvariant

Scala lets you declare the variance of a type by annotating the type parameter:

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

Function trait declaration

So functions are contravariant in their argument types and covariant in their result type

This leads to the following revised definition of the FUnction1 trait:

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

Type tests and type casts (discouraged in scala)

def isInstance[T]: Boolean // checks whether this objects type confirms to T
def asInstanceOf[T]: T // treats this object as an instance of type T 
                       // throws 'ClassCastException' if it isn't

Pattern matching

Case clases

A case class definition is similar to a normal class definition , except that it is preceeded by the modifier case. For example:

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

Like before this defines a trait Expr and two concrete subclasses Number and Sum

It also implicitly defines companion objects with apply methods

object Number {
  def apply(n: Int) = new Number(n) // this allows writing val myNum = Number(1) without the "new" keyword
}

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

so you can write Number(1) instead of new Number(1)

However these classes are now empty. So how can we access the members?

Pattern Matching

Pattern matching is a generalization of switch from c/java to class hierarchies.

It's expressed in scala using the keyword match.

Example:

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

Rules:

• match is followed by a seuence of cases pat => expr
• Each case assoiciates an expression expr with a pattern pat
• A MatchError exception is thrown if no pattern matches the value of the selector.

e match {
  case pat => expr,
  case pat2 => expr2 ...
}

Forms of patterns

Patterns are constructed from:

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

Variables always begin with a lowercase letter

The same variable name can only appear once in a pattern. So Sum(x,x) is not a legal pattern.

Names of constants begin with a capital letters with the exception of the reserved words null, true, false

What do patterns match?

• A constructor pattern C(p1,...pn) matches all the values of type C (or subtype) that have been constructed with arguments matching the patterns p1, ... pn
• A variable pattern x matches any value and binds the name of the variable to this value
• A constant pattern c matches values that are equal to c (in the sense of ==)

Data structures

Lists

The list is a fundamental data strucutre in functional programming.

A list having x₁, ... , x_n as elemenmts is writting List(x1,..,xn)

Example:

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()

There are two important differences betweeen lists and arrays

• Lists are immutable -- the elements of alist cannot be changed
• Lits are recursive, while arrays are flat

Pair and Tuples

The pair consisting of x and y is written (x,y) in Scala.

Example:

val pair = ("answer", 42) > pair: (String,Int) = (answer,42)

The type of pair above is (String,Int)

Pairs can also be used as patterns

val (label,value) = pair > label : String = answer , value : Int = 42

This works analogously for tuples with more than two elements

Higher order functions

Map

abstract class List[T] {
  def map[U](f: T => U) : List[U] = this match {
    case Nil => Nil
    case x::xs => f(x) :: cs.map(f)
  }
  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)
   }
}

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

Reduce left

reduceLeft inserts a given binary operator between adjacent elements of a list

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

Using reduceLeft we can simplify:

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

A shorter way to write functions

Instead of writing (x,y) => x*y one can also write shorter (_ * _)

Every _ represents a new parameter, going from left to right.

The parameters are defined at the next outer pair of parantheses (or the whole expression if there are no enclosing parantheses)

So sum and product can also be expressed like this:

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

Vector

a list of lists of lists ... each list has 32 elements , when it is exhausted it will create another level of 32 lists

 val nums = Vector(1,2,3,4)
 val people = Vector("Bob", "James")

They support the same operations as lists with the exception of :: Instead of x :: xs , there is:

x +: xs // create a new vector with the leading element x followed by all eleemnts of xs
xs :+ x // create a new vector with trailing elemenet x, preceded by all elements of xs

Note that the : always points to the sequence

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 +---------+
           |                    +              |
           |                    |              |
           v                    v              v
         Seq                   Set            Map
  +------+  +------+
  |                |
  v                v
List             Vector

Also Array and String can behave like Iterable

val xs = Array(1,2,3,4)
xs map (x => x *2)

val s = "hello"
s filter (c => c.isUpper)

Ranges

Another simple kind of sequence is the range. It represents a sequence of evenly spaced integers.

Three operators:

to (inclusive) , until (exclusive) , by (to determine step value)

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

Good example

To compute the scalar product of two vectors:

def scalaProduct(xs : Vector[Double], ys : Vector[Double]): Double = 
  (xs zip ys).map(xy => xy._1 * xy._2).sum // zip creates tuples (x1,y1),(x2,y2)...
                                            // xy is a tuple (xi,yi) and xy._1 , xy._2 is the decomposition of a tuple by their position

An alternative way to write this is with pattern matching function value.

def scalarProduct(xs : Vector[Double], ys: Vector[Double]) : Double = (xs zip ys).map { case (x,y) => x*y}.sum

Generally the function value, {case p1=>e1 ... case pn=>en} is equivalent to x => x match { case p1 => e1 ... case pn => en }

A prime number:

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

Vector

Vectors are implemented as very shallow trees

Up to 32 elements:

+----+----+----+----+
|    |    |    |    |
|    |    |    |    |  32
+----+----+----+----+

Larger than 32 the representation changes to 32 pointers to 32 vectors of 32 elements (here we are drawing only 4)

                                          +----+----+----+----+
                                          |    |    |    |    |
  +---------------------------------------+    |    |    |    |  32
  |                                       -----+-+--+--+-+--+-+
  |                                              |     |    |
  |                             +----------------+     |    +-------------------------+
  |                             |                      +---+                          |
  |                             |                          |                          |
+-+--+----+----+----+         +-+--+----+----+----+      +-+--+----+----+----+      +-+--+----+----+----+
|    |    |    |    |         |    |    |    |    |      |    |    |    |    |      |    |    |    |    |
|    |    |    |    |         |    |    |    |    |      |    |    |    |    |      |    |    |    |    |
-----+----+----+----+         -----+----+----+----+      -----+----+----+----+      -----+----+----+----+

After 32*32 elements we add another level to get a pointer to a pointer to 32 elements (323232) elements (232) elements

so we get a maximum depth of ~10 (3210) elements)

Operations on vectors

Vectors are craeeted analogously to lists:

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

They support the same operations as lists, with the exception of ::

Instead of x :: xs there is:

x +: xs	Create a new vector with leading element x, followed by all elements of xs
xs :+ x	Create a new vector with trailing element x, preceeded by all elements of xs

(Note that the : always points to the sequence.)

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 pairs |
+---------------+----------------------------------------------------------------------------------------------------------------+
| xs.flatMap f  |  Applies collection-valued function f to all elements of xs and concatenates the result                        |
+---------------+----------------------------------------------------------------------------------------------------------------+
| xs.sum        |  The sum of all elements of this numeric collection                                                            |
+---------------+----------------------------------------------------------------------------------------------------------------+
| xs.product    |  The product of all elements of this numeric collection (an Ordering must exist)                               |
+---------------+----------------------------------------------------------------------------------------------------------------+
| xs.min        |  The minimum of all elements of this collection                                                                |
+---------------+----------------------------------------------------------------------------------------------------------------+

Example: Combinations

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)))

Scalar product of two vectors

\[\sum_{i=1}^{n}x_{i}*y_{i}\]

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

Handling nested sequences

We can extend the usage of higher order functions on sequences to many calcualtions which are usually expressed using nested loops.

Example: 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 |
+------+-----------------+

Algorithm

A natural way to do this is to:

• Generate the sequence of all pairs of integers (i,j) such that i <= j < i < n
• Filter the pairs for which i + j is prime

One natural way to generate the sequence of pairs is to:

• Generate all the integers i between 1 and n (excluded).
• For each integer i, generate the list of pairs (i,1)...(i,i-1)

This can be achieved by combining until and map:

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

Generate pairs

The previous step gave a sequence of sequences, lets call it xss.

We can combine all the sub-sequences using foldRight with ++"

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

Or equivalently we use the built-in method flatten

xss.flatten

This gives:

(1 until n) map ( i =>
  (1 until i) map (j => (i,j))).flatten

                 ++
             XXX    XXXX
          XXXX          XXXXXXX
        XXX                   XX
+--+--+---+--+                    ++
|  |  |   |  |                   X   XX
+--+--+---+--+                 XX     XXXX
                             XXX          XXX
                             X               XXXX
                 +--+--+---+--+                 XX
                 |  |  |   |  |                     ++
                 +--+--+---+--+                 XXX   X
                                                X     XX
                                  +--+--+---+--+       XX
                                  |  |  |   |  |        XXX
                                  +--+--+---+--+          XXX
                                                            XX
                                                   +--+--+---+--+
                                                   |  |  |   |  |
                                                   +--+--+---+--+

Here's a useful law:

cs flatmap f = (xs map f).flatten

Flatmap is mapping f and then flattening the collections

Hence the above expression can be simplified to

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

and to filter the primes:

(1 until n) flatmap ( i => (1 until i) map (i,j))).filter( pair => isPrime(pair._1 + pair._2))

For expressions

Higher order functions such as map flatMap or filter provide powerful constructs for manipulating lists.

But sometimes the level of abstraction required by these function make the program difficult to understand.

In this case Scala's for expression notation can help.

For-Expression Example

Let persons be a list of class Person, with fields name and age.

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

To obtain the names of persons over 20 years old you can write:

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

which is equivalent to:

persons filter (p=> p.age > 20) map (p => p.name)

The for-expression is similar to loops in imperative languages except that it builds a list of the results of all iterations.

Syntax of For

A for-expression is of the form:

for (s) yield e

where s is a sequence of generators and filters and e is an expression whose value is returned by an iteration.

• A generator is of the form p <- e, where p is a pattern and e an expression whose value is a collection
• A filter is of the form if f where f is a boolean expression.
• The sequence must start with a generator.
• If there are several generators in the sequence , the last generators vary faster than the first

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

Use of For

Here are two examples which were previously solved with higher-order functions:

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

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

Sets

Sets are another basic abstraction in the scala collections.

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)
fruit filter (_.startsWith == "app")
s.nonEmpty

Sets vs Sequences

The principle differences between sets and sequences are:

1. Sets are unordered. The elements of a set do not have a predefined order in which they appear in the set
2. Sets do not have duplicate elements
3. The fundamental operation on sets is contains: s contains 5 // true

Example: N-Queens

The eigtht queens problem is to place eight queens on a chessboard so that no queen is threatened by another.

• In other words , there can't be two queens in the same row, column, or diagonal

We now develop a solution for a chessboard of any size, not just 8.

One way to solve the problem is to place a queen on each row.

Once we placeced k-1 queens one must place the kth queen in a column where it's not 'in check' with any other queen on the board.

Algorithm

We can solve this problem with a recursive algorithm:

• Suppose that we have already generated all the solutions consiting of placing k-1 queens on a board of size n.
• Each solution is represented by a list (of lenght k-1) containing the numbers of columns (between 0 and n-1)
• The column number of the queen in the k-1th row comes first in the list followed by the column number of the queen in row k-2 etc.
• The solution set is thus represented as a set of lists with one elemenet for each solution.
• Now to place the kth queen we generate all possible extensions of each solution preceeded by a new queen

def queens(n : Int) : Set[List[Int]] = {
  def placeQueens(k : Int) : Set[List[Int]] = {
    if (k == 0) Set(List())
    else
      for {
        queens <- placeQueens(k-1)
        col <- 0 until n
        if isSafe(col,queens)
      } yield col :: queens
    placeQueens(n)
    }
  }
  def isSafe(col : Int, queens : List[Int]) : Boolean = {
    val row = queens.length
    val queensWithRow = (row -1 to 0 by -1) zip queens
    queensForRow forall {
      case (r,c) => col != c && math.abs(col -c) != row -r // checking diagonals
    }
  }

Queries with for

The for notation is essentially equeivalant to the common operations of query languages for databases

Example suppose that we have a database books represented as a a list of books.

case class Book(title: String, authors : List[String])

Some queries

To find the titles of books whose authors name is Bird:

for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title

To find all the books which have the word "Program" in the title:

for(b <- books if b.title indexOf "Program" >= 0) yield b.title

To find the names of all authors who have written at least two books present in the database.

{ for {
  b1 <- books
  b2 <- books
  if b1 != b2 // b1.title < b2.title so we don't get the pair twice "swapped" in the order
  a1 <- b1.authors
  a2 <- b2.autors
  if a1 == a2
} yield a1 } .distinct

Generalization of for

Interestingly , the translation of thfor is not limited to lists or sequences or even collections.

It is based solely on the presence of the methods map, flatmap and withFilter

This lets you use the for syntax for your own types as well - you must only define map, flatmap and withFilter for these types.

There are many types for which this is useful: arrays, iterators, databases, XML data, optional values, parsers etc.

For and Databases

For example, books might not be a list, but a database stored on some server.

As long as the client interface to the database defines the methods map, flatMap, and withFilter , we can use the for syntax for querying the database.

This sithe basis of the Scala data base connection frameworks ScalaQuery and Slick.

Similar ideas underly Microsoft's LINQ

Map

Another fundamental colleciton type is the map.

A map of type Map[Key,Value] is a data strucutre that associates keys of type key with values of type Value.

Examples:

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

Maps are functions

Class Map[Key,Value] also extends the function type Key => Value, so maps can be used everywhere that functions can.

In particular, maps can be applied to key arguments:

capitalOfCountry("US") // Washington

but if the item doesn't exist we get an exception (because the function doesn't "exist")

So we can use the get function

capitalOfCountry get "andorra" // Option None

The 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

• None if map does not contain the given key
• Some(x) if map associates the given key with the value x

Decomposing Option

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

def showCapital(country : String) = capitalOfCOutnry.get(country) match {
  case Some(capital) => capital
  case None => "Missing data"
}
showCapital("US")
showCapital("Andorra")

Options also support quite a few operations of the other collections.

Sorted and GroupBy

Two useful operation of SQL queries in addition to for-expressions are groupBy and orederBy

orderBy on a collection can be expressed by sortWith and sorted

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

groupBy is available on Scala collections. It partitions a collection into a map of collections according to a discrimantor function f.

Example

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

Example polynomials defined as map of power to value of cooefficant

class Poly(val terms : Map[Int,Double]) {
  def + (other: Poly) = {
    def adjust(input : (Int,Double)) : (Int,Double) = {
      val (exp,coeff) = input
      terms get exp match {
        case Some(coeff1) => exp -> (coeff + coeff1)
        case None => exp -> coeff
      }
    }
    
    new Poly(terms ++ (other.terms map adjust))
    
  }
}

val p1 = new Poly(Map(1 -> 2.0, 3 -> 4.0, 5 -> 6.2)
val p2 = new Poly(Map(0 -> 3.0, 3 -> 7.0)
p1 + p2

Default values

So far, maps were partial functions. Applying a map to a key valu in map(key) could lead to an exception, if the key was not stored in the map.

There is an operation withDefaultValue that turns a map into a total function:

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

Impovement for solution 1 with default values:

class Poly(terms0 : Map[Int,Double]) {
  def this(bindings: (Int,Double)*) = this(bindings.toMap) // * repeated parameters
  val terms = terms0 withDefaultValue 0.0
  def + (other: Poly) = new Poly(terms ++ (other.terms map adjust))
  def adjust(term : (Int, Double)) : (Int,Double) = {
    val (exp,coeff) = term
    exp -> (coeff + terms(exp))
  }
}

Delayed evaluation

Avoid computing the tail of a sequence until it is needed for the evaluation result (which might be never AKA "Break")

This idea is implemented in a new class, the Stream

Streams are similar to lists but their tail is evaluated only on demand.

Defining streams

Streams are defined from a constant Stream.empty and a constructor Stream.cons

For instance:

val xs = Stream.cons(1,Stream.cons(2,Stream.empty))

They can also be defined like the other collecitons by using the object Stream as a factory Stream(1,2,3)

The toStream method on a collection will turn the collection into a stream:

(1 to 1000).toStream > res0: Stream[Int] = Stream(1,?)

Stream ranges

Let's try to write a function that returns (lo until hi).toStream directly

def streamRange(lo : Int, hi : Int) : Stream[Int] = 
  if (lo >= hi) Stream.empty
  else Stream.cons(lo,streamRange(lo+1,hi))

Methods on Streams

Stream supports almost all methods of List:

For instance, to find the second prime number between 1000 and 10000

((1000 to 10000).toStream filter isPrime)(1)

Stream Cons Operator

The one major exception is ::.

x :: xs always produces a list, never a stream.

There is however an alternative operator #:: which produces a stream.

x #:: xs == Stream.cons(x,xs)

#:: can be used in expressions as well as patterns

// all natural numbers 
def from(n: Int): Stream[Int] = n #:: from(n+1)

val nats = from(0)

val m4s = nats map (_ * 4) // all natural numbers by 4

(m4s take 1000).toList // all naturals taking 1000

// generate prime numbers using sieve
def sieve(s : Stream[Int]) : Stream[Int] = 
  s.head #:: sieve(s.tail filter (_ % s.head != 0))

Back to square roots

Our previous algorithm for square roots always used a isGoodEnough test to tell when to terminate the iteration.

With streams we can now express the concept of converging seqence without having to worry about when to terminate it:

def sqrtStream(x: Double): Stream[Double] = {
  def improve(guess: Double) = (guess + x/ guess) / 2
  lazy val guesses: Stream[Double] = 1 #:: (guesses map improve)
  guesses
}