Skip to content

Instantly share code, notes, and snippets.

@edwardbeckett

edwardbeckett/progfun04

Forked from nicokosi/progfun04
Created October 30, 2016 21:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save edwardbeckett/95e28ad2c339a7e498db07d1f2e3e9da to your computer and use it in GitHub Desktop.
Save edwardbeckett/95e28ad2c339a7e498db07d1f2e3e9da to your computer and use it in GitHub Desktop.
Download ZIP
My notes from Coursera course "Functional Programming Principles in Scala" (https://class.coursera.org/progfun-004).
Raw
progfun04
Notes from Coursera course 'Functional Programming Principles in Scala":
https://class.coursera.org/progfun-004
✔ Week 1: Functions & Evaluations @done (14-05-01 17:20)
✔ Lecture 1.1 - Programming Paradigms (14:32) @done (14-04-27 17:54)
3 paradigms: imperative, functional, logic
OO: orthogonal
imperative:
mutable variables + if/loops
Von Neuman style, match hardware but low level
functional:
avoid mutations and loops
functions are fist-class citizens
strict FP languages: Pure Lisp, Haskell (without I/O Monad, UnsafePerformIO), etc...
non-strict FP languages: Lisp, Clojure, SML, OCaml, F#, Haskell (full language), Scala
Why FP:
simple reasoning principles
modularity
multi-core
Additional resources:
FP : SICP
Scala: Scala for the impatient (free download)
video: "Working hard to keep it simple"
✔ Lecture 1.2 - Elements of Programming (14:25) @done (14-04-27 19:53)
REPL:
"scala" or "sbt console"
primitives:
Int, Double, Boolean, etc...
abstractions:
"def"
def pi = 3.14
def square (x: Double) = x * x
evaluation of function applications:
substitution model: cf. lambda-calculus (Alonso Church), OK if no side effect
call-by-value:
1. evaluate args, 2. substitute function definition with args, 3. evaluate (precedence rule)
advantage: args evaluated once
call-by-name:
substitute function first
advantage: arguments are only evaluated if needed
✔ Lecture 1.3 - Evaluation Strategies and Termination (4:22) @done (14-04-28 13:08)
for a given expression, if call-by-value evaluation terminates, then call-by-name also terminates (the reverse is not true)
Scala uses call-by-value by default
call-by-name can be used with "=>"
example:
def constOne(x: Int, y: => Int) = 1p
✔ Lecture 1.4 - Conditionals and Value Definitions (8:49) @done (14-04-28 13:25)
if/else:
with predicates (and not statements)
&& and || use "short-circuit": right operand may not be evaluated
def/value evaluation:
def is called-by-name, val is called-by-value
def loop: Boolean = loop
// OK in REPL:
def x = loop
// infinite loop in REPL:
val x = loop
✔ Lecture 1.5 - Example: square roots with Newton's method (11:25) @done (14-04-29 13:26)
method:
1. start with init estimate y = 1
2. repeatedly improve estimate: y = mean (y, x/y)
// Scala code, recursive implem:
def abs(x: Double) = if (x < 0) -x else x
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) < 0.001
def improve(guess: Double, x: Double) =
(guess + x / guess) / 2
def sqrt(x: Double) = sqrtIter(1.0, x)
N.B.: Scala recursive functions need an explicit return type
For non-recursive functions, type is optional
✔ Lecture 1.6 - Blocks and Lexical Scope (8:00) @done (14-04-29 19:13)
goal: make code modular and easy to use
1. use nested functions to provide namespace pollution
block: code delimited by { ... }
definitions inside block:
are only visibly wihin block
can shadow defintions that exist outside
2. remove parameters duplicated in nested functions
✔ Lecture 1.7 - Tail Recursion (12:32) @done (14-04-29 19:36)
classical recursive algorithms:
- greater common divisor via Euclid's algo
- factorial
tail recursive functions reuse function stack frame directly
gcd is tail recursive, factorial is not
tail recursion acts as a loop
Generally, if last function action is calling a function, it is tail recursive
In Scala, @tailrec annotation is used to check that a function is tail recursive (otherwise, compilation would fail)
exercise: tail recursive factorial
☐ Week 2: Higher Order Functions
✔ Lecture 2.1 - Higher-Order Functions (10:18) @done (14-05-04 20:31)
Higher-Order Functions:
For FP languages, functions are treated as first-class values
higher-ordered function: which is passed as other function's argument or returned from another function
motivation: a way to compose programs
example:
def sumInts(a: Int, b: Int): Int =
if (a > b) 0 else a + sumInts(a + 1, b)
def sumCubes(a: Int, b: Int): Int =
if (a > b) 0 else cube(a) + sumInts(cube(a + 1, b)
// let's factorize common code via HOF (equilavent to math. expression "sigma(f(n)) with n = [a, b]"):
def sum(f: Int => Int, a: Int, b: Int) =
if (a > b) 0 else f(a) + sum(f, a + 1, b)
def sumInts(a: Int, b: Int): Int = sum(id, a, b)
def sumCubes(a: Int, b: Int): Int = sum(cube, a, b)
def sumFactorials(a: Int, b: Int): Int = sum(fact, a, b)
"A => B" is the type of a function that takes argument of type A and returns an argument of type B
Anonymous functions:
Sometimes it's tedious to name short functions
=> use anonymous functions
// anonymous function that takes an integer and returns its cube, as an integer:
(i: Int) => i * i *
// returned type can be omitted if it can be infered:
i => i * i * i
// anonymous function with 2 params:
(Int: a, Int: a) => a + b
// or
a, b => a + b
Any anonymous function is equivalent to:
def f(a: A, b: B) =
// body ; f(a, b)
So they are "syntactic sugar" (i.e. they're not essential)
Our example, revisited with anonymous functions:
sum(i => i)(1, 3)
sum(i => i*i*i)(1, 3)
✔ Lecture 2.2 - Currying (14:58) @done (14-05-05 13:34)
A curried function is a function that returns (nested) functions. All functions have 1 arg.
motivation:
factorize repetition
example:
// a lot of repetition there:
def sumInts(a: Int, b: Int): Int = sum(id, a, b)
def sumCubes(a: Int, b: Int): Int = sum(cube, a, b)
def sumFactorials(a: Int, b: Int): Int = sum(fact, a, b)
// ...can be curried to:
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
}
def sumInts2 = sum(x => x)
def sumCubes2 = sum(x => x*x*x)
sumCubes2(1, 10) + sumInts(10, 20)
// or use curried function directly:
sum(cube)(1, 10)
// Special (shortest) synthax for currying:
def sum(f: Int => Int)(a: Int, b: Int): Int = {
if (a > b) 0 else f(a) + sum(f)(a + 1, b)
}
Any function f(a, b, c, ...) can be curried to f(a)(b)(c)(...)
Function types:
// What's the type of this function?:
def sum(f: Int => Int)(a: Int, b: Int): Int = ...
// answer:
(Int => Int) => (Int, Int) => Int
Exercise:
// A function which generalizes both sum and product:
def mapReduce(f: Int => Int, combine: (Int, Int) => Int, init: Int) (a: Int, b: Int): Int =
if (a > b) init
else combine(f(a), mapReduce(f, combine, init)(a + 1, b))
def product(f: Int => Int)(a: Int, b: Int): Int = mapReduce(f, (a, b) => a * b, 1)(a, b)
product(x => x*x)(3, 4)
✔ Lecture 2.3 - Example: Finding Fixed Points (10:46) @done (14-05-06 08:53)
fixed point of a function:
number x is a fixed point of a function f if f(x) = x
Often found starting with initial estimate and applying f repeatedly until "stable": x, f(x), f(f(x)), etc...
example - computation of square root via fixed point:
specification: sqrt(x) = the number y such that y * y = x
or: sqrt(x) = the number y such that y = x / y
consequently, sqrt(x) is a fixed point of the function (y => x / y)
But implementing it directly does not work, it does not converge
def sqrt(x: Double) = fixedPoint(y => x / y)(1.0) // fails
solution is averaging successive values (prevent estimations from varying too much)
def sqrt(x: Double) = fixedPoint(y => (y + x / y) / 2)(1.0)
// or better
def sqrt(x: Double) = fixedPoint(averageDamp(y => x / y))(1)
Conclusion:
know how to reuse code via abstraction (higher-ordered functions)
but do not always use the highest level of abstraction!
✔ Lecture 2.4 - Scala Syntax Summary (4:13) @done (14-05-06 09:13)
context-free syntax (Extended Backus-Naur form):
| : alternative
[...] : option (0 or 1)
{...} : repetition (0 or more)
types:
numeric type: [Int Double Byte Short Char Long]
Boolean with values true and false
String
function type
(+ some others, see later)
expressions:
identifier (i.e. "isGoodEnough")
literal (i.e 2, "abc")
function application (i.e. "sqrt(x)")
operator application (i.e. "-x")
selection (i.e. "math.abs")
conditional (i.e. "if (x > 2)"")
block (i.e. "{ val foo = 2 }")
anonymous function (i.e. "x => x +1")
definitions:
value definition, like "val y = sqrt(2)"
function definition, like "def cube(x: Int) = x * x
call-by-value function parameter, like "(x: Int)"
call-by-name function parameter, like "(y: => Int)"
✔ Lecture 2.5 - Functions and Data (11:50) @done (14-05-06 13:11)
goal:
create and encapsulate data structures in a class
class: type with name + constructor in a namespace
object: class instanciation
members: are accessed with infix operator '.'
methods: functions packages inside class
example:
object rationals {
val x = new Rational(1, 2) //> x : week2.Rational = 1/2
val y = new Rational(5, 7) //> y : week2.Rational = 5/7
val z = new Rational(3, 2) //> z : week2.Rational = 3/2
x.numer //> res0: Int = 1
x.add(y) //> res1: week2.Rational = 17/14
x.neg //> res2: week2.Rational = -1/2
x.sub(y) //> res3: week2.Rational = -3/14
}
class Rational(x: Int, y: Int) {
def numer = x
def denom = y
def add(that: Rational) =
new Rational(
numer * that.denom + that.numer * denom,
denom * that.denom)
def neg() = {
new Rational(-numer, denom)
}
def sub(that: Rational) =
add(that.neg) // DRY
override def toString = numer + "/" + denom
}
✔ Lecture 2.6 - More Fun With Rationals (15:08) @done (14-05-06 19:37)
goal:
show data abstraction
data abstraction:
= separate API (public methods and values) from private definitions
self-reference:
Use 'this' to refer to current instance)
requirement:
via "require" predefined function which can throw IllegalArgumentException
used for preconditions on a function (constructor, method or function), on caller side
assertion:
via "assert" predefined function, throws AssertionError
used to check the code
constructors:
primary constructor: take class params + execute class body
secondary constructor are "this" definitions, i.e. "def this(x: Int) = this(x, 42)"
✔ Lecture 2.7 - Evaluation and Operators (16:25) @done (14-05-06 21:08)
classes and substitution model:
class instanciations are function are evaluated like normal functions
// given:
class(x1) { def f(y1) = b }
// how is this evaluated?:
new Class(v1).f(w1)
3 substitutions:
- substitution of params of class
- substitution of params of function 'f'
- substitution of the self reference 'this' (by the value of "new C(...)"
operator "overload":
// we can use operators (such as '+') for objects
new Rational(2/3) + new Rational(4/5)
// ... instead of:
new Rational(2/3).add(new Rational(4/5))
via 1. infix notation for functions:
example: "r1 add r2" instead of "r1.add(r2)"
2. relaxed identifiers:
identifiers can
- start with alphanumeric and contain special chars ('+?%&_)
- contain only special chars ('+?%&_)
Examples of valid identifiers: x1, *, +?%&, vector_++, counter_=
operator precedence:
precedence of an operator depends on its 1st letter
chars sorted by priority: letters | ^ & < > = ! : + - * / % (all other special chars)
WARNING:
use operators with care and onywhen it makes sense
✔ Week 3: Data and Abstraction @done (14-05-20 08:03)
✔ Lecture 3.1 - Class Hierarchies (25:50) @done (14-05-11 16:30)
core concept: dynamic binding
abstract class / extension:
can have members without implementation
cannot be instanciated
example: binary trees with purely functional data structure (no mutation), aka persistent data structure
superclass / subclass / base class
in Scala, all classes extend java.lang.Object
overriding:
subclasses can redefine a non-abstract definition via 'override' modifier (mandatory)
example:
abstract class MyBaseClass { def foo = 1; def bar: Int }
class MySubClass {
override def foo = 2 // override is mandatory
override def bar = 3 // override is optional (less preferred < noisy)
}
singleton object:
class with only one instance
can reference itself (since it is a value)
object Empty ... // instead of "class Empty ..."
N.B.: standalone apps (main programs) are singletons with a main function
dynamic binding:
dynamic method dispatch: code invoked by a method depends on the runtime type of the object that contains the method
Scala implements it (like other some other OOP langs)
cf. similarity with HOFs (can we implement objects via HOFs and vice-versa?)
✔ Lecture 3.2 - How Classes Are Organized (20:30) @done (14-05-11 17:18)
How to organize real-life code (i.e. 100+ classes)?
packages:
classes and objects are organized in packages
fully qualified class name: <package>.<class name>
import:
- a single class or object from a package: "import mypackage.MyClass"
- import several classes (or objects) from a package: "import mypackage.{MyClass, OtherClass}"
- import all classes (or objects) from a package: "import mypackage._" (wildcard import)
(automatically imported:)
- scala._ (Int, Boolean, etc...)
- java.lang._ (Object, etc...)
- scala.Predef._ (require, assert, etc...)
scaladoc:
generated code documentation (see Scala lib's scala doc)
Traits:
Traits are like abstract classes
Scala uses single inheritance, so 1 object / class or trait
can inherit from only 1 class
but can inherit from several traits
ex: class Square extends Shape with Planar with Movable
Traits cannot have value params
Scala's class hierarchy:
Any // Any's methods: == != equals hashCode toString
AnyVal (primitive types + Unit) + cf. conversion relations
AnyRef (other types: String, Seq, etc...) / ScalaObject
Null // subtype of AnyRef (except Nothing), null's type
Nothing // subtype of all types, has no value, used for 1. abnormal termination (exceptions) + 2. for empty collections
✔ Lecture 3.3 - Polymorphism (21:09) @done (14-05-11 18:00)
parameterized types:
Functions and classes can have parameterized types
notation: MyClass[MyParameterizedType]
example: a fundamental data structure, immutable linked list (cons-list)
N.B: type params can often be deduced by compiler (type inference)
ex: "singleton(2)" instead of "singleton[Int](2)"
Type erasure:
type param does not affect evaluation in Scala (it only affects compilation)
Some other langs (C++, F#, et...) keep type at runtime
Polymorphism:
= a function type comes in "many forms":
a function can be applied to args of many types (-> subtyping)
or
a type can have instances of many types (-> generics)
✔ Week 4: Types and Pattern Matching @done (14-05-29 16:22)
✔ Lecture 4.1 - Functions as Objects (8:04) @done (14-05-20 08:39)
How function types relate to classes & how function values relate to objets
Functions as objects:
Function values are treated as objects
Type "A => B" is a abbreviation for "trait Function1[A,B] { def apply (x: A): B }"
see Function2, Function3, etc...
Anonymous function '(x: Int) => x * x" is expanded to: //
{
class AnonFun extends Function1[Int, Int] {
def apply(x: Int) = x * x
}
new AnonFun
} // or shorter, using anonymous class syntax:
new Function1[Int, Int] {
def apply(x: Int) = x * x
}
Function calls (expansion):
Methods such as
def f(x: Int): Boolean = ..."
is only converted to a function value when function type is expected ("eta-expansion in lambda-calculus").
Ex: //
(x: Int) => f(x)
is expanded to: //
new Function1[Int, Boolean] { def apply(x: Int) = f(x) }
✔ Lecture 4.2 - Objects Everywhere (19:07) @done (14-05-20 13:38)
primitive types as classes (OO):
pure object-oriented language: every value is an object, type of every value is a class
Is Scala a pure OO language?
Yes, we can implement all primitive types and operators (i.e. boolean, int) via classes (Boolean, Int, etc...).
exercise 1: implement Boolean operators from scratch via a class
exercise 2: implement class that represents non-negative integers without primitive type ("Peano numbers")
✔ Lecture 4.3 - Subtyping and Generics (15:02) @done (14-05-21 08:35)
About polymorphism and Liskov Substitution Principle
2 forms of polymorphism:
- generics (for functions)
- subtyping (for types => OOP)
2 areas:
- type bounds
- variance
Type bounds:
Upper bound:
// S is a subtype of T
S <: T
Lower bounds:
// S is a supertype of T (i.e. T is a subtype of S)
S >: T
Mixed bounds:
example: S >: NonEmpty <: IntSet
example:
Function 'assertAllPos' which input is Int set and which returns
- empty Int set if input is empty
- non empty set if input contains only positive ints
- throw Exception otherwise
// we can use "upper bound"
def assertAllPos[S <: IntSet](r: S): S
Covariance:
Given
NonEmpty <: IntSet
Is List[NonEmpty] <: List[IntSet] true?
In Java, arrays are covariant, but it causes runtime problems (not detected by compilation)
In Scala, arrays are not covariant
Liskov Substitution Principle:
if A <: B, all methods of type B should be available for value of type A
(N.B.: LSP is a bit more formal)
// NonEmpty <: IntSet
val a: Array[NonEmpty] = ...
val b: Array[IntSet] = a // Compilation error!
b(0) = Empty
val s: NonEmpty = a(0)
☐ Lecture 4.4 - Variance (Optional) (21:33)
✔ Lecture 4.5 - Decomposition (16:57) @done (14-05-21 09:31)
Example:
// write a small interpreter for arithmetics expression
Non-solution 1:
Not scalable type hierarchy (+ eval function) could be
trait Expr
- isNumber
- isSum
- isProd
... // does not scale (quadratic increase of methods)...
- number
/ | \p
Number Sum Prod etc...
NOT SCALABLE!
Non-solution 2:
Using type tests and type casts in eval function
pro: no classification
cons: low level / unsafe
Solution 1 via OOP decomposition:
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 : e1.eval + e2.evpal }
limitation:
If we add another method (example: "show"), we add to implement it in all hierarchy
We cannot simplify expressions in one method (ex: a * b + a * c -> a * (b + c))
This issue is known as the "expression problem"
Cf. "pattern matching" lecture for fixing this issue
✔ Lecture 4.6 - Pattern Matching (19:36) @done (14-05-21 13:18)
pattern matching is good fit for resolving our decomposition problem
case classes:
- allow pattern matching on a constructor, variables, constants or wildcard ('_')
- define implicit apply method (=> factory methods) ex: Number(2)
syntax:
... match {
case pattern1 => eval1
case pattern2 => eval2
// otherwise: expression error
}
If a pattern matches, expression is rewritten to its right-hand side of expression.
If pattern contains a variable, name of variable is bound to its value
Solution 2 via pattern matching:
// in eval function:
def eval(e: Expr): Int = e match {
case Number(n) => n
case Sum(e1, e2) => eval(e1) + eval(e2)
}
// or in trait:
trait Expr {
def eval: Int = this match {
case Number(n) => n
case Sum(e1, e2) => e1.eval() + e2.eval()
}
}
Adding an operation (example, "show") is implemented in a single function
def show(e: Expr): String = e match {
case Number(x) => x.toString
case Sum(l, r) => show(l) + " + " + show(r)
}
✔ Lecture 4.7 - Lists (16:20) @done (14-05-21 21:12)
Collections (particularly immutables ones)
Lists:
immutable (arrays are mutables)
recursive (arrays are flat)
homogeneous: all elems must have same type
cons-list: constructed with empty list 'Nil' + operation '::' (pronounced "cons")
[convention: all functions ending with ':'
- associate to the right, i.e. A :: B :: C is interpreted as A :: (B :: C)
- are method calls on the right-hand operator, i.e. 1 :: 2 :: Nil is equivalent to Nil.::(2).::(1) ]
val l = List("a", "b", "c")
val l2 = List(List(1, 2), List(3, 4, 5)) // recursive
val l3 = List() // empty list
val l4 = 1 :: (2 :: Nil)
basic operations: head, tail, isEmpty
pattern matching can be used (and is often prefered) => list decomposition
sorting can be done via pattern matching
def insertionSort(xs: List[Int]): List[Int] = xs match {
case List => List()
case y :: ys => insertionSort(y, ys)
}
☐ Week 5: Lists
✔ Lecture 5.1 - More Functions on Lists (13:04) @done (14-05-29 17:16)
More methods: length, last, init (all elements except last), take(n) (first n elements), drop(n)
(index)
creation:
++ (concatenation), reverse, updated(n, x)
finding elements:
xs indexOf x (index of first element that equals x)
xs contains x (true if xs contains x)
(n) (value at index n)
complexity:
warning:
last, init are O(n)
xy :: xs is O(size(xs))
reverse is O(n2)
✔ Lecture 5.2 - Pairs and Tuples (10:45) @done (14-05-29 17:37)
pair = 2-tuple
pairs can be pattern matched
(a,b) is an abbreviation of scala.Tuple2(a,b)
(a,b,c) is an abbreviation of scala.Tuple3(a,b,c)
case class Tuple2[T1,T2] (_1: +T1, .2: +T2)
ex:
val pair ("answer", 42)
val answerIs = pair._2
usage example:
Sort list more efficiently via merge sort
1. split list in 2 sub-lists
2. sort sub-lists
3. merge sorted sub-lists into single list
def mergeSort(xs: List[Int]): List[Int] ={
val n = xs.length / 2
if (n == 0) xs
else {
// use nested patter matching that reflect the inherent symetry of the algotrithm
def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, xy) match {
case (Nil, ys) => xy
case (xs, Nil) => xs
case (x :: xs1, y :: ys1) => if (x < y) x :: merge(xs1, ys) else y :: merge(xs, ys1)
}
val (first, second) = xs splitAt n
merge(mergeSort(first), mergeSort(second))
}
}
✔ Lecture 5.3 - Implicit Parameters (11:08) @done (14-05-29 17:59)
Implicit parameter is infered by the compiler (not set explicitely in function call)
How to use mergeSort function for other types that Int?
Use type parameter + comparison function:
def mergeSort[T](xs: List[T])(lt: (T,T) => Boolean) = ...
mergeSort(List(1,6,3,5))((x,y) => x < y) // compiler infers types...
// or use standard lib for ordering: math.Ordering which contains lt(x,y)
def mergeSort[T](xs: List[T])(ord: Ordering) = ...
mergeSort(List(1,6,3,5))(Ordering.Int)
// or better, use implicit parameter
def mergeSort[T](xs: List[T])(implicit ord: Ordering) = ...
mergeSort(List(1,6,3,5)))
✔ Lecture 5.4 - Higher-Order List Functions (14:53) @done (14-05-30 17:19)
several patterns: transform all elements, combine them, retrieve another list...
map:
apply function to all elements, return list (NB: works for all collections)
xs map f
filter:
return list filtered by a function
xf filter (x => x > 10)
variations of filter: filterNot, partition (split in two lists), takeWhile, dropWhile, span (split in two lists)
✔ Lecture 5.5 - Reduction of Lists (15:35) @done (14-05-30 17:36)
fold / reduce combinators
reduceLeft/reduceRight:
Cannot be applied to empty list
List(1,2,3) reduceLeft ((x,y) => x + y)
// or:
List(1,2,3) reduceLeft 0 (_ + _)
foldLeft/foldRight:
Similar, can be applied to empty list because it has an accumulator param
(List(1,2,3) foldLeft 0)(_ + _)
☐ Lecture 5.6 - Reasoning About Concat (13:00)
Proof techniques
Laws of concat (++):
associative: (xs ++ ys) ++ zs = xs ++ (ys ++ zs)
admit Nil neutral elem: xs ++ Nil = xs and Nil ++ xs = xs
Natural induction:
1. show property for base case n
2. induce step n+1
Referential transparency:
Structural induction:
☐ Lecture 5.7 - A Larger Equational Proof on Lists (9:53)
☐ Week 6: Collections
✔ Lecture 6.1 - Other Collections (20:45) @done (14-06-02 09:01)
Other immutable collections than List
Iterable
/ | \
Seq Set Map
/ | \
List Vector Range
Vector:
is a Seq (sequence), like List
implemented via array tree that progressively grows
=> get(i) = O(log(n))
adapted to bulk operations (chunks in cache) like map, filter, etc...
operations are similar to List, except the cons
x +: xs // x is the 1st elem
xs :+ x // x is the last elem
construction is O(log(n)) due to object creation
Range:
lower bound + upper bound + step value)
1 until 5 // 1,2,3,4
1 to 5 // 1,2,3,4,5
1 to 10 by 3 // 1,4,7,10
Seq:
Array ans String have same ops that Seq
support ranges
ops:
xs exists p
xs forall p
xs zip ys // returns a sequence of pairs
xs unzip // returns a flat seq from pairs
xs.flatMap f // returns a seq containing all elements of xs with f applied
xs.sum
xs.product
xs.max
xs.min
examples:
// list all combinations (x, y):
(1 to M) flatMap (x => (1..N) map (y => (x,y)))
// product of scalar vectors (sum from i=1 to n = xi * yi):
def scalarProduct(xs: Vector(Double), ys: Vector(Double)): Double =
(xs zip ys).map(xy => xy._1 * xy._2).sum
// or via pattern matching:
(xs zip ys).map{ case (x, y) => x * y }.sum
// is prime number?
def isPrime(n: Int): Boolean = (2 until n) forall (d => n % d != 0)
✔ Lecture 6.2 - Combinatorial Search and For-Expressions (13:12) @done (14-06-02 20:33)
handling nesting sequences, without loops
for-expression is similar to imperative loop:
for (s) => yield e
example 1:
find all pairs of positive integers i, j such as j < i and i + j is prime
the FP way: 1. generate pairs such as j < i
2. filter pairs for which i + j is prime
// via until + flatMap + map (a bit hard to read)
(1 until n) flatMap (i =>
(l until i) map (j => (i, j)))
.filter(pair => isPrime(pair._1 + pair._2))
// via for-expression (clearer):
for {
i <- 1 until n
j <- 1 until i
if isPrime(i + j)
} yield(i, j)
example 2:
def scalarProduct(xs: List[Double], ys: List[Double]): Double =
(for ((x, y) <- xs zip ys) yield x * y).sum
✔ Lecture 6.3 - Combinatorial Search Example (16:54) @done (14-06-03 08:26)
Sets are similar to sequences but:
1. unordered
2. no duplicate elements
3. fundamental operation is "contains"
Set examples:
val fruits = Set("apple, banana", "pear")
val nums = (1 to 2).toSet
nums map (_ + 2)
fruits filter(_.startsWith == "app")
N-queens example:
// place n queens on a board without "threatening" (in same row or column or diagonal)
def queens(n: Int): Set[List[Int]] = {
def isSafe(col: Int, queens: List[Int]) = {
val row = queens.length
val queensWithRow = (row-1 to 0 by -1) zip queens
queensWithRow forall {
case (r, c) => col != c && math.abs(col - c) != row - r
}
}
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 show(queens: List[Int]) = {
val lines =
for (col <- queens.reverse)
yield Vector.fill(queens.length)("* ").updated(col, "X ").mkString "\n" + (lines mkString "\n")
}
// queens(4) map show
// (queens(8) take 3) map show
✔ Lecture 6.4 - Queries with For (7:50) @done (14-06-03 09:05)
More about for-expressions
for-expression notation is similar to query languages for database
// retrieve title of books which author name starts with "Bird":
for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title
// find authors who have written at least 2 books:
{
for {
b1 <- books ; b2 <- books
if (b1 != b2)
a1 <- b1.authors ; a2 <- b1.authors
if (a1 == a2)
} yield a1
}.distinct // remove duplicate names, if books is a list (but not needed it is a set)
✔ Lecture 6.5 - Translation of For (11:23) @done (14-06-03 13:52)
Implementation of for-expressions
related to HOF functions map, flatMap and filter
* map, flatMap and filter can be implemented by for-expression
* for-expressions are implemented by map, flatMap and filter:
// example 1:
for (x <- e1) yield e2
// is translated by Scala compiler to:
e1.map(x => e2)
// example 2:
for (x <- e1 if f; s) yield e2
// is translated by Scala compiler to:
for (x <- e1.withFilter(x => f); s) yield e2 // withFilter is lazy version of filter
// example 3:
for (x <- e1; y <- e2; s) yield e3
// is translated by Scala compiler to:
e1.flatMap(x => for (y <- e2; s) yield e3)
// example 4:
for {
i <- 1 until n
j <- 1 until i
if isPrime(i + j)
} yield (i, j)
// is translated by Scala compiler to:
(1 until n).flatMap(i =>
(1 until i).withFilter(j => isPrime(i+j))
.map(j => (i, j)))
Exercise:
// translate the following code
for (b <- books; a <- b.authors if a startsWith "Bird")
yield b.title
// into a HOF:
books flatMap ( b =>
b.authors withFilter (a => a startsWith "Bird")
map (y => y.title))
✔ Lecture 6.6 - Maps (22:39) @done (14-06-03 20:44)
Map:
maps associate key to value
are iterable and are functions, in Scala
Examples:
// create map:
val romanNumerals = Map("I" -> 1, "II" -> 2)
// query value for a given key (error if absent):
romanNumerals("II") // returns 2
romanNumerals("not exists") // throws java.util.NoSuchElementException
// query value option for a given key
romanNumerals get "not exists" // Option: None
romanNumerals get "I" // Option: Some(1)
Option decomposition:
// using pattern matching:
def showNumber(roman: String) = romanNumerals.get(roman) match = {
case Some(number) => number
case None => 0
}
Sort / group-by:
val fruits = List("banana", "apple")
fruits sortWith (_ < length < _.length) // List("apple", "banana")
fruits.sorted // List("apple", "banana")
fruits groupBy (_.head) // Map(a -> List("apple"), b -> List("banana")
Default value:
val romanNumeral withDefaultValue -1
val("I") // 1
val("not exists") // -1
Example - polynomial:
// x^3 - 2 x + 5 can be represented by:
Map(0 -> 5, 1 -> -2, 3 -> 1)
// let's design a class Polynom that reprensent polynoms as maps:
object Polynomials {
class Poly(val terms0: Map[Int -> Double]) {
val terms = term0 withDefaultValue 0.0
def this(bindings: (Int, Double)*) // *: repeating parameter (vararg), as a sequence
this(bindings.toMap)
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))
}
// alternative implem that uses foldLeft (more efficient that '+'):
def plus (other: Poly) =
new Poly((other.terms foldLeft terms)(addTerm))
def addTerm(terms: Map[Int, Double], term: (Int, Double)): Map[Int, Double] = {
val (exp, coeff) = term
terms + (exp -> (coeff + terms(exp)))
}
override def toString =
(for ((exp, coeff) <- terms.toList.sorted.reverse)
yield coeff + "x^" + exp) mkString " + "
}
val p1 = new Poly(Map(0 -> 5, 1 -> -2, 3 -> 1))
val p2 = new Poly(0 -> 5, 1 -> -2, 3 -> 1)
p1 + p2
}
✔ Lecture 6.7 - Putting the Pieces Together (20:35) @done (14-06-03 21:24)
Example: convert phone numbers to sentences (cf. Lutz Prechelt: An empirical comparison of seven programming languages)
val words = Source.fromURL("http://xxx").getLines.toList
filter (word => word forall (chr => chr.isLetter)) // filter words with chars such as "-"
val mnemonics = Map('2' -> "ABC", '3' -> "DEF" ...)
// produce all phrases that could be used as mnemonics:
// "invert mnemonic map" (i.e. Map('A' -> '2', 'B' > '2'))
val charCode: Map[Char, Char] =
for ((digit, str) <- mnemonics); ltr <- str) yield ltr -> digit
// map a word to a digit string (i.e. "java" -> "5282")
val charCode(word: String): String =
word.toUpperCase map charCode
// all words for a digit lists (i.e. "5282" -> List("java", "kata", ...))
val wordsForNum: Map[String, Seq[String]] =
words groupBy wordCode withDefaultValue(Seq())
// i.e. "7225247386" -> Set("xxx yyuy zzzdz", ...)
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
// i.e. "7225247386" -> "xxx yyuy zzzdz"
def translate(number: String): Set[String] =
encode(number) map (_ mkString " ")
☐ Week 7: Lazy Evaluation
☐ Lecture 7.1 - Structural Induction on Trees (15:10)
✔ Lecture 7.2 - Streams (12:12) @done (14-06-09 12:34)
Streams
Stream: like list, but with lazy tail (on demand)
Usage example:
// find 2nd prime number, elegant way but not performant at all (all primes in range are computed):
((1000 to 10000) filter isPrime)(1)
// with stream:
(1000 to 10000).toStream filter isPrime)(1)
Stream construtors:
stream1 = Stream.cons(1, Stream.cons(2, Stream.empty))
stream2 = Stream(1, 2, 3)
(1 to 1000).toStream // REPL: Stream[Int] = (1, ?)
Stream range:
def streamRange(lo: Int, hi: Int): Stream[Int] =
if (lo >= hi) Stream.empty
else Stream.cons(lo, streamRange(lo + 1, hi))
Stream methods:
Same methods as List: isEmpty, head, tail, filter, etc... but except cons "::" which always produces a list
"#::" produces a stream
Cons implem:
trait Stream {
// Notice that tail param is a by-name parameter
def cons[T] (hd: T, tl: => Stream[T]) = {
def isEmpty = false
def head = hd
def tail = tl
}
}
✔ Lecture 7.3 - Lazy Evaluation (11:38) @done (14-06-10 08:48)
lazy evaluation:
compute late and compute only once
(like by-name evaluation, but compute once)
=> avoid performance issue if multiple recomputations
Haskell uses lazy eval by default.
Scala uses strict evaluation by default.
def fooDef = { println "fooDef"; 0}
val fooVal = { println "fooVal"; 0}
lazy val = { println "fooVal"; 0}
Syntax:
lazy val x = expr
Usage example, Stream improvement (lazy tail):
trait Stream {
def cons[T] (hd: T, tl: => Stream[T]) = {
def head = hd
lazy val tail = tl
// ...
}
}
✔ Lecture 7.4 - Computing with Infinite Sequences (9:01) @done (14-06-10 09:10)
Lazy vals allow infinite streams
Basic usage:
def from(n: Int): Stream[Int] = n #:: from(n+1)
// all natural numbers:
val naturalNumbers = from(0)
// all multiples of 4:
naturalNumbers map (_ * 4)
Examples:
Sieve of Eratosthenes (prime numbers):
def sieve(s: Stream[Int]): Stream[Int] =
s.head #:: sieve(s.tail filter (_ % s.head != 0))
val primes = sieve(from(2))
Square roots:
def sqrtStream(x: Double): Stream[Double] = {
def improve(guess: Double) = (guess + x / guess) / 2
lazy val guesses: Stream[Double] = 1 #:: (guesses map improve)
guesses
}
def isGoodEnough(guess: Double, x: Double) =
math.abs((guess * guess - x) / x) < 0.0001
sqrtStream(4) filter (isGoodEnough(_, 4))
✔ Lecture 7.5 - Case Study: the Water Pouring Problem (31:45) @done (14-06-10 21:09)
(our solution can be compared to original Python's solution)
Problem:
measure a given water volume via several glasses that have distinct capacity
Representation (state and moves):
Glass: Int
State: Vector[Int] (one entrey per glass)
Moves: Empty(glass)
Fill(glass)
Pour(from, to)
Solution: find all paths until a state contains our requested quantity
Implem:
class Pouring(capacity: Vector[Int]) {
// State:
type State = Vector[Int]
val initialState = capacity map (x => 0)
// Moves:
trait Move {
def change(state: State): State
}
case class Empty(glass: Int) extends Move {
def change(state: State): State = state updated (glass, 0)
}
case class File(glass: Int) extends Move {
def change(state: State): State = state updated (glass, capacity)
}
case class Pour(from: Int, to: Int) extends Move {
def change(state: State): State = {
val amount = state(from) min (capacity(to) - state(to))
state updated (from, state(from) - amount) updated (to, state(to) + amount)
}
}
val glasses = 0 until capacity.length
val moves =
(for (g <- glasses) yield Empty(g)) ++
(for (g <- glasses) yield Fill(g)) ++
(for (from <- glasses; to <- glasses if from != to) yield Pour(from, to))
// optimization: compute end state once
class Path(history: List[Move], val endState: State) {
def extend(move: Move) = new Path(move :: history, move change endState)
override toString() = (history.reverse mkString " ") + "--> " + endState
}
val initialPath = new Path(Nil, initialState)
def from(paths: Set[Path], explored: Set[Path]): Stream[Set[Path]] =
if (paths.isEmpty) Stream.empty
else {
val more = for {
path <- pathes
next <- moves map path.extend
// prevent infinite search: do no visit explored state twice
if !(explored contains next.endState)
} yield next
paths #:: from(more, explored ++ (more map (_.endState)))
}
val pathSets = from(Set(initialPath), Set(initialState))
def solution(target: Int): Stream[Path] =
for {
pathSet <- pathSets
path <- pathSet
if path.endState contains target
} yield path
}
Note:
we could also naked data structures with functions (and not OO methods)
Guidelines for good design:
name everything you can
put operations into natural scopes (use private functions, etc...)
keep degrees of freedom for future refinements
✔ Lecture 7.6 - Course Conclusion (5:34) @done (14-06-10 21:18)
what we've seen:
higher-order functions
case classes and pattern matching
immutable collections
absence of mutable state
flexible evaluation strategies (strict/lazy/by name)
=> a useful toolkit + a different way to think about programs
References:
Laurent Poulain's Scala ref card
Twitter's Scala school
"Programming in Scala" (book)
"Scala Tour" (web)
Scala meetups
Typesafe blog
Cake solutions' blog
Next?:
FP and state (how to mix mutable and immutable?)
parallelism
domain specific languages
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment