> sbt
> console
> import packageName._ // imports a package from the working directory
https://docs.scala-lang.org/tour/tour-of-scala.html
printing:
println(1) // 1
println(1 + 1) // 2
println("Hello!") // Hello!
println("Hello," + " world!") // Hello, world!val x = 1 + 1 // infered
println(x) // 2
val x: Int = 1 + 1 // explicitvar x = 1 + 1
x = 3 // This compiles because "x" is declared with the "var" keyword.
println(x * x) // 9You 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 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 + 1On 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)) // 2Functions may take multiple parameters.
val add = (x: Int, y: Int) => x + y
println(add(1, 2)) // 3Or it can take no parameters.
val getTheAnswer = () => 42
println(getTheAnswer()) // 42Methods 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)) // 3Notice 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)) // 9Or 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.)
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!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 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) // 2Traits 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.
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 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
}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))
}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!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)
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
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)
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)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(args1)
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)
}
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 week3The 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
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
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 MovableTraits 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
| 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 |
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
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")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
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
}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]
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")
}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 BooleanType 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
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
}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
}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
Consider the method assertAllPos which
- takes an
IntSet - returns the
IntSetitself 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 <: TmeansSis a subtype ofT, andS >: Tmeans:Sis a supertype ofT, orTis a subtype ofS
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
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!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
}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'tA 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 ExprLike 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 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:
matchis followed by a seuence of casespat => expr- Each case assoiciates an expression
exprwith a patternpat - A
MatchErrorexception is thrown if no pattern matches the value of the selector.
e match {
case pat => expr,
case pat2 => expr2 ...
}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 typeC(or subtype) that have been constructed with arguments matching the patternsp1, ... pn - A variable pattern
xmatches any value and binds the name of the variable to this value - A constant pattern
cmatches values that are equal toc(in the sense of==)
The list is a fundamental data strucutre in functional programming.
A list having x1, ... , xn 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
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
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) 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)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 (_ * _)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 xsNote that the : always points to the sequence
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)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 -2To 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 positionAn 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}.sumGenerally 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)
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)
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.)
+---------------+----------------------------------------------------------------------------------------------------------------+
| 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 |
+---------------+----------------------------------------------------------------------------------------------------------------+
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).sumWe 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 |
+------+-----------------+
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)))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))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.
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.namewhich 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.
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, wherepis a pattern andean expression whose value is a collection - A filter is of the form
if fwherefis 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).sumSets 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).toSetMost operations on sequences are also available on sets:
s map (_ + 2)
fruit filter (_.startsWith == "app")
s.nonEmptyThe principle differences between sets and sequences are:
- Sets are unordered. The elements of a set do not have a predefined order in which they appear in the set
- Sets do not have duplicate elements
- The fundamental operation on sets is contains:
s contains 5 // true
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.
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
}
}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])
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 } .distinctInterestingly , 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 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
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")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 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
Noneif map does not contain the given keySome(x)if map associates the given key with the value x
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.
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.sortedgroupBy 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
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))
}
}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.
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,?)
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))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)
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))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
}