Записки программиста, обо всем и ни о чем. Но, наверное, больше профессионального.

2016-03-23

Functional Programming Principles in Scala

Вот тут
я начал выкладывать материал про Scala.
Продолжу.

Курс
Functional Programming Principles in Scala
Мартин Одерски (Martin Odersky), автор Scala.



Getting Started


Tools Setup
you need to have the following tools installed on your machine:
– JDK (Java Development Kit) version 1.7 or 1.8
– Sbt, a build tool for Scala, version 0.13.x
– The Scala IDE for Eclipse (or another IDE of your choice)
aptitude install java7-jdk
valik@snafu:~$ java -version
java version "1.7.0_85"

echo "deb https://dl.bintray.com/sbt/debian /" | tee -a /etc/apt/sources.list.d/sbt.list
sudo apt-key adv --keyserver hkp://keyserver.ubuntu.com:80 --recv 642AC823
aptitude install apt-transport-https
aptitude update
aptitude install sbt
sbt -v # and wait ...
... java_version = '1.7.0_95'
> about
[info] This is sbt 0.13.11
[info] sbt, sbt plugins, and build definitions are using Scala 2.10.6
Scala IDE for Eclipse is best installed (and updated) directly from within Eclipse.
This is done by using Help → Install New Software..., add the Add... button in the dialog

Tutorial: Working on the Programming Assignments
– download and unpack assignment
cd epfl.FPP-in-Scala/streams
sbt -v
clean
compile
styleCheck
test
run
reload
eclipse
– start Eclipse, import project

– In sbt, you can use 'console' command to start REPL.
– In Eclipse you can open/create 'Scala Worksheet' and use REPL
object testWorksheet {
    println("Welcome to the Scala worksheet")     //> Welcome to the Scala worksheet
    val x = 3                                     //> x  : Int = 3
    def increase(i: Int) = i + 1                  //> increase: (i: Int)Int
    increase(x)                                   //> res0: Int = 4
}

To run a program, you can create 'Scala App' and write something like:
object Hello extends App {
  println("Hello, World!")
}

Two recursive functions, for example
package example
object Lists {
  def sum(xs: List[Int]): Int = {
    if(xs.isEmpty) 0
    else xs.head + sum(xs.tail) }
  def max(xs: List[Int]): Int = {
    def maxi(ai: Int, bi: Int): Int = {
      if(ai > bi) ai
      else bi}
    if(xs.isEmpty) throw new java.util.NoSuchElementException("List is empty")
    else if(xs.length == 1) xs.head
    else maxi(xs.head, max(xs.tail)) } }

Week 1: Functions & Evaluations


-- Lecture 1.1 - Programming Paradigms
paradigm: distinct concepts or thought patterns in some scientific discipline

– programming paradigms: imperative prog.; functional prog.; logic prog.;
object-oriented prog. (orthogonal).
– imperative: Von Neumann computer:
mutable variables = mem.cells; var assignment = store instructions, …
– we need to scale-up: defining high-level abstractions (collections, documents, …)
– develop theories of collections, documents, …
theory: data type(s), operations on them, laws that describe ralationships between values and ops.
a theory does not describe mutations! see math.
– e.g: theory of polynomials, op: sum of two by law:
(ax+b) + (cx + d) = (a+c)x + (b+d)
does not define an op. to change a coeff. while keeping the polynomial the same.

bottom line: if we want to implement high-level concepts following their math. theories, there's no place for mutations.
For that: concentrate on defining theories, ops expressed as functions; avoid mutations;
have powerful ways to abstract and compose functions.

OK, functions: FP means
– restricted sense: programming w/o mutable variables, assignments, loops, other imperative control structures
pure Lisp, XSLT, XPath, XQuery, … Haskell w/o io monad or whatnot – declarative languages.
– wider sense: focusing on the functions – first-class citizens – values that are produced, consumed, and composed.
functions: defined anywhere, passed as parameters, returned as result. Composed like other values.
Enters FP language: Scala

-- Lecture 1.2 - Elements of Programming, evaluation
substitution model

Evaluation: expression is evaluated as follows
– take the leftmost operator, evaluate its operands (left before right);
apply the operator to the operands.
– a name is evaluated by replacing it with the right hand side of its definition.
– evaluation process stops once it results in a value, say a number.

Definitions can have parameters: def square(x: Double) = x*x
– params come with their type, after a colon
– return type: def square(x: Double): Double = x*x

Functions applications evaluation: in a similar way
– evaluate all f. arguments, left-to-right
– replace the f.application by the f. right-hand side and, at the same time
– replace the formal parameters by the actual arguments
sumOfSquares(3, 2+2)
sumOfSquares(3, 4)
square(3) + square(4)
3*3 + square(4)
9 + square(4)
9 + 4*4
9+16
25

The substitution model (SM): scheme of evaluation above is called the SM
– idea: evaluation reduce an expression to a value
– can be applied to all expressions, as long as they have no side effects
– SM is formalized in the lambda-calculus, which gives a foundation for FP.
– For side effects you need some storage, and another model.

-- Lecture 1.3 - Evaluation Strategies and Termination
Call-By-Name, Call-By-Value, Termination

– not every expression reduce to a value: def loop: Int = loop
– reduce functions arguments to values before rewriting the function application: CBV
– apply the function to unreduced arguments: CBN (start func.parameter with '=>' in func. def)
def square(x: =>Int) = x*x
square(2+2)
(2+2) * (2+2)
4 * (2+2)
4 * 4
16

both strategies reduce to the same final values as long as:
– the reduced expression consists of pure functions
– both evaluations terminate
A pure function is a function where the return value is only determined by its input values, without observable side effects.
If evaluation CBV terminate => CBN also terminate.

advantages:
– CBV: evaluates every function argument only once, more effective in practice
– CBN: argument is not evaluated if the corresponding parameter is unused in the evaluation of the function body

-- Lecture 1.4 - Conditionals and Value Definitions
Expression 'if-else' (not statement, unlike Java)

– expression can be reduced to value, statement is more general: expression is part of a statement.
def abs(x: Int) = if (x >= 0) x else -x
def and(x: Boolean, y: =>Boolean) = if(x) y else false // y CBN
def or(x: Boolean, y: =>Boolean) = if(x) true else y // y CBN
– 'x >= 0' is a predicate, of type Boolean (bool valued function).
Boolean expressions can be composed of
– operands: true, false, !b, b && b, b || b // constants, negation, conjunction, disjunction
– operations: <=, >=, <, >, ==, !=

Rewrite/reduction rules for Boolean expressions (evaluation model)
– !true = false
– !false = true
– true && e = e
– false && e = false // short-circuit evaluation
– true || e = true // short-circuit evaluation
– false || e = e
Note that && and || do not always need their right operand to be evaluated

Value definitions: CBN, CBV
– val x = square(2) // CBV, x refers to 4, evaluated inplace
– def y = square(3) // CBN, type Int
The difference def vs. val becomes apparent when the right-hand side does not terminate.

-- Lecture 1.5 - Example: square roots with Newton's method
recursion: right-hand side calls itself
    def sqrt(x: Double): Double = {
        def sqrtIter(guess: Double): Double =
            if (isGoodEnough(guess)) guess
            else sqrtIter(improve(guess))
        def isGoodEnough(guess: Double): Boolean =
            abs(guess * guess - x) / x < 0.00000001
        def improve(guess: Double): Double =
            (guess + x / guess) / 2
        sqrtIter(1) }

-- Lecture 1.6 - Blocks and Lexical Scope (visibility)
A block is delimited by braces '{ }'

– it's an expression (can be reduced to a value)
– contains a sequence of definitions or expressions
– last element defines block value
– the definitions inside a block are only visible from the block
– the definitions inside … shadows definitions of the same names outside the block

Semicolons
– needed only to separate a few statements in one line
val y = x + 1; y * y
– one issue (infix operations): expressions that span several lines
use parentheses: (longExprOne … \n + otherLongExpr)
or write operator on the first line: longExprOne … + \n otherLongExpr

-- Lecture 1.7 - Tail Recursion
We have here two types of recursion: linear recursion and tail recursion

– tail recursion: iterative process, function calls itself as its last action // tail-call
def gcd(a: Int, b: Int): Int = if(b == 0) a else gcd(b, a % b)
// rewrite (evaluation model)
gcd(14, 21) 
if(21 == 0) 14 else gcd(21, 14 % 21)
if (false) 14 else gcd(21, 14 % 21)
gcd(21, 14 % 21)
gcd(21, 14)
...
tail call, stack can be reused.

– linear recursion: after recur.call other ops exists
def factorial(n: Int): Int = if(n == 0) 1 else {n * factorial(n-1)} 
// rewrite 
factorial(4) 
if(4==0) 1 else 4 * factorial(4-1) 
4 * factorial(3) 
4 * (3 * factorial(2))
...
we can't reuse stack frames, no tail recursion, no loop

– one can require that a function is tail-recursive using a @tailrec annotation
@tailrec 
def gcd(a: Int, b: Int): Int = if(b == 0) a else gcd(b, a % b)

Tail recursion using accumulator
@tailrec
def factorial(n: Int): 
  def loop(acc: Int, x: Int): Int = if(x == 0) acc else loop(acc*x, x-1)
  loop(1, n) 

Week 2: Higher Order Functions / f. compositions


-- Lecture 2.1 - Higher-Order Functions, f. as a parameter
functions: first-class values, can be passed as a parameter and returned as a result

functions that take other f. as parameter or that return f. as results are called: higher-order functions
– Example: sum n:a..b f(n)
def sumInts(a: Int, b: Int): if(a > b) 0 else a + sumInts(a+1, b)
– Higher-Order sum, function f as parameter:
def sum(f: Int => Int, a: Int, b: Int) = if(a > b) 0 else f(a) + sum(f, a+1, b)
def id(x: Int) = x
def sumInts(a: Int, b: Int) = sum(id, a, b)
– function 'f': Int to Int, type A arrow type B – is the type of a function
that takes type A and returns type B (function that map A to B)
– Int => Int is the type of functions that map integers to integers

Anonymous functions
– passing functions as parameters leads to the creation of many small functions
– we would like function literals: anonymous functions
– a.f. are syntactic sugar
(x: Int) => x*x*x // cube 
(x: Int, y: Int) => x+y // sum
// can be always expressed as 
{ def fn(x: Int) = x*x*x; fn }
{ def fn(x: Int, y: Int) = x+y; fn }
// back to sumInts example:
def sumInts(a: Int, b: Int) = sum(x => x, a, b)

Sum with tail-recursion, exercise
def sum(f: Int => Int, a: Int, b: Int) = 
  @tailrec
  def loop(a: Int, acc: Int) = if(a > b) acc else loop(a+1, f(a) + acc)
  loop(a, 0)
sum(x => x*x, 3, 5) // sum of squares

-- Lecture 2.2 — Currying / return f.
Function that returns another function

example
def sum(f: Int => Int): (Int, Int) => Int = {
  def dosum(a: Int, b: Int) = if(a > b) 0 else f(a) + dosum(a+1, b)
  dosum }
can you see there rewrited anonymous function? Yep, with sugar it will be:
def sum(f: Int => Int) (a: Int, b: Int): Int = // multiple parameter list 
  if(a > b) 0 else f(a) + sum(f)(a+1, b)

Defining 'sum' that way, we can create particular sum functions
def sumInts = sum(x => x) // save 'f' in new definition
sumInts(3, 5)
or, omitting middleman
sum(x => x)(3, 5) // call 'sum' then call 'dosum'

Generally, function application assotiates to the left
sum (x => x) (3, 5) == (sum (x => x)) (3, 5)
// process 
def f(args1) … (args n) = E
def f(args1) … (args n-1) = {def fn(args n); fn}
// or for short 
def f = (args1 => (args2 => … (args n => E) … ))
This style of definition and function application is called currying (Haskell Brooks Curry).

Function types associate to the right (applications to the left!)
def sum(f: Int => Int) (a: Int, b: Int): Int = … // what is the type of 'sum'?
(Int => Int) => ((Int, Int) => Int) // func (Int => Int) map to func (Int, Int) => Int
// associate to the right:
Int => Int => Int is equivalent to Int => (Int => Int)

Exercise: product, factorial, sum, using general func (map-reduce pattern)
def mapReduce(f: Int => Int, combine: (Int, Int) => Int, zero: Int)(a: Int, b: Int): Int =
    if (a > b) zero
    else combine(f(a), mapReduce(f, combine, zero)(a + 1, b)) // iterate and accum

def product(f: Int => Int)(a: Int, b: Int) = mapReduce(f, (x, y) => x * y, 1)(a, b)
def sum(f: Int => Int)(a: Int, b: Int)     = mapReduce(f, (x, y) => x + y, 0)(a, b)

def fact(n: Int) = product(x => x)(1, n)
def sumInts(a: Int, b: Int) = sum(x => x)(a, b)

sumInts(3, 5) // 12
fact(5) // 120

-- Lecture 2.3 - Example: Finding Fixed Points
fixed point of a function: f(x) = x; average damping

for some functions 'f' we can locate the fixed points recursively:
x, f(x), f(f(x)), ...until the value does not vary anymore.
    def fixedPoint(f: Double => Double)(firstGuess: Double): Double = {
        def iterate(guess: Double): Double = {
            val next = f(guess)
            if (isCloseEnough(guess, next)) next
            else iterate(next) }
        iterate(firstGuess) }
fixedPoint(x => 1 + x/2)(1) // fp for function y = 1 + x/2: y = 1.9 if x = 1.9

Fixed point for sqrt(x): number y = x/y
def sqrt(x: Double) = fixedPoint(y => x/y)(1.0)
– but this does not converge, unfortunately.
– Fix that by averaging successive values: average damping
def sqrt(x: Double) = fixedPoint(y => (y + x/y) / 2)(1.0)

Using function that return function
– average damp strategy, currying
def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2
– Then sqrt will be simple
def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
Bottom line: two abstracted strategies encapsulated in high-order functions leads to nice solution.

-- Lecture 2.4 - Scala Syntax Summary
EBNF: Extended Backus-Naur form
| denotes an alternative 
[ … ] an option (0 or 1)
{ … } a repetition (0 or more)

Types: simple, function, ...
– numeric type (Int, Double, Byte, Short, Char, Long, Float)
– Boolean
– String
– function, like (Int, Int) => Int
– and more
Type = SimpleType | FunctionType 
FunctionType = SimpleType '=>' Type | '('[Types]')' '=>' Type 
Types = Type {',' Type} 
SimpleType = Ident 

Expressions: infix, function, conditional
– identifier (x, isGoodEnough)
– literal (0, «abc»)
– func.application (sqrt(x)
– operator application (-x, y+x)
– selection (math.abs)
– conditional expression (if … else …)
– block { … }
– anonymous func. (x => x+1)
Expr = InfixExpr | FunctionExpr | if '(' Expr ')' else Expr 
InfixExpr = PrefixExpr | InfixExpr Operator InfixExpr 
PrefixExpr = ['+' | '-' | '!' | '~'] SimpleExpr
SimpleExpr = ident | literal | SimpleExpr '.' ident | Block 
FunctionExpr = Bindings '=>' Expr 
Bindings = ident [':' SimpleType] | '(' [Binding {',' Binding}] ')'
Binding = ident [':' Type]
Operator = ident 
Block = '{' {Def ';'} Expr '}'

Definitions: function, value
– def square(x: Int) = x*x
– val y = square(2)
Parameter: CBN, CBV
– cbv: (x: Int)
– cbn: (x: =>Int)
Def = FunDef | ValDef
FunDef = def ident {'(' [Parameters] ')'} [':' Type] '=' Expr 
ValDef = val ident [':' Type] '=' Expr 
Parameters = Parameter {',' Parameter}
Parameter = ident ':' ['=>'] Type 
That's not all of it.

-- Lecture 2.5 - Functions and Data / classes, objects, methods
Data abstraction/encapsulation, for Rational Numbers (x/y – numerator/denominator)

rational numbers theory?
– class Rational
class Rational(x: Int, y: Int) { def numer = x; def denom = y }
// type Rational 
// constructor Rational 
– there's no conflict between two definitions: names of types and values in different namespaces.
– note that members 'numer' and 'denom' defined as CBN methods
– x and y: class parameters (not class fields)
– if you will write: class Rational(val x: Int, val y: Int) – x and y will be parameters and fields of a class

Create an object of a class/type: val o = new Rational(1, 2)
– select object member with infix operator '.': o.numer
– use 'this': object on which the current method is executed

Class methods: functions operating on a data abstraction in the data abstraction itself
class Rational(x: Int, y: Int) {
    private def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
    private val g = gcd(x, y)
    def numer = x / g
    def denom = y / g

    override def toString = numer / g + "/" + denom / g
    def less(that: Rational): Boolean = numer * that.denom < that.numer * denom
    def max(that: Rational): Rational = if (this.less(that)) that else this
    def add(that: Rational): Rational = new Rational(
            numer * that.denom + that.numer * denom,
            denom * that.denom)
    def neg: Rational = new Rational(-numer, denom)
    def sub(that: Rational): Rational = add(that.neg) }

-- Lecture 2.6 - More Fun With Rationals
Class: private members; greatest common denominator

members
– save memory: def numer = x / gcd(x, y)
– save time: val numer = x / g
Same interface, different implementations.

Preconditions/Assertions:
– use predefined function 'require' to enforce a precondition
class Rational(x: Int, y: Int) {
    require(y != 0, "denominator must be nonzero")
– There is also 'assert': assert(x >= 0, «x must be positive»)
– both preconditions can throw exceptions: IllegalArgumentException and AssertionError
– difference in intent: require is used to enforce a precondition on the caller; assert is used as to check the code

Constructors
– primary constructor: class Rational(x: Int, y: Int) { …
takes the parameters of the class; executes all statements in the class body
– secondary constructor: def this(x: Int) = this(x, 1)

-- Lecture 2.7 - Evaluation and Operators / infix operators
substitution model for classes

– computational model based on substitution: classes and objects
– instantiation of the class: new C(e1, …, em) evaluated like normal function application, resulting to a value
– evaluation of: new C(v1, …, vm).f(w1, …, wn) :
the substitution of the formal parameters of the function 'f' by the arguments w
the substitution of the formal parameters of the class 'C' by the arguments v
the substitution of the self reference 'this' by the value of the object new C(v1, …, vm)
new Rational(1,2).less(new Rational(2,3))
→ [1/x, 2/y] [new Rational(2,3)/that] [new Rational(1,2)/this]
  this.numer * that.denom < that.numer * this.denom
= new Rational(1,2).numer * new Rational(2,3).denom < ...
→ 1*3 < 2*2 ...

Operators: can be used as identifiers
– step 1: infix notation: any method with a parameter can be used like an infix operator
r add s // in place of r.add(s)
– step 2: relaxed identifiers: identifier can be alphanumeric, symbolic, '_', 'unary_-'
e.g: x1, *, +?%&, vector_++
def < (that: Rational) = this less that
def + (that: Rational) = this add that 
def unary_- : Rational = new Rational(-numer, denom)
def — (that: Rational) = this + -that

Operator precedence
– determined by its first character
– increasing order of priority
all letters // lowest priority 
|
^
&
< >
= !
:
+ -
* / %
all other special characters // highest priority
example
a + b ^? c ?^ d less a ==> b | c
( ((a + b) ^? (c ?^ d)) less ((a ==> b) | c) )

Week 3: Data and Abstraction


-- Lecture 3.1 - Class Hierarchies
example: immutable Int set, binary search tree

Abstract class
– can contain members w/o implementation
– no instances of an abstract class can be created
– declare an interface
abstract class IntSet { def incl(x: Int): IntSet; def contains(x: Int): Boolean }

Class extensions
– extension (Empty and NonEmpty) is a subclasses of IntSet
– IntSet is a superclass/base class of Empty and NonEmpty
– subclass implement interface from the base class or
the definitions of 'contains' and 'incl' in the classes Empty and NonEmpty
implement the abstract functions in the base trait IntSet
– in definition of constructor, base class IntSet used for definition of parameter type
class Empty extends IntSet { def contains(x: Int) = false 
  def incl(x: Int) = new NonEmpty(x, new Empty, new Empty) }
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
    def contains(x: Int): Boolean =
        if (x < elem) left contains x
        else if (x > elem) right contains x
        else true
    def incl(x: Int): IntSet =
        if (x < elem) new NonEmpty(elem, left incl x, right)
        else if (x > elem) new NonEmpty(elem, left, right incl x)
        else this }
// note that we have Persistent Data Structure, immutable set 

in Scala, any user-defined class extends another class
– java.lang.Object is a base class by default
– It's possible to redefine an existing, non-abstract definition in a subclass
override def toString = "{" + left + elem + right + "}"

singleton object
– object definition can express case of singleton
object Empty extends IntSet { def contains ...
– singleton objects are values, Empty evaluates to itself.
– standalone application is objects
object Hello {
    def main(args: Array[String]) = println("Week 3, Hello app.") }
– you can run it from the command line: scala Hello
– objects can be used as class companion / fabrics (later)

Exercise
– implement method union for IntSet
abstract class IntSet {
    def union(other: IntSet): IntSet
class Empty extends IntSet {
    def union(other: IntSet): IntSet = other
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
    def union(other: IntSet): IntSet =
        ((left union right) union other) incl elem
– dynamic programming: drill down to lesser problems until terminate

Dynamic binding
– dynamic method dispatch implementation in Scala
– runtime define actual method to call, depends on the runtime type of the object
– dynamic dispatch is analogous to calls to higher-order functions
– can we implement one concept in terms of the other?
yes, it's proven: Semantical Equivalence of Process Functional and Imperative Programs.

-- Lecture 3.2 - How Classes Are Organized
packages, imports, traits, objects, classes, Scala's class hierarchy,
exceptions, Nothing, Null, AnyVal, AnyRef, Any

Package
– Classes and objects are organized in packages
– at the top of your sorce file: package progfun.examples … object Hello { …
– fully qualified name: progfun.examples.Hello

Import, several forms
– import progfun.examples.Hello … Hello.someMethod()
– import all: import progfun.examples._
– import progfun.examples.{Hello, Rational}
– auto imported: scala._, java.lang._, scala.Predef._

Trait
– In Java, as well as in Scala, a class can only have one superclass
– you could use traits for inherit a subclass from several supertypes
– a trait is declared like an abstract class, just with 'trait' instead of 'abstract class'
trait Planar { def height: Int … 
class Square extends Shape with Planar with Movable ...
– classes, objects and traits can inherit from one class but many traits
– traits resemble interfaces in Java, but can contains fields and concrete methods
– traits cannot have (value) parameters, only classes can

Scala's class hierarchy
– scala.Any on top, AnyVal, AnyRef is a subclasses of Any
– scala.Nothing is a subclass of scala.Null
– AnyRef is an alias for java.lang.Object
– AnyVal: the base type of all primitive types
– Nothing: at the bottom of type hierarchy; no value of type Nothing
as an element type of empty collections
to signal abnormal termination
def err(msg: String): Nothing = throw new Error(msg) // it's type of expression that throw exception
– Null: every ref.class type also has null as a value
the type of null is Null

-- Lecture 3.3 — Polymorphism (Generics, example: immutable linked list)
polymorphism: subtyping; generics. Example: linked list

subtyping: instances of a subclass can be passed to a base class
– linked list constructed from two blocks: empty list = Nil; a cell with data and link = Cons
– list of integers (subtyping polymorphism)
trait IntList … 
class Nil extends IntList … 
class Cons(val head: Int, val tail: IntList) extends IntList ...
– note that we use: val head: Int – 'val' means that parameters becomes fields of a class
– it' too narrow, only for integers

generics (type parameter): instances are created by type parametrization
– we can generalize the definition using a type parameter
trait List[T] {
    def isEmpty: Boolean
    def head: T
    def tail: List[T] }
class Cons[T](val head: T, val tail: List[T]) extends List[T] {
    def isEmpty = false }
class Nil[T] extends List[T] {
    def isEmpty = true
    def head: Nothing = throw new NoSuchElementException("Nil.head")
    def tail: Nothing = throw new NoSuchElementException("Nil.tail") }
– like classes, functions can have type parameters
def singleton[T](elem: T) = new Cons[T](elem, new Nil[T])
singleton[Int](1)
in fact, Scala compiler smart enough, usually you can omit type parameter while calling such a function
singleton(1)

evaluation (type erasure)
– type parameters do not affect evaluation in Scala
– we can assume that all type parameters and type arguments are removed
before evaluating the program: it's called type erasure
– Java, Scala, Haskell, ML, OCaml, … : lang.that use type erasure
– C++, C#, F#, … : lang. that keep type parameters aroung at runtime

polymorphism
– in many forms
– the function can be applied to arguments of many types (generics), or
– the type can have instances of many types (subtyping)

Exercise: n-th element from list
def nth[T](n: Int, list: List[T]): T =
    if (list.isEmpty) throw new IndexOutOfBoundsException("n: " + n)
    else if (n == 0) list.head
    else nth(n - 1, list.tail)

Week 4: Types and Pattern Matching


-- Lecture 4.1 - Functions as Objects
function type, function value, methods

function type: class/trait
– The function type 'A => B' is just an abbreviation for the class
scala.Function1[A, B] like
trait Function1[A, B] { def apply(x: A): B }
– so functions are objects with 'apply' method
– there are also traits Function2, … Function22 (up to 22 params)

function value: call-by-value = instance of a func.class
– an anonymous function (x: Int) => x*x
is expanded to class instance
{ 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 call f(a, b) expanded to
f.apply(a, b)
// so 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 (not class m., just m.): call-by-name, 'def f(...' not expanded into a value immediately
– note that a method {def f(x: Int): Boolean = … } is not itself a function value
– only when method is used in a place where a Function type is expected,
it's converted to the function value (x: Int) => f(x) or, expanded
new Function1[Int, Boolean] { def apply(x: Int) = f(x) }
it's called: eta-expansion in lambda-calculus
A method can appear in an expression as an internal value (to be called with arguments)
but it can’t be the final value, while a function can:
//a simple method
scala> def m(x: Int) = 2*x
m: (x: Int)Int
//a simple function
scala> val f = (x: Int) => 2*x
f: (Int) => Int = <function1>
when a function is expected but a method is provided, it will be automatically converted into a function. This is called the ETA expansion.
A call by name parameter is just a method

Exercise: define object List { … } so that users can create lists
List(), List(1), List(2, 3)
object List {
    def apply[T](): List[T] = Nil
    def apply[T](x1: T): List[T] = new Cons(x1, Nil)
    def apply[T](x1: T, x2: T): List[T] = new Cons(x1, new Cons(x2, Nil))

-- Lecture 4.3 - Subtyping and Generics
The Barbara Liskov Substitution Principle (LSP, lsp).
Two forms of polymorphism (subtyping, generics);
bounds; variance/covariance.

The Liskov Substitution Principle
is a concept in OOP that states:
Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it.

interactions between subtyping and generics
– in two main areas: bounds and variance
– we need control over parameters types

bounds : define subset of allowed types (upper bounds, lower bounds)
– consider method: def assertAllPositive(s: IntSet): IntSet
– can one be more precise?
assertAllPos(Empty) = Empty 
assertAllPos(NonEmpty) = NonEmpty or throw new Error
– we want more control, be more precise for compile-time checks.
– lets say: Empty => Empty and NonEmpty => NonEmpty
– a way to express this is
def assertAllPos[S <: IntSet](r: S): S = ...
– here, ' <: IntSet' means: IntSet is an upper bound of the type parameter S
– it means that S can be instantiated only to types that conform to IntSet
– result wold be the same type as a paremeter
– in short: S <: T means: S is a subtype of T; S >: T means: S is a supertype of T
lower bounds: [S >: NonEmpty]
– only supertypes on NonEmpty allowed {NonEmpty, IntSet, AnyRef, Any}
– we will see later where lower bounds are useful
mixed bounds: [S >: NonEmpty <: IntSet]
– would restrict S any type on the interval between NonEmpty and IntSet

Covariance : is type of collection changes when changing type of items?
– consider this: if NonEmpty <: IntSet than is List[NonEmpty] <: List[IntSet] ?
– if this relation holds: types are covariant and we have compiler-time checks on types
because their (List) subtyping relationship varies with the type parameter
– what about Java Array? They are covariant and it's a failure
– why? because Array is mutable, that's why
NonEmpty[] a = new NonEmpty[]{new NonEmpty(...)}
IntSet[] b = a // lsp, ok 
b[0] = Empty // lsp?, but no, runtime error 
NonEmpty s = a[0] // covariance lead to NonEmpty = Empty?
– runtime error: Java check array items type in runtime
– for Java it was before generics, they want do things like 'sort(Array[] a)'
bottom line: covariance is good only if collection is immutable

LSP: if A <: B, then everything one can to do with a value of type B
one should also be able to do with a value of type A.
– arrays shouldn't be covariant
– in Scala arrays are not covariant
val a: Array[NonEmpty] = Array(new NonEmpty(...)) 
val b: Array[IntSet] = a // compile error, arrays are not covariant in Scala

-- Lecture 4.2 - Objects Everywhere
Scala is a pure OO language

– pure OO language: every value is an object
– language based on classes: type of each value is a class
– even primitive types
– how it can be done?

Exercise: pure OO boolean
abstract class Boolean {
  def IfThenElse[T](t: => T, e: => T): T
  def && (x: => Boolean): Boolean = ifThenElse(x, false) // if this: x else: false 
  def || (x: => Boolean): Boolean = ifThenElse(true, x) // if this: true else x
  def unary_!: Boolean = IfThenElse(false, true)
  def == (x: => Boolean): Boolean = ifThenElse(x, x.unary_!)
  def != (x: => Boolean): Boolean = ifThenElse(x.unary_!, x)
  def < (x: => Boolean): Boolean = ifThenElse(false, x)
…
object true extends Boolean { def ifThenElse[T](t: => T, e: => T) = t } // constant 'true'
object false extends Boolean { def ifThenElse[T](t: => T, e: => T) = e } // constant 'false'

Exercise: pure OO natural numbers, non-negative integers
abstract class Nat { // natural numbers >= 0
    def isZero: Boolean
    def predecessor: Nat
    def successor: Nat = new Succ(this)
    def +(that: Nat): Nat
    def -(that: Nat): Nat }
object Zero extends Nat {
    def isZero: Boolean = true
    def predecessor: Nat = throw new Error("Zero have not predecessors")
    def +(that: Nat): Nat = that
    def -(that: Nat): Nat =
        if (that.isZero) this
        else throw new Error("Zero minus Nat is negative") }
class Succ(n: Nat) extends Nat {
    def isZero: Boolean = false
    def predecessor: Nat = n
    def +(that: Nat): Nat = {
        new Succ(n + that) }
    def -(that: Nat): Nat =
        if (that.isZero) this
        else n - that.predecessor }

-- Lecture 4.4 - Variance (Optional)
interactions between subtyping and generics (polymorphism);
function variance (argument/result contravariant/covariant);
compiler-time type checks; lower bounds.

– a type that accept mutations of its elements should not be covariant
– but immutable types can be covariant, if some conditions on methods are met

3 sorts of variance: say we have C[T]; A <: B // A subtype of B
– covariant: C[A] <: C[B] // genericA subtype of genericB
– contravariant: C[A] >: C[B]
– nonvariant: neither is subtype
Scala annotations for variance
– covariant: class C[+A] …
– contravariant: class C[-A] …
– nonvariant: class C[A] …

function type variance : func. are contravariant in their argument types and covariant in their result type
– say we have two func.types
type A = IntSet => NonEmpty 
type B = NonEmpty => IntSet
– according to LSP, is A subtype of B? yes. why?
– answer: we can call A(new NonEmpty) but we can't call B(new IntSet)
– func.parameter should be supertype if func is subtype
– general rule says: for func.subtype func.params are contravariant
A1 => B1 <: A2 => B2
if A2 <: A1 and B1 <: B2
// so, function trait is 
trait Function1[-T, +U] { def apply(x: T): U } // compiler can check 
You should pass less specific param and return more specific result.

Exercise: how Java array covariance looks in Scala
class Array[+T] { def update(x: T) … } // covariance in method params 
Scala rules:
– covariant type params only in method results;
– contravariant … in method params;
– invariant … anywhere.

Exercise: covariant List
// make Nil an object
// type parameter Nothing as subtype of all types
// and make List covariance to pass type checks
object Nil extends List[Nothing] {
    def isEmpty = true
    def head: Nothing = throw new NoSuchElementException("Nil.head")
    def tail: Nothing = throw new NoSuchElementException("Nil.tail") }
// to do that (object Nil) we need to make List covariant

// make List covariant for accepting Nil as List
// Nil is subtype of List (thanks Nothing subtyping all)
trait List[+T] {
    def isEmpty: Boolean
    def head: T
    def tail: List[T]
…

Remember lower bounds? Let's see, why we need it
// prepend method 
trait List[+T] { def prepend(elem: T): List[T] = new Cons(elem, this) } 
// compiler error, covariant parameter in method 
// lsp violation: we can (if error supressed)
xs: List[IntSet]; xs.prepend(Empty) // ok with compiler 
ys: List[NonEmpty]; ys.prepend(Empty) // compiler error: type mismatch
// so, List[NonEmpty] can't be a subtype of List[IntSet] (covariant)
Enters lower bound
trait List[+T] {    
    // and applying lower bounds to type parameter we pass variance checking rule
    def prepend[U >: T](elem: U): List[U] = new Cons(elem, this)
…
def f(xs: List[NonEmpty], x: Empty): List[IntSet] = xs prepend x 
– covariant type params may appear in lower bounds of method type params
– contravariant t.p. may appear in upper bounds of method t.p.
Bottom line: static typing can be tricky.

Lecture 4.5 — Decomposition
pattern matching prerequisites: OO problems with decomposition


decomposition on example: interpreter for arithmetic expressions
– let's restrict to numbers and additions
– expressions can be represented as a class hierarchy: trait Expr, class Number, class Sum
– it's necessary to know the expression's shape and its components
trait Expr {
  def isNumber: Boolean 
  def isSum: Boolean 
  def numValue: Int 
  def leftOp: Expr 
  def rightOp: Expr }
class Number(n: Int) extends Expr {
  def isNumber: Boolean = true
  def isSum: Boolean = false
  def numValue: Int = n
  def leftOp: Expr = throw new Error(«Number.leftOp»)
  def rightOp: Expr = throw new Error(«Number.rightOp») }
class Sum(e1: Expr, e2: Expr) extends Expr {
  def isNumber: Boolean = false
  def isSum: Boolean = true
  def numValue: Int = throw new Error(«Sum.numValue»)
  def leftOp: Expr = e1
  def rightOp: Expr = e2 }

#1: evaluation of expressions: classification and access methods
def eval(e: Expr): Int = { if(e.isNumber) e.numValue
  else if(e.isSum) eval(e.leftOp) + eval(e.rightOp)
  else throw new Error(«Unknown expr » + e) }
– problem: quickly becomes tedious
– worse: if you want to add new expression forms, say
class Prod(e1: expr, e2: Expr) extends Expr // e1 * e2 
class Var(x: String) extends Expr // Variable 'x'
you need to rewrite all classes, adding quadratic number of methods => bad solution
classification and access methods: quadratic explosion.

#2: a non-solution: use type tests and type casts:
def isInstanceOf[T]: Boolean
def asInstanceOf[T]: T
def eval(e: Expr): Int = if(e.isInstanceOf[Number] e.asInstanceOf[Number].numValue 
  else if(e.isInstaceOf[Sum]) …
  else throw new Error(«Unknown expr » + e)
unsafe, low-level.

#3: OO decomposition, move eval into Expr subtypes
trait Expr { def eval: Int 
class Number(n: Int) extends Expr { def eval: Int = n }
class Sum(e1: Expr, e2: Expr) extends Expr {
  def eval: Int = e1.eval + e2.eval }
– not so good: if we want to extend (say, display expressions), we need to rewrite all methods
– and what if we want all chain, say, for simplification, like a*b + a*c => a*(b+c)
this is a non-local simplification, it can't be encapsulated in the method of a subclass
back to square one: you need test and access methods for all subclasses

Enters Pattern Matching.

-- Lecture 4.6 - Pattern Matching / algebraic datatypes
if you need test and access methods for all different subclasses;
we need general and convinient way to access objects in a extensible class hierarchy

solution: functional decomposition with pattern matching
– observation: test and accessor functions do reverse the construction process
which subclass?
what were the arguments?
– many func.languages automate it

case class : like a normal class
trait Expr 
case class Number(n: Int) extends Expr 
– it implicitly defines companion objects with 'apply' methods
object Number { def apply(n: Int) = new Number(n) }
so you can write 'Number(1)' instead of 'new Number(1)'

pattern matching is a generalization of 'switch' from C/Java to class hierarchies
– expressed using the keyword 'match'
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 sequence of 'case's: pat => expr
– each case associates an expression expr with a pattern pat
– if no pattern matches the value, a MatchError exception is thrown
patterns
– constructors: Number, Sum
– variables: n, e1
– wildcard patterns: '_'
– constants: 1, true
variables always begin with a lowercase letter
– the same variable name can only appear once in a pattern
Sum(x, x) is not a legal pattern
– names of constants begin with a capital letter (exception: null, true, false)

evaluating match expressions
– an expression of the form 'e match { case p1 => e1 … case pn => en }
– matches the value of the selector 'e' with the patterns p in the order in which they are written
– the whole match expression is rewritten to the right-hand side of the first case where the pattern mathes
– references to pattern variables are replaced by the corresponding parts in the selector

what do patterns match
– constructor pattern 'C(p1...pn)': matches all the values of type 'C' or a subtype
that have been constructed with matched arguments
– variable pattern 'x': matches any value and binds the name to this value
– constant pattern 'c': matches values that are equal to 'c'

Exercise : representation of a given expression
def show(e: Expr): String = e match {
  case Number(x) => x.toString
  case Sum(e1, e2} => show(e1) + « + » + show(e2) }

-- Lecture 4.7 — Lists
immutable collection; list is recursive, homogeneous;
cons operation '::' right assotiativity; based on (head, tail, isEmpty);
list pattern matching; list insertion sort;

Example
– List('apples', 'oranges')
– List(List(1,0,0), List(0,1,0))

list vs. array
– lists are immutable
– lists are recursive (arrays are flat)
– lists and arrays are homogeneous: elements must all have the same type
List[T]: val nums: List[Int] = List(1,2,3)

list construction
– 1. from the empty list 'Nil' and
– 2. the construction 'cons' operation '::' x :: xs
– cons is right-associative: 'A :: B :: C' == 'A :: (B :: C)' (like a foldRight or func.types)
– in fact, operators ending in ':' associate to the right (as func.types do: 'Int => Int => Int' == 'Int => (Int => Int)')
– also, ops ending in ':' are seen as method calls of the right-hand operand: x :: xs == xs.cons(x)
consider this: x :: xs == xs.prepend(x)

basic operations, all ops on lists can be expressed in terms of
– head: the first element
– tail: list of all elems except the head
– isEmpty: true if list is empty

list patterns matching
– Nil -- Nil
– p :: ps -- head p and a tail ps
– List(p1, …, pn) -- same as p1 :: … :: pn :: Nil
example
– 1 :: 2 :: xs -- list 1,2
– x :: Nil -- list of length 1
– List(x) -- same as x :: Nil
– List() – the empty list, Nil
– List(2 :: xs) – list length 1, item is a list 2 :: xs
– x :: y :: List(xs, ys) :: zs – list length >= 3 (zs may be Nil)

insertion sort : sort a list (time N .. N^2)
– 1. sort the tail
– 2. insert head in the right place
def isort(xs: List[Int]): List[Int] = xs match {
  case List() => List()
  case y :: ys => insert(y, isort(ys)) }
def insert(x: Int, xs: List[Int]): List[Int] = xs match {
  case List()  => List(x)
  case y :: ys => if (x <= y) x :: xs else y :: insert(x, ys) }

Week 5: Lists


Lecture 5.1 - More Functions on Lists
fp list processing

list methods : implement this using basics (head, tail, isEmpty)
– length
– last
– init : all elements but last one
– take(n) first n elements
– drop(n) all but first n
– apply(n) n-th element
– xs ++ ys: all from xs followed by all from ys
– reverse : elements in reversed order
– indexOf(x)
– contains(x)

last: complexity
– time: N
def last[T](xs: List[T]): T = xs match {
  case List() => throw new Error(«last of empty list»)
  case List(x) => x
  case y :: ys => last(ys) }
// exercise: init
def init[T](xs: List[T]): List[T] = xs match {
  case List() => throw new Error(«init of empty list»)
  case List(x) => List()
  case y :: ys => y :: init(ys) }

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

reverse
def reverse[T](xs: List[T]): List[T] = xs match {
  case List() => List()
  case y :: ys => reverse(ys) ++ List(y) }
// time N^2: n times reverse * n times concat 

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

flatten : matching types
def flatten(xs: List[Any]): List[Any] = xs match {
    case Nil => Nil
    case head :: tail => (head match {
        case x: List[Any] => flatten(x)
        case y            => List(y)
    }) ::: flatten(tail) }

-- Lecture 5.2 - Pairs and Tuples / list mergesort
take a look to tuples : list mergesort

mergesort idea
– if list.size <= 1: it's sorted, else
– list.split
– firsthalf.sort; secondhalf.sort
– merge(firsthalf, secondhalf) // nested match, no good
def msort(xs: List[Int]): List[Int] = {
    val n = xs.length / 2
    if (n == 0) xs
    else {
        val (fst, snd) = xs splitAt n
        merge(msort(fst), msort(snd)) }}
def merge(xs: List[Int], ys: List[Int]): List[Int] = xs match {
    case Nil => ys
    case x :: xs1 => ys match {
        case Nil => xs
        case y :: ys1 => {
            if (x < y) x :: merge(xs1, ys)
            else y :: merge(xs, ys1) }}}
splitAt returns two sublists, in a pair : tuple => (a, b)

tuple (used in maps, see later)
val pair = («answer», 42) // type is (String, Int)
val (label, value) = pair // pattern 
– tuple type: scala.Tuplen[T1, …, Tn] is a parametrized type
– tuple expression: scala.Tuplen(e1, …, en) is a function application
– tuple pattern scala.Tuplen(p1, …, pn) is a constructor pattern
– model : using '_1', '_2', ...
case class Tuple2[T1, T2](_1: +T1, _2: +T2) { … }

merge using tuples
def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {
    case (Nil, ys) => ys
    case (xs, Nil) => xs
    case (x :: xs1, y :: ys1) => {
        if (x < y) x :: merge(xs1, ys)
        else y :: merge(xs, ys1) }}

-- Lecture 5.3 - Implicit Parameters / general sort
sort lists of any type : parameterize 'merge' with the comparison function

make the function 'sort' polymorphic and pass the comparison operation as
an additional parameter
def msort[T](xs: List[T])(less: (T, T) => Boolean) = {
  …
  merge(msort(fst)(less), msort(snd)(less)) }
// apply 
msort(nums)((x: Int, y: Int) => x < y)
// or, if 'less' is internal, Scala can inference types 
msort(nums)((x, y) => x < y)
// or, you can use standard ordering 
import math.Ordering
msort(nums)(Ordering.Int)

implicit parameters
– we can avoid passing 'less' around
def msort[T](xs: List[T])(implicit ord: Ordering) = … 
  if(ord.lt(x, y)) … 
  merge(msort(fst), msort(snd)) 
...
msort(nums)
– compiler will figure out the right implicit to pass based on the demanding type

implicit rules :
function takes implicit parameter of type T, compiler will search an implicit definition that
– is marked 'implicit'
– has a type compatible with T
– is visible at the point of the function call, or is defined in a companion object associated with T
– if there is a single (most specific) definition, it will be taken as actual argument
– otherwise: error

-- Lecture 5.4 - Higher-Order List Functions
recurring patterns for computations on lists (map, filter, reduce)

recurring patterns
– transforming each element
– retrieving a list of items satisfying a criterion
– combining the elements using an operator
FP allow to implement patterns using higher-order functions

applying a function to each element: map
– transfor each element and return list of results
– example: multiply by factor
def scaleList(xs: List[Int], factor: Int): List[Int] = xs match {
  case Nil => xs
  case y :: ys => y*factor :: scaleList(ys, factor)}
– lets generalize
abstract class List[T] { ... 
    def map[U](f: T => U): List[U] = this match {
        case Nil     => this
        case x :: xs => f(x) :: xs.map(f) }
// usage 
def scaleList(xs: List[Int], factor: Int) = xs map(x => x*factor)

retrieving a filtered list: filter
– select items satisfying a given condition
def posElems(xs: List[Int]): List[Int] = xs match {
    case Nil        => xs 
    case y :: ys    => if(y > 0) y :: posElems(ys) else posElems(ys) }
– filter method
abstract class List[T] { ...
    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) }
// usage 
def posElems(xs: List[Int]): List[Int] = xs.filter(x => x > 0)
filter variations
– xs.filterNot p : filter with predicate '!p(x)'
– xs partition p : same as (xs.filter p, xs.filterNot p)
– xs.takeWhile p : longest prefix of list consisting of items that satisfy the predicate
– xs.dropWhile p : the remainder of the list after any leading items satisfying 'p' have been removed
– xs.span p : same as (xs.takeWhile p, xs.dropWhile p)

Exercise
// function that pack consecutive duplicates of list into sublists
// (a, a, a, b, c, c, a) => (a, a, a), (b), (c, c), (a)
def pack[T](xs: List[T]): List[List[T]] = xs match {
    case Nil => Nil
    case head :: tail => {
        val (first, rest) = xs.span(y => y == head)
        first :: pack(rest) }}
// encode duplicates, item x => (x, count)
// (a, a, a, b, c, c, a) => (a, 3), (b, 1), (c, 2), (a, 1)
def encode[T](xs: List[T]): List[(T, Int)] =
    pack(xs) map (ys => (ys.head, ys.length))

-- Lecture 5.5 - Reduction of Lists
recurring patterns for computations on lists (map, filter, reduce/fold);
unit value

we can have operators between adjacent elements of a list
combine elements of a list using given operator (and accumulator)
– sum(List(...)) = 0 + x1 + x2 …
– product(List(...)) = 1 * x1 * x2 …
unit value: 0 for sum, 1 for product
pattern
def sum(xs: List[Int]): Int = xs match {
    case Nil => 0
    case y :: ys => y + sum(ys) }

generalization
reduceLeft: associates to left using given binary operator
List(x1, …, xn) reduceLeft op = ( … ((x1 op x2) op x3) … ) op xn
def sum(xs: List[Int]) = (0 :: xs) reduceLeft ((x,y) => x+y)
def product(xs: List[Int]) = (1 :: xs) reduceLeft ((x,y) => x*y)
by the way, Scala have some shugar: '_'
– every '_' represents a new parameter, going from left to right
– the parameters are defined at the next outer pair of parentheses, so
def sum(xs: List[Int]) = (0 :: xs) reduceLeft (_ + _)
def product(xs: List[Int]) = (1 :: xs) reduceLeft (_ * _)

foldLeft: more general function, takes accum and operator
(List(x1, …, xn) foldLeft acc)(op) = (… (acc op x1) op …) op xn
def sum(xs: List[Int]) = (xs foldLeft 0) (_ + _) // fold with a + and unit value 0
def product(xs: List[Int]) = (xs foldLeft 1) (_ * _)

fold/reduce left implementation
– it is a classic loop with accumulator, tail-call
abstract class List[T] { ...
    def reduceLeft(op: (T, T) => T): T = this match {
        case Nil        => throw new Error("Nil.reduceLeft")
        case x :: xs    => (xs foldLeft x)(op) }
    def foldLeft[U](acc: U)(op: (U, T) => U): U = this match {
        case Nil        => acc
        case x :: xs    => (xs foldLeft op(acc, x))(op) }}
// produces left-leaning operation tree
(List(a,b,c) foldLeft acc)(op) = op(op(op(acc,a), b), c)
        op
        /\
      op  c
      /\
    op  b
    /\
  acc a
– they have two dual functons

fold/reduce right : produce trees which lean to the right
– List(a, b, c) reduceRight op = a op (b op c)
– List(a, b, c) foldRight acc)(op) = a op (b op (c op acc))
– drill to tail and fold back to head : recursive loop
abstract class List[T] { ...
    def reduceRight(op: (T, T) => T): T = this match {
        case Nil        => throw new Error("Nil.reduceRight")
        case x :: Nil   => x
        case x :: xs    => op(x, xs.reduceRight(op)) }
    def foldRight[U](acc: U)(op: (T, U) => U): U = this match {
        case Nil        => acc
        case x :: xs    => op(x, (xs foldRight acc)(op)) }}
// compare to foldLeft
// case x :: xs    => (xs foldLeft op(acc, x))(op)

// right-leaning tree
List(a, b, c) foldRight acc)(op) = a op (b op (c op acc))
 op
 /\
a  op
   /\
  b  op
     /\
    c acc

foldLeft vs foldRigh
– they are equivalent (except efficiency) for operators that are associative and commutative
foldRigh is good for concat: def concat[T](xs: List[T], ys: List[T]): List[T] = (xs foldRight ys) (_ :: _)
foldLeft wouldn't do: the types would not work out: (item :: list => list.binary_::(item))

-- Lecture 5.6 - Reasoning About Concat / proof of correctness
natural induction, structural induction : optional

How can we proof that definitions satisfy certain laws, represented as equalities between terms?
e.g. concat properties (Nil: neutral element; ++ is assotiative)
– Nil ++ xs = xs
– xs ++ Nil = xs
– (xs ++ ys) ++ zs = xs ++ (ys ++ zs)
how can we prove it?
– enters structural induction
– but lets start with natural induction first

natural induction principle: base case … induction step
– property P(n) for all int n >= b
– base case: show that we have P(b)
– induction step: for all n >= b show that if P(n): P(n+1)

natural induction example
– show that, for all n >= 4 factorial(n) >= power(2, n)
def factorial(n: Int): if (n == 0) 1 else n*factorial(n-1) // 1st and 2nd clause
– base case: factorial(4) = 24 >= power(2, 4) = 16 // true
– induction step: n+1 for n >= 4
factorial(n+1)
>= (n+1) * factorial(n)
> 2 * factorial(n) // n+1 > 2 == 5 > 2
>= 2 * power(2, n) // by induction hypothesis
= power(2, n+1) // by def.of power

referential transparency
– note that a proof can freely apply reduction steps as equalities to some part of a term
– that works because pure func.programs don't have side effects

structural induction
– the principle of structural induction is analogous to natural induction
– to prove a property P(xs) for all lists xs : show base case; induction step
– base case: show that P(Nil) holds
– induction step: for a list xs and some element x, show: if P(xs) holds, then P(x :: xs) also holds

example: show that (xs ++ ys) ++ zs = xs ++ (ys ++ zs)
def concat[T](xs: List[T], ys: List[T]) = xs match {
    case List() => ys
    case x :: xs1 => x :: concat(xs1, ys) }
– two clauses
Nil ++ ys = ys
(x :: xs1) ++ ys = x :: (xs1 ++ ys)
– base case: Nil
(Nil ++ ys) ++ zs // left-hand
= ys ++ zs // first clause
Nil ++ (ys ++ zs) // rigth-hand
= ys ++ zs // first clause
base case established
– induction step: left-hand side
((x :: xs) ++ ys) ++ zs
= (x :: (xs ++ ys)) ++ zs // 2nd clause
= x :: ((xs ++ ys) ++ zs // 2nd clause
= x :: (xs ++ (ys ++ zs)) // induction hypothesis
– induction step : right-hand side
(x :: xs) ++ (ys ++ zs)
= x :: (xs ++ (ys ++ zs)) // 2nd clause
case/property is established

-- Lecture 5.7 - A Larger Equational Proof on Lists
structural induction for xs.reverse.reverse = xs

Nil.reverse = Nil // 1st clause
(x :: xs).reverse = xs.reverse ++ List(x) // 2nd clause

base case: Nil
Nil.reverse.reverse
= Nil.reverse // 1st clause
= Nil

induction step: (x :: xs).reverse.reverse = x :: xs
– left-hand
(x :: xs).reverse.reverse
= (xs.reverse ++ List(x)).reverse // 2nd clause
– right-hand
x :: xs
= x :: xs.reverse.reverse // induction hypothesis
– we need to generalize the equation: (ys ++ List(x)).reverse = x :: ys.reverse
for any list ys
this equation can be proven by a second induction argument on ys;
fold/unfold method... skip.

Week 6: Collections


-- Lecture 6.1 - Other Collections
vector, list, string, sequence, …

list: access to the first element is much faster than access to the middle or end

vector: up to 32 elements is just array, access is O(1) .. O(log_32 N)
– if more than 32: it's 32 pointers to 32 vectors in 2nd layer (B-tree like)
– layers capacity: 2^5 = 32, 2^10 = 1024, 2^15 = 32768, …
– good for batch/bulk processing
– operations
val nums = Vector(1, 2, 3)
val people = Vector('Bob','James')
// add item to vector, no Cons ::, instead 
x +: xs
xs :+ x
– add item to vector, O(log32 N), create one new block for each layer

collection hierarchy
– Seq(Iterable); Set(Iterable); Map(Iterable)
– List(Seq); Vector(Seq)
– Arrays, Strings: come from Java, support the same ops as Seq;
can be implicitly converted to sequence
val xs = Array(1,2,3)
xs map (x => x*2) 
val s = "Hello Word"
s filter (c => c.isUpper)

range: sequence
– ops: 'to', 'until', 'by'
val r: Range = 1 until 5 // 1, 2, … 4
val rr = 6 to 1 by -2 // 6, 4, 2
– single object with 3 fields: lower bound, upper bound, step

sequence ops
– xs exists p
– xs forall p
– xs zip ys = sequence of pairs
– xs.unzip = split into two seq.
– xs flatMap f = applies collection-valued function 'f' to all elements of xs and concat. the results
– xs.sum ; xs.product ; max; min; …

examples
// to list all combinations of numbers x, y
(1 to X) flatMap (x => (1 to Y) map (y => (x,y)))
// scalar product of two vectors
def scalarProduct(xs: Vector[Int], ys: Vector[Int]): Int = 
    (xs zip ys).map(xy => xy._1 * xy._2).sum
// or
def scalarProduct(xs: Vector[Int], ys: Vector[Int]): Int =
    (xs zip ys).map{ case(x,y) => x*y }.sum
// { case ... } = x => x match { case ... }

// a number is prime if the only divisors of n are 1 and n itself 
def isPrime(n: Int): Boolean = (2 until n) forall (d => n % d != 0)

-- Lecture 6.2 - Combinatorial Search and For-Expressions
nested loops applications

example: given n > 0, find all pairs i,j with 1 <= j < i < n such that i+j is prime
– natural solution: create the seq. of all pairs (i, j) 1 <= j < i < n and filter for i+j is prime
– is = 1 until n; js = 1 until i
– but there's a rub : result is seq. of sequences, we need seq. of pairs
val n = 7                                    
val xss = (1 until n) map (i => (1 until i) map (j => (i, j)))
// Vector(Vector(), Vector((2,1)), Vector((3,1), (3,2)), Vector((4,1), (4,2), (4,3)), ...
– lets flatten nested sequence
val fr = (xss foldRight Seq[(Int, Int)]())(_ ++ _)
// Vector((2,1), (3,1), (3,2), (4,1), (4,2), (4,3), ...
val fl = (xss foldLeft Seq[(Int, Int)]())(_ ++ _)
// List((2,1), (3,1), (3,2), (4,1), (4,2), (4,3), ...
val flat = xss.flatten
// Vector((2,1), (3,1), (3,2), (4,1), (4,2), (4,3), ...

val fm = (1 until n) flatMap (i => (1 until i) map (j => (i, j)))
// Vector((2,1), (3,1), (3,2), (4,1), (4,2), (4,3), …
val primePairs = fm filter (pair => isPrime(pair._1 + pair._2))
– xs flatMap f = (xs map f).flatten
– and filter : val primeSum = fm filter (pair => isPrime(pair._1 + pair._2))
– can we do this by more simple way?

Enters For-Expression
– for-expr. solution
val forE = for {
    i <- 1 until n
    j <- 1 until i
    if isPrime(i + j)
} yield (i, j)
– the for-expression is similar to loops in imperative languages, except
that it builds a list of the results of all iterations
– find all persons over 20
for(p <- persons if p.age > 20) yield p.name ==
persons filter (p => p.age > 20) map (p => p.name)
– a for-expression is of the form: 'for(s) yield e'
– '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 be used

exercise
def scalarProduct(xs: List[Double], ys: List[Double]): Double = {
    val pairs = xs zip ys
    val prods = for {
        (x, y) <- pairs
    } yield x * y
    prods sum }

-- Lecture 6.3 - Combinatorial Search Example
set, N-Queens puzzle

set: another basic abstraction
– val s = (1 to 6).toSet; val fruit = Set('apple')
– most ops on sequences are also available on sets
– sets are unordered
– sets do not have duplicate elements
– the fundamental operation on sets is 'contains' // hash? bst?

N-Queens : combinatorial search problem
– problem is to place n queens on a chessboard so that no queen is threatened by another
– there can't be two queens in the same row, column, or diagonal
– place k-th queen in a k-th row in a column where it's not 'in check' with any other q.
– we have set of solutions (set of lists)
– list: column number for each row
– generate all possible extensions of each solution
– recursive algorithm
def solveQueens(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
    queensWithRow forall {
        case (r, c) => col != c && math.abs(col - c) != row - r }}
// print 
def show(queens: List[Int]) = {
    val lines = for (col <- queens.reverse)
        yield Vector.fill(queens.length)("* ").updated(col, "X ").mkString
    "\n" + (lines mkString "\n") }
(solveQueens(8) take 3 map show) mkString "\n"

-- Lecture 6.4 - Queries with For
BD query model

for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title
// transforms to:
books.flatMap { b =>
    b.authors.withFilter { a =>
        a.startsWith("Bird")
    } map (a => b.title) }

author with at least 2 books
for {
    b1 <- books 
    b2 <- books 
    if b1.title < b2.title 
    a1 <- b1.authors 
    a2 <- b2.authors 
    if a1 == a2 
} yield a1
// or, better 
{ for {
    b1 <- books 
    b2 <- books 
    if b1.title < b2.title 
    a1 <- b1.authors 
    a2 <- b2.authors 
    if a1 == a2 
} yield a1 }.distinct // remove duplicates 

-- Lecture 6.5 - Translation of For
For-Expression in terms of: map/flatMap and filter

upside-down
def map[T, U](xs: List[T], f: T => U): List[U] =
    for(x <- xs) yield f(x)
def flatMap[T, U](xs: List[T], f: T => Iterable[U]): List[U] =
    for(x <- xs; y <- f(x)) yield y
def filter[T](xs: List[T], p: T => Boolean): List[T] =
    for(x <- xs if p(x)) yield x

in reality it goes other way, compiler rewrite FE to
for(x <- e1) yield e2 =
    e1.map(x => e2)

// f is a filter; s is a sequence of generators and filters
for(x <- e1 if f; s) yield e2 =
    for(x <- e1.withFilter(x => f); s) yield e2
...

for(x <- e1; y <- e2; s) yield e3 =
    e1.flatMap(x => for(y <- e2; s) yield e3
…
// example 
for { i <- 1 until n
    j <- 1 until i
    if isPrime(i+j)
} yield (i, j) 
=
    (1 until n).flatMap(i => (1 until i)
        .withFilter(j => isPrime(i+j))
        .map(j => (i, j)))
bottom line: if (map, flatMap, withFilter) defined for datatype, For-Expression can be used.
– xml, db, parsers, optional data, etc.
– DB: ScalaQuery, Slick / MS LINQ uses that idea

-- Lecture 6.6 - Maps
collection type: map = key-value collections. hash? bst?

Map[Key, Value] associates keys with values (tuple k,v)
val romanNumerals = Map('I' → 1, 'V' → 5)
– maps are iterables, support collection ops
– the syntax 'key → value' = '(key, value)'
– maps are (partial) functions, extends the type 'Key => Value'
m.get // total function
capitals("Andorra") // NoSuchElementException: key not found 
capitals get "Andorra" // res0: Option[String] = None 
capitals get "US" // Some("Washington")
– Option value as a result of getting no-key

Option type : useful with pattern matching (Some / None)
trait Option[+A] // covariant 
case class Some[+A](value: A) extends Option[A] 
object None extends Option[Nothing]

def showCap(country: String) = capitals.get(country) match {
    case Some(cap) => cap 
    case None => "n/a" }

orderBy, groupBy: useful ops
– sortWith, sorted
fruit.sortWith(_.length < _.length) // short .. long 
fruit.sorted // natural order 
– groupBy: partitions a collection into a map of collections according to a
discriminator function f
fruit groupBy(_.head) // Map('p' -> List('pear', 'pineapple'), 'a' -> List('apple'))

Example: polinomials
– a polinomial can be seen as a map from exponents to coefficients
– x^3 — 2x + 5 → Map(0 → 5, 1 → -2, 2 → 0, 3 → 1)
class Poly(terms0: Map[Int, Double]) { // exp -> coeff
    def this(args: (Int, Double)*) = this(args.toMap) // seq. of pairs
    val terms = terms0 withDefaultValue 0.0 // unknown exp return coeff = 0.0
// w/o def.val we have to apply case Some/None

    def +(other: Poly) = { plus2(other) }

    def plus2(other: Poly) = { // final version, tail-call
        new Poly((other.terms foldLeft terms)(addTerm)) }
        
    def addTerm(terms: Map[Int, Double], term: (Int, Double)) = {
        val (e1, c1) = term
        val (e2, c2) = (e1, terms(e1))
        val (exp, coeff) = (e2, c2 + c1)
        terms + (exp -> coeff) }

    override def toString =
        (for ((e, c) <- terms.toList.sorted.reverse) yield c + "x^" + e) mkString " + "
}
val p1 = new Poly(1 -> 2.0, 3 -> 4.0, 5 -> 6.2)
val p2 = new Poly(0 -> 3.0, 3 -> 7.0)
p1 + p2
– map(key) is a partial function: could lead to an exception
– operation 'withDefaultValue' that turns a map into a total function
// first version, using concat
def plus1(other: Poly) = {
    new Poly(terms ++ (other.terms map adjust)) }
def adjust(term: (Int, Double)): (Int, Double) = {
    val (e1, c1) = term
    val (e2, c2) = (e1, terms(e1))
    (e2, c2 + c1) }

-- Lecture 6.7 - Putting the Pieces Together
larger example, all about sequences

Paper: An empirical comparison of C, C++, Java, Perl, Python, Rexx, and Tcl
by Lutz Prechelt

Task: convert telephone numbers to sentences
val mnemonics = Map('2' → 'ABC', '3' → 'DEF', ...)
Assume you are given a dictionary words as a list of words.
Design a method 'translate' such that translate(phoneNumber)
produces all phrases of words that can serve as mnemonics for the phone number.
Example: '7225247386' should have the mnemonics 'Scala is fun' as one element of the set.

import scala.io.Source
val in = Source.fromURL("http://lamp.epfl.ch/files/content/sites/lamp/files/teaching/progfun/linuxwords.txt")

/* create a list and filter out all words where *all* their characters are not letters (like dashes) */
val words = in.getLines.toList filter (word => word forall (chr => chr.isLetter))

/* define the map of numbers to letters */
val mnem = Map('2' -> "ABC", '3' -> "DEF", '4' -> "GHI", '5' -> "JKL", '6' -> "MNO", '7' -> "PQRS", '8' -> "TUV", '9' -> "WXYZ")

/* invert the mnem map the give a map from char to digit */
val charCode: Map[Char, Char] = for ((digit, str) <- mnem; ltr <- str) yield ltr -> digit

/* maps a word to the digit string, e.g. Java → 5282 */
def wordCode(word: String): String = word.toUpperCase map charCode

/* group all words of our long list with the same number, e.g. 5282 → List(Java, Kata, ...) */
val wordsForNum: Map[String, Seq[String]] = words groupBy wordCode withDefaultValue Seq()

def encode(number: String): Set[List[String]] =
    if (number.isEmpty) Set(List())
    else {
        for {
            split <- 1 to number.length // iterate over the number
            word <- wordsForNum(number take split) // get the word before the spilt
            rest <- encode(number drop split) //get the words after the split
        } yield word :: rest // join the results
    }.toSet

def translate(number: String): Set[String] = encode(number) map (_ mkString " ")
translate("7225247386") foreach println
bottom line: Scala's immutable collections are
– easy to use; concise; safe; fast; universal

Week 7: Lazy Evaluation


-- Lecture 7.1 - Structural Induction on Trees / Set
prove properties about programs : Set contains x

Structural induction is not limited to lists; it applies to any tree structure.
General principle : to prove a property P(t) for all trees 't' of a certain type
– show that P(leaf) holds for all leaves 'leaf' of a tree
– for each type of internal node 't' with subtrees s1,...,sn, show that
P(s1) ^...^P(sn) implies P(t)

Interesting fact about IntSet (it's a BST, remember?)
abstract class IntSet { def incl(x: Int): IntSet; def contains(x: Int): Boolean }
class Empty extends IntSet { def contains(x: Int) = false
  def incl(x: Int) = new NonEmpty(x, new Empty, new Empty) }
class NonEmpty(elem: Int, left: IntSet, right: IntSet) extends IntSet {
    def contains(x: Int): Boolean =
        if (x < elem) left contains x
        else if (x > elem) right contains x
        else true
    def incl(x: Int): IntSet =
        if (x < elem) new NonEmpty(elem, left incl x, right)
        else if (x > elem) new NonEmpty(elem, left, right incl x)
        else this }
– invariant: elements are ordered
– we want prove that this implementation is correct
– we have 3 laws: for any set 's' and items 'x' and 'y'
Empty contains x = false
(s incl x) contains x = true
(s incl x) contains y = s contains y if x != y
Can we prove these laws?

proposition 1. Empty contains x = false
– proof: according to the definition of Empty.contains
proposition 2. (s incl x) contains x = true
– structural induction on 's', base case: Empty
(Empty incl x) contains x 
= NonEmpty(x, Empty, Empty) contains x) // def Empty.incl 
= true // def NonEmpty.contains 
– Induction step: NonEmpty(z, l, r)
two cases: z = x, z != x 
(NonEmpty(x, l, r) incl x) contains x 
= NonEmpty(x, l, r) contains x // def NonEmpty.incl 
= true // def NonEmpty.contains
– Induction step: NonEmpty(y, l, r) where y < x (or y > x)
(NonEmpty(y, l, r) incl x) contains x 
= NonEmpty(y, l, r incl x) contains x // or 'l incl x' if y > x, def NonEmpty.incl
= (r incl x) contains x // def NonEmpty.contains 
= true // induction hypothesis 
proposition 3. if x != y : (xs incl y) contains x = xs contains x
– structural induction on 's'. Assume that y < x (y > x is symmetrical)
– base case: Empty
(Empty incl y) contains x 
= NonEmpty(y, Empty, Empty) contains x // def Empty.incl 
= Empty contains x // def NonEmpty.contains 
– Induction step: a tree NonEmpty(z, l, r); We distinguish five cases
z = x 
z = y 
z < y < x 
y < z < x 
y < x < z
– first two are easy
// z = x, z = y 
(NonEmpty(x, l, r) incl y) contains x 
= NonEmpty(x, l incl y, r) contains x // def NonEmpty.incl 
= true // def NonEmpty.contains 
(NonEmpty(y, l, r) incl y) contains x
= NonEmpty(y, l, r) contains x // def NonEmpty.incl 
= false
… etc, skip

-- Lecture 7.2 - Streams
lazy lists: tail evaluated only on demand, elegant solution to search problems

example: find the second prime number between 1000..10000
// it's short all right, but can you see computational complexity?
((1000 to 10000) filter isPrime)(1)
// it constructs all prime numbers between 1000...10000 in a list, but only ever looks at the first two 

// it's efficient, but ugly:
def secondPrime(from: Int, to: Int) = nthPrime(from, to, 2)
def nthPrime(from: Int, to: Int, n: Int): Int = 
    if(from >= to) throw new Error("no prime")
    else if(isPrime(from)) 
        {if(n == 1) from else nthPrime(from+1, to, n-1}
    else nthPrime(from+1, to, n)

delayed evaluation
– avoid computing the tail of a sequence until it's needed for the evaluation result
– this idea is implemented in a 'Stream' class
– streams are similar to lists, but their tail is evaluated only on demand

Stream
– defined from a constant 'Stream.empty' and a constructor 'Stream.cons'
val xs = Stream.cons(1, Stream.cons(2, Stream.empty))
– or using object factory
val xs = Stream(1, 2, 3)
– or using collection 'toStream'
val xs = (1 to 1000).toStream
– stream supports almost all methods of list
x :: xs always produces a list, never a stream
– x #:: xs == Stream.cons(x, xs) // can be used in expressions and patterns

Example: stream range
def streamRange(lo: Int, hi: Int): Stream[Int] = 
    if(lo >= hi) Stream.empty 
    else Stream.cons(lo, streamRange(lo+1, hi))
// isomorphic func. for list 
def listRange(lo: Int, hi: Int): List[Int] = 
    if(lo >= hi) Nil
    else lo :: listRange(lo+1, hi)
– list will be built immediately
– stream will create head and delay creating tail

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

Stream implementation
trait Stream[+A] extends Seq[A] { // covariant 
    def isEmpty: Boolean 
    def head: A 
    def tail: Stream[A] 
    ... }
– quite close to the one of lists
– all other methods can be defined in terms of these three
– stream companion object (see CBN tail?):
object Stream {
    def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] { // lazy tail
        def isEmpty = false; def head = hd; def tail = tl}
    val empty = new Stream[Nothing] {
        def isEmpty = true; def head = throw new Error ... }}
// other methods like in list 
class Stream[+T] { // covariant 
    def filter(p: T => Boolean): Stream[T] = 
        if(isEmpty) this 
        else if (p(head)) cons(head, tail.filter(p)) // lazy tail 
        else tail.filter(p) }

-- Lecture 7.3 - Lazy Evaluation
do things as late as possible and never do them twice

Stream didn't cache:
– if tail is called several times, the corresponding stream will be recomputed each time
– problem can be avoided by storing the result of the first evaluation
– in purely func.languages an expression produces the same result each time

lazy evaluation: as opposed to by-name eval. and strict eval.
– delay evaluation, store result, reuse result
– CBN + cache
lazy val x = expr
– quite unpredictable: when it be computed, how mach space it takes?

exercise
def expr = {
    val x = {print("x"); 1}         // immediately
    lazy val y = {print("y"); 2}    // once 
    def z = {print("z"); 3}         // every time 
    z + y + x + z + y + x }
expr // xzyz

lazy stream
object Stream {
    def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
        def isEmpty = false; def head = hd; 
        lazy val tail = tl }

-- Lecture 7.4 - Computing with Infinite Sequences
lazy infinite streams

the stream of all natural numbers
def from(n: Int): Stream[Int] = n #:: from(n+1)
val nats = from(0)
nats map (_ * 4) // all multiples of 4
– it can be useful

The Sieve of Eratosthenes
– start with all integers from 2, the first prime
– eliminate all multiples of 2
– the first = 3, prime number
– eliminate all multiples of 3 ...
def sieve(s: Stream[Int]): Stream[Int] = 
    s.head #:: sieve(s.tail filter (_ % s.head != 0))
val primes = sieve(from(2)) 
primes.take(100).toList

Square roots, again
– previous algorithm used 'isGoodEnough' test to tell when to terminate
– with streams we can express the concept of converging sequence
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 }

// termination decoupled from sqrt 
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
infinite stream of moves in a maze + BFS

problem : Die Hard 3 puzzle = given 5, 3 get 4
– we have fosset, sink, glasses (for example: 400, 900 ml)
– task: produce (say 600 ml) water in one glass
– A-star algorithm (BFS on the moves tree)

model
– glass numbers: 0..n-1
– water in glasses: State: Vector[Int], size n, each entry 0..m deciliters
– moves: Empty(glass), Fill(glass), Pour(fromGlass, toGlass)

idea: generate all possible moves : Paths
– path length 1, 2, 3 … until hit result
class Pouring(capacity: Vector[Int]) {
def solutions(target: Int): Stream[Path] = { // stream of all solutions for problem
    for {
        pathSet <- pathSets // for each set of paths
        path <- pathSet // for each path in that set
        if path.endState contains target // if path end state has desired glass content
    } yield path }

// all possible paths
val pathSets = from(Set(initialPath), Set(initialState))

// generate all paths (sequences of moves)
def from(paths: Set[Path], explored: Set[State]): Stream[Set[Path]] = {
    // extend all path in set (paths) to one step: make all moves
    // explored states we have already, don't go there
    if (paths.isEmpty) Stream.empty
    else {
        val more = for {
            p <- paths // for each path make all moves to extend path
            next <- (moves map p.extend)
            if !(explored contains next.endState)
        } yield next
        // lazy generator
        paths #:: from(more, explored ++ (more map (_.endState))) } }

val initialPath = new Path(Nil, initialState)
val initialState = capacity map (_ => 0)
type State = Vector[Int]
val glasses = 0 until capacity.length // glass numbers

// list of moves
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))

trait Move {
    def change(state: State): State }
case class Empty(glass: Int) extends Move {
    def change(state: State): State = state updated (glass, 0) } // new updated vector
case class Fill(glass: Int) extends Move {
    def change(state: State): State = state updated (glass, capacity(glass)) }
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) }}

// single path
class Path(history: List[Move], val endState: State) {
    // history in reverse, last move in head
    // endState is a value and is open to external calls
    def extend(move: Move) = new Path(move :: history, move change endState)
    override def toString = (history.reverse mkString " ") + "--> " + endState }
} // Pouring class
val problem = new Pouring(Vector(4, 9))
problem.solutions(6).take(3).toList

-- Lecture 7.6 - Course Conclusion
overview

FP provides a coherent set of notations and methods based on
– higher-order functions
– case classes and pattern matching
– immutable collections
– absence of mutable state
– flexible evaluation strategies: strict/lazy/by name

A different way of thinking about programs

What remains to be covered
– fp and state: mutable state, what changes and what does it mean
– parallelism: immutability for parallel execution
– DSL: domain-specific languages, high-level libs as embedded DSL; interpretation techiques for external DSL




Martin Odersky is the inventor of the Scala language,
a professor at EPFL in Lausanne, Switzerland, and Chairman and Chief Architect of Typesafe.

Lightbend: formerly Typesafe


https://mitpress.mit.edu/sicp/ Structure and Interpretation of Computer Programs
http://www.artima.com/pins1ed/ Programming in Scala, First Edition by Martin Odersky, Lex Spoon, and Bill Venners December 10, 2008




original post http://vasnake.blogspot.com/2016/03/functional-programming-principles-in.html

1 комментарий:

  1. Excellent ! I am truly impressed that there is so much about this subject that has been revealed and you did it so nicely.
    PHP Training in Chennai

    ОтветитьУдалить

Архив блога

Ярлыки

linux (241) python (191) citation (185) web-develop (170) gov.ru (156) video (123) бытовуха (111) sysadm (100) GIS (97) Zope(Plone) (88) Book (81) programming (81) бурчалки (80) грабли (77) development (73) Fun (72) windsurfing (72) Microsoft (64) hiload (62) opensource (58) internet provider (57) security (57) опыт (55) movie (52) Wisdom (51) ML (47) language (45) hardware (44) JS (41) curse (40) money (40) driving (39) DBMS (38) bigdata (38) ArcGIS (34) history (31) PDA (30) howto (30) holyday (29) Google (27) Oracle (27) virtbox (27) health (26) vacation (24) AI (23) Autodesk (23) SQL (23) Java (22) humor (22) knowledge (22) translate (20) CSS (19) cheatsheet (19) hack (19) tourism (18) Apache (16) Manager (15) web-browser (15) Никонов (15) happiness (14) music (14) todo (14) PHP (13) weapon (13) HTTP. Apache (12) SSH (12) course (12) frameworks (12) functional programming (12) hero (12) im (12) settings (12) HTML (11) SciTE (11) crypto (11) game (11) map (11) scala (10) HTTPD (9) ODF (9) купи/продай (9) benchmark (8) documentation (8) 3D (7) CS (7) DNS (7) NoSQL (7) Photo (7) cloud (7) django (7) gun (7) matroska (7) telephony (7) Microsoft Office (6) VCS (6) bluetooth (6) pidgin (6) proxy (6) Donald Knuth (5) ETL (5) NVIDIA (5) REST (5) bash (5) flash (5) keyboard (5) price (5) samba (5) CGI (4) LISP (4) RoR (4) cache (4) display (4) holywar (4) nginx (4) pistol (4) xml (4) Лебедев (4) IDE (3) IE8 (3) J2EE (3) NTFS (3) RDP (3) USA (3) mount (3) spark (3) Гоблин (3) кухня (3) урюк (3) AMQP (2) ERP (2) IE7 (2) NAS (2) Naudoc (2) PDF (2) address (2) air (2) british (2) coffee (2) font (2) ftp (2) holiday (2) messaging (2) notify (2) sharepoint (2) ssl/tls (2) stardict (2) tests (2) tunnel (2) udev (2) APT (1) CRUD (1) Canyonlands (1) Cyprus (1) DVDShrink (1) Jabber (1) K9Copy (1) Matlab (1) Palanga (1) Portugal (1) VBA (1) WD My Book (1) autoit (1) bike (1) cannabis (1) chat (1) concurrent (1) dbf (1) ext4 (1) idioten (1) krusader (1) license (1) mindmap (1) pneumatic weapon (1) quiz (1) regexp (1) robot (1) science (1) serialization (1) tie (1) vim (1) Науру (1) крысы (1) налоги (1) пианино (1)

Google+ Followers