VSnake notes: Functional Programming Principles in Scala

Вот тут

http://vasnake.blogspot.com/2015/11/scala.html

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

Продолжу.

Курс

Functional Programming Principles in Scala

https://www.coursera.org/course/progfun

Мартин Одерски (Martin Odersky), автор Scala.

Digest

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

http://scala-ide.org/download/sdk.html

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

http://download.scala-ide.org/sdk/lithium/e44/scala211/stable/site

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

http://docs.scala-lang.org/tutorials/tour/unified-types.html

– 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.

https://dzone.com/articles/revealing-scala-magician%E2%80%99s

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

Expression Problem

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

http://stackoverflow.com/questions/1446419/how-do-you-know-when-to-use-fold-left-and-when-to-use-fold-right

– 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