My notes from Coursera course "Functional Programming Principles in Scala" (https://class.coursera.org/progfun-004).

progfun04

Notes from Coursera course 'Functional Programming Principles in Scala":
https://class.coursera.org/progfun-004

✔ Week 1: Functions & Evaluations @done (14-05-01 17:20)

    ✔ Lecture 1.1 - Programming Paradigms (14:32) @done (14-04-27 17:54)

        3 paradigms: imperative, functional, logic
        OO: orthogonal
        imperative:
            mutable variables + if/loops
            Von Neuman style, match hardware but low level
        functional:
            avoid mutations and loops
            functions are fist-class citizens
            strict FP languages: Pure Lisp, Haskell (without I/O Monad, UnsafePerformIO), etc...
            non-strict FP languages: Lisp, Clojure, SML, OCaml, F#, Haskell (full language), Scala
        Why FP:
            simple reasoning principles
            modularity
            multi-core
        Additional resources:
            FP : SICP
            Scala: Scala for the impatient (free download)
            video: "Working hard to keep it simple"
    ✔ Lecture 1.2 - Elements of Programming (14:25) @done (14-04-27 19:53)
        REPL:
            "scala" or "sbt console"
        primitives:
            Int, Double, Boolean, etc...
        abstractions:
         "def"
            def pi = 3.14
            def square (x: Double) = x * x
        evaluation of function applications:
            substitution model: cf. lambda-calculus (Alonso Church), OK if no side effect
            call-by-value:
                1. evaluate args, 2. substitute function definition with args, 3. evaluate (precedence rule)
                advantage: args evaluated once
            call-by-name:
                substitute function first
                advantage: arguments are only evaluated if needed            
    ✔ Lecture 1.3 - Evaluation Strategies and Termination (4:22) @done (14-04-28 13:08)
        for a given expression, if call-by-value evaluation terminates, then call-by-name also terminates (the reverse is not true)
        Scala uses call-by-value by default
        call-by-name can be used with "=>"

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

    ✔ Lecture 1.4 - Conditionals and Value Definitions (8:49) @done (14-04-28 13:25)
        if/else:
            with predicates (and not statements)
            && and || use "short-circuit": right operand may not be evaluated
        def/value evaluation:
            def is called-by-name, val is called-by-value
                def loop: Boolean = loop
                // OK in REPL:
                def x = loop
                // infinite loop in REPL:
                val x = loop

    ✔ Lecture 1.5 - Example: square roots with Newton's method (11:25) @done (14-04-29 13:26)
        method:
            1. start with init estimate y = 1
            2. repeatedly improve estimate: y = mean (y, x/y)
         
        // Scala code, recursive implem:
        def abs(x: Double) = if (x < 0) -x else x

        def sqrtIter(guess: Double, x: Double): Double =
            if (isGoodEnough(guess, x)) guess
            else sqrtIter(improve(guess, x), x)

        def isGoodEnough(guess: Double, x: Double) =
            abs(guess * guess - x) < 0.001

        def improve(guess: Double, x: Double) =
             (guess + x / guess) / 2

        def sqrt(x: Double) = sqrtIter(1.0, x) 

        N.B.: Scala recursive functions need an explicit return type
        For non-recursive functions, type is optional

    ✔ Lecture 1.6 - Blocks and Lexical Scope (8:00) @done (14-04-29 19:13)
        goal: make code modular and easy to use

        1. use nested functions to provide namespace pollution

            block: code delimited by { ... }
            definitions inside block:
                are only visibly wihin block
                can shadow defintions that exist outside

        2. remove parameters duplicated in nested functions

    ✔ Lecture 1.7 - Tail Recursion (12:32) @done (14-04-29 19:36)

        classical recursive algorithms:
            - greater common divisor via Euclid's algo
            - factorial

        tail recursive functions reuse function stack frame directly
        gcd is tail recursive, factorial is not

        tail recursion acts as a loop

        Generally, if last function action is calling a function, it is tail recursive

        In Scala, @tailrec annotation is used to check that a function is tail recursive (otherwise, compilation would fail)

        exercise: tail recursive factorial

 ☐ Week 2: Higher Order Functions

    ✔ Lecture 2.1 - Higher-Order Functions (10:18) @done (14-05-04 20:31)

    Higher-Order Functions:

        For FP languages, functions are treated as first-class values
        higher-ordered function: which is passed as other function's argument or returned from another function
        motivation: a way to compose programs

        example:
            def sumInts(a: Int, b: Int): Int =
                if (a > b) 0 else a + sumInts(a + 1, b)
            def sumCubes(a: Int, b: Int): Int =
                if (a > b) 0 else cube(a) + sumInts(cube(a + 1, b)
                
            // let's factorize common code via HOF (equilavent to math. expression "sigma(f(n)) with n = [a, b]"):
            def sum(f: Int => Int, a: Int, b: Int) =
                if (a > b) 0 else f(a) + sum(f, a + 1, b)
            def sumInts(a: Int, b: Int): Int = sum(id, a, b) 
            def sumCubes(a: Int, b: Int): Int = sum(cube, a, b)
            def sumFactorials(a: Int, b: Int): Int = sum(fact, a, b)

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

        Anonymous functions:
            Sometimes it's tedious to name short functions
            => use anonymous functions

            // anonymous function that takes an integer and returns its cube, as an integer:
            (i: Int) => i * i *
            // returned type can be omitted if it can be infered:
            i => i * i * i
            // anonymous function with 2 params:
            (Int: a, Int: a) => a + b
            // or 
            a, b => a + b

        Any anonymous function is equivalent to:
            def f(a: A, b: B) = 
                // body ; f(a, b)
            So they are "syntactic sugar" (i.e. they're not essential)

        Our example, revisited with anonymous functions:
            sum(i => i)(1, 3)
            sum(i => i*i*i)(1, 3)

    ✔ Lecture 2.2 - Currying (14:58) @done (14-05-05 13:34)

        A curried function is a function that returns (nested) functions. All functions have 1 arg.

        motivation:
            factorize repetition

        example: 
            // a lot of repetition there:
            def sumInts(a: Int, b: Int): Int = sum(id, a, b) 
            def sumCubes(a: Int, b: Int): Int = sum(cube, a, b)
            def sumFactorials(a: Int, b: Int): Int = sum(fact, a, b)
            // ...can be curried to:
            def sum(f: Int => Int): (Int, Int) => Int = {
                def sumF(a: Int, b: Int): Int =
                    if (a > b) 0 else f(a) + sumF(a + 1, b)
                 sumF
            }
            def sumInts2 =  sum(x => x)
            def sumCubes2 =  sum(x => x*x*x)
            sumCubes2(1, 10) + sumInts(10, 20)
            // or use curried function directly:
            sum(cube)(1, 10)

            // Special (shortest) synthax for currying:
            def sum(f: Int => Int)(a: Int, b: Int): Int = {
                if (a > b) 0 else f(a) + sum(f)(a + 1, b)
            }

        Any function f(a, b, c, ...) can be curried to f(a)(b)(c)(...)

        Function types:
            // What's the type of this function?:
            def sum(f: Int => Int)(a: Int, b: Int): Int = ...
            // answer:
            (Int => Int) => (Int, Int) => Int

        Exercise: 
             // A function which generalizes both sum and product:
             def mapReduce(f: Int => Int, combine: (Int, Int) => Int, init: Int) (a: Int, b: Int): Int = 
                 if (a > b) init
                 else combine(f(a), mapReduce(f, combine, init)(a + 1, b))
             def product(f: Int => Int)(a: Int, b: Int): Int = mapReduce(f, (a, b) => a * b, 1)(a, b)
             product(x => x*x)(3, 4)

    ✔ Lecture 2.3 - Example: Finding Fixed Points (10:46) @done (14-05-06 08:53)

        fixed point of a function:
            number x is a fixed point of a function f if f(x) = x
            Often found starting with initial estimate and applying f repeatedly until "stable": x, f(x), f(f(x)), etc...

        example - computation of square root via fixed point:
            specification:  sqrt(x) = the number y such that y * y = x
            or:                    sqrt(x) = the number y such that y = x / y
            consequently, sqrt(x) is a fixed point of the function (y => x / y)

            But implementing it directly does not work, it does not converge
            def sqrt(x: Double) = fixedPoint(y => x / y)(1.0) // fails

            solution is averaging successive values (prevent estimations from varying too much)
            def sqrt(x: Double) = fixedPoint(y => (y + x / y) / 2)(1.0)
            // or better
            def sqrt(x: Double) = fixedPoint(averageDamp(y => x / y))(1)

         Conclusion:
             know how to reuse code via abstraction (higher-ordered functions)
             but do not always use the highest level of abstraction!

    ✔ Lecture 2.4 - Scala Syntax Summary (4:13) @done (14-05-06 09:13)

        context-free syntax (Extended Backus-Naur form):
            | : alternative
            [...] :  option (0 or 1)
            {...} : repetition (0 or more)

       types:
           numeric type: [Int Double Byte Short Char Long]
           Boolean with values true and false
           String
           function type
           (+ some others, see later)

       expressions:
           identifier (i.e. "isGoodEnough")
           literal (i.e 2, "abc")
           function application (i.e. "sqrt(x)")
           operator application (i.e. "-x")
           selection (i.e. "math.abs")
           conditional (i.e. "if (x > 2)"")
           block (i.e. "{ val foo = 2 }")
           anonymous function (i.e. "x => x +1")

       definitions:
           value definition, like "val y = sqrt(2)"
           function definition, like "def cube(x: Int) = x * x
               call-by-value function parameter, like "(x: Int)"
               call-by-name function parameter, like "(y: => Int)"

    ✔ Lecture 2.5 - Functions and Data (11:50) @done (14-05-06 13:11)

        goal:
            create and encapsulate data structures in a class

        class: type with name + constructor in a namespace
        object: class instanciation
        members: are accessed with infix operator '.'
        methods: functions packages inside class

        example:
            object rationals {
              val x = new Rational(1, 2)                      //> x  : week2.Rational = 1/2
              val y = new Rational(5, 7)                      //> y  : week2.Rational = 5/7
              val z = new Rational(3, 2)                      //> z  : week2.Rational = 3/2

              x.numer                                         //> res0: Int = 1
              x.add(y)                                        //> res1: week2.Rational = 17/14
              x.neg                                           //> res2: week2.Rational = -1/2
              x.sub(y)                                        //> res3: week2.Rational = -3/14
            }

            class Rational(x: Int, y: Int) {
              def numer = x
              def denom = y

              def add(that: Rational) =
                new Rational(
                  numer * that.denom + that.numer * denom,
                  denom * that.denom)
              
              def neg() = {
                new Rational(-numer, denom)
              }

              def sub(that: Rational) =
                    add(that.neg) // DRY

              override def toString = numer + "/" + denom
            }

    ✔ Lecture 2.6 - More Fun With Rationals (15:08) @done (14-05-06 19:37)

      goal:
        show data abstraction

      data abstraction:
        = separate API (public methods and values) from private definitions

      self-reference:
        Use 'this' to refer to current instance)
      
      requirement:        
        via "require" predefined function which can throw IllegalArgumentException
        used for preconditions on a function (constructor, method or function), on caller side

      assertion:
        via "assert" predefined function, throws AssertionError
        used to check the code

      constructors:
        primary constructor: take class params + execute class body
        secondary constructor are "this" definitions, i.e. "def this(x: Int) = this(x, 42)"

    ✔ Lecture 2.7 - Evaluation and Operators (16:25) @done (14-05-06 21:08)

      classes and substitution model:
        class instanciations are function are evaluated like normal functions

        // given:
        class(x1) { def f(y1) = b }
        // how is this evaluated?:
        new Class(v1).f(w1)

      3 substitutions:
          - substitution of params of class
          - substitution of params of function 'f'
          - substitution of the self reference 'this' (by the value of "new C(...)"

      operator "overload":
          // we can use operators (such as '+') for objects
          new Rational(2/3) +  new Rational(4/5)
          // ...  instead of:
          new Rational(2/3).add(new Rational(4/5))

      via 1. infix notation for functions:
                example: "r1 add r2" instead of "r1.add(r2)"
          2. relaxed identifiers:
            identifiers can
            - start with alphanumeric and contain special chars ('+?%&_)
            - contain only special chars ('+?%&_) 
            Examples of valid identifiers: x1, *, +?%&, vector_++, counter_=

      operator precedence:
        precedence of an operator depends on its 1st letter
        chars sorted by priority: letters | ^ & < > = ! : + - * / % (all other special chars)

      WARNING:
        use operators with care and onywhen it makes sense


 ✔ Week 3: Data and Abstraction @done (14-05-20 08:03)

   ✔ Lecture 3.1 - Class Hierarchies (25:50) @done (14-05-11 16:30)

     core concept: dynamic binding

     abstract class / extension:
       can have members without implementation
       cannot be instanciated       
       example: binary trees with purely functional data structure (no mutation), aka persistent data structure

       superclass / subclass / base class
       in Scala, all classes extend java.lang.Object

     overriding:
       subclasses can redefine a non-abstract definition via 'override' modifier (mandatory)

       example:
         abstract class MyBaseClass { def foo = 1; def bar: Int }
         class MySubClass {            
           override def foo = 2 // override is mandatory
           override def bar = 3 // override is optional (less preferred < noisy)
         }

     singleton object:
       class with only one instance
       can reference itself (since it is a value)
       object Empty ... // instead of "class Empty ..."

       N.B.: standalone apps (main programs) are singletons with a main function

     dynamic binding:
       dynamic method dispatch: code invoked by a method depends on the runtime type of the object that contains the method
       Scala implements it (like other some other OOP langs)
       cf. similarity with HOFs (can we implement objects via HOFs and vice-versa?)


   ✔ Lecture 3.2 - How Classes Are Organized (20:30) @done (14-05-11 17:18)
     How to organize real-life code (i.e. 100+ classes)?

     packages:
       classes and objects are organized in packages
       fully qualified class name: <package>.<class name>

       import:
         - a single class or object from a package: "import mypackage.MyClass"
         - import several classes (or objects) from a package: "import mypackage.{MyClass, OtherClass}"
         - import all classes (or objects) from a package: "import mypackage._" (wildcard import)

       (automatically imported:)
         - scala._ (Int, Boolean, etc...)
         - java.lang._ (Object, etc...)
         - scala.Predef._ (require, assert, etc...)

       scaladoc:
         generated code documentation (see Scala lib's scala doc)

       Traits:
         Traits are like abstract classes
         Scala uses single inheritance, so 1 object / class or trait
          can inherit from only 1 class
          but can inherit from several traits

        ex: class Square extends Shape with Planar with Movable

        Traits cannot have value params

      Scala's class hierarchy:
        Any       // Any's methods: == != equals hashCode toString
          AnyVal (primitive types + Unit) + cf. conversion relations
          AnyRef (other types: String, Seq, etc...) / ScalaObject
        Null      // subtype of AnyRef (except Nothing), null's type
        Nothing   // subtype of all types, has no value, used for 1. abnormal termination (exceptions) + 2. for empty collections        

   ✔ Lecture 3.3 - Polymorphism (21:09) @done (14-05-11 18:00)

     parameterized types:
       Functions and classes can have parameterized types
       notation: MyClass[MyParameterizedType]
       example: a fundamental data structure, immutable linked list (cons-list)

       N.B: type params can often be deduced by compiler (type inference)
       ex: "singleton(2)" instead of "singleton[Int](2)"

     Type erasure:
       type param does not affect evaluation in Scala (it only affects compilation)
       Some other langs (C++, F#, et...) keep type at runtime

     Polymorphism:
       = a function type comes in "many forms":
         a function can be applied to args of many types (-> subtyping)
           or
         a type can have instances of many types (-> generics)

 ✔ Week 4: Types and Pattern Matching @done (14-05-29 16:22)

    ✔ Lecture 4.1 - Functions as Objects (8:04) @done (14-05-20 08:39)
      How function types relate to classes & how function values relate to objets

      Functions as objects:
        Function values are treated as objects

        Type "A => B" is a abbreviation for "trait Function1[A,B] { def apply (x: A): B }"
        see Function2, Function3, etc...

        Anonymous function '(x: Int) => x * x" is expanded to: //
        { 
            class AnonFun extends Function1[Int, Int] {
              def apply(x: Int) = x * x
            } 
            new AnonFun
        } // or shorter, using anonymous class syntax:
        new Function1[Int, Int] {
          def apply(x: Int) = x * x
        } 

      Function calls (expansion):
        Methods such as
          def f(x: Int): Boolean = ..."
        is only converted to a function value when function type is expected ("eta-expansion in lambda-calculus").

        Ex: //
          (x: Int) => f(x)
        is expanded to: //
          new Function1[Int, Boolean] { def apply(x: Int) = f(x) }

    ✔ Lecture 4.2 - Objects Everywhere (19:07) @done (14-05-20 13:38)

    primitive types as classes (OO):
      pure object-oriented language: every value is an object, type of every value is a class

      Is Scala a pure OO language?
      Yes, we can implement all primitive types and operators (i.e. boolean, int) via classes (Boolean, Int, etc...).

      exercise 1: implement Boolean operators from scratch via a class
      exercise 2: implement class that represents non-negative integers without primitive type ("Peano numbers")

    ✔ Lecture 4.3 - Subtyping and Generics (15:02) @done (14-05-21 08:35)

      About polymorphism and Liskov Substitution Principle

      2 forms of polymorphism:
       - generics (for functions)
       - subtyping (for types => OOP)       

      2 areas:
       - type bounds
       - variance 

      Type bounds:

        Upper bound:
          // S is a subtype of T
          S <: T

        Lower bounds:
          // S is a supertype of T (i.e. T is a subtype of S)
          S >: T

        Mixed bounds:
          example: S >: NonEmpty <: IntSet

        example:
          Function 'assertAllPos' which input is Int set and which returns
          - empty Int set if input is empty
          - non empty set if input contains only positive ints
          - throw Exception otherwise

            // we can use "upper bound"
            def assertAllPos[S <: IntSet](r: S): S

          Covariance:
            Given
              NonEmpty <: IntSet 
            Is List[NonEmpty] <: List[IntSet] true?

            In Java, arrays are covariant, but it causes runtime problems (not detected by compilation)
            In Scala, arrays are not covariant

          Liskov Substitution Principle:
            if A <: B, all methods of type B should be available for value of type A
            (N.B.: LSP is a bit more formal)

          // NonEmpty <: IntSet
          val a: Array[NonEmpty] = ...
          val b: Array[IntSet] = a // Compilation error!
          b(0) = Empty
          val s: NonEmpty = a(0)

    ☐ Lecture 4.4 - Variance (Optional) (21:33)

    ✔ Lecture 4.5 - Decomposition (16:57) @done (14-05-21 09:31)
      
      Example:
        // write a small interpreter for arithmetics expression
        
      Non-solution 1:
        Not scalable type hierarchy (+ eval function) could be
           trait Expr
            - isNumber
            - isSum
            - isProd
            ... // does not scale (quadratic increase of methods)...
            - number
           /       |       \p
  Number  Sum    Prod etc...
         
         NOT SCALABLE!

        Non-solution 2:
          Using type tests and type casts in eval function
          pro: no classification 
          cons: low level / unsafe

        Solution 1 via OOP decomposition:
          trait Expr { def eval: Int}
          class Number(n: Int) extends Expr { def eval : Int = n}
          class Sum(e1: Expr, e2: Expr) extends Expr { def eval : e1.eval + e2.evpal }

          limitation:
            If we add another method (example: "show"), we add to implement it in all hierarchy
            We cannot simplify expressions in one method (ex: a * b + a * c     ->    a * (b + c))

            This issue is known as the "expression problem"
            Cf. "pattern matching" lecture for fixing this issue

    ✔ Lecture 4.6 - Pattern Matching (19:36) @done (14-05-21 13:18)

    pattern matching is good fit for resolving our decomposition problem

    case classes:
    - allow pattern matching on a constructor, variables, constants or wildcard ('_')
    - define implicit apply method (=> factory methods)        ex: Number(2)

    syntax:
      ... match {
        case pattern1 => eval1
        case pattern2 => eval2
        // otherwise: expression error
      }

      If a pattern matches, expression is rewritten to its right-hand side of expression.
      If pattern contains a variable, name of variable is bound to its value

    Solution 2 via pattern matching:
      // in eval function:
      def eval(e: Expr): Int = e match {
        case Number(n) => n
        case Sum(e1, e2) => eval(e1) + eval(e2)
      }
      // or in trait:
      trait Expr {
        def eval: Int = this match {
          case Number(n) => n
          case Sum(e1, e2) => e1.eval() + e2.eval()
        }
      }

      Adding an operation (example, "show") is implemented in a single function
        def show(e: Expr): String = e match {
          case Number(x) => x.toString
          case Sum(l, r) => show(l) + " + " + show(r)
      }

    ✔ Lecture 4.7 - Lists (16:20) @done (14-05-21 21:12)

    Collections (particularly immutables ones)

    Lists:
      immutable (arrays are mutables)
      recursive (arrays are flat)
      homogeneous: all elems must have same type
      cons-list: constructed with empty list 'Nil' + operation '::' (pronounced "cons")
      [convention: all functions ending with ':' 
        - associate to the right, i.e. A :: B :: C is interpreted as A :: (B :: C)
        - are method calls on the right-hand operator, i.e. 1 :: 2 :: Nil is equivalent to Nil.::(2).::(1) ]
    
    val l = List("a", "b", "c")
    val l2 = List(List(1, 2), List(3, 4, 5)) // recursive
    val l3 = List() // empty list
    val l4 = 1 :: (2 :: Nil)

    basic operations: head, tail, isEmpty
    pattern matching can be used (and is often prefered) => list decomposition
    sorting can be done via pattern matching
      def insertionSort(xs: List[Int]): List[Int] = xs match {
        case List => List()
        case y :: ys => insertionSort(y, ys)
      }

☐ Week 5: Lists

  ✔ Lecture 5.1 - More Functions on Lists (13:04) @done (14-05-29 17:16)

  More methods: length, last, init (all elements except last), take(n) (first n elements), drop(n)
  (index)

  creation: 
    ++ (concatenation), reverse, updated(n, x)

  finding elements:
    xs indexOf x (index of first element that equals x)
    xs contains x (true if xs contains x)
    (n) (value at index n)

  complexity:
    warning:
      last, init are O(n)
      xy :: xs is O(size(xs))
      reverse is O(n2)

  ✔ Lecture 5.2 - Pairs and Tuples (10:45) @done (14-05-29 17:37)
    pair = 2-tuple
    pairs can be pattern matched
    
    (a,b) is an abbreviation of scala.Tuple2(a,b)
    (a,b,c) is an abbreviation of scala.Tuple3(a,b,c)
    case class Tuple2[T1,T2] (_1: +T1, .2: +T2) 

    ex: 
      val pair ("answer", 42)
      val answerIs = pair._2

    usage example:
      Sort list more efficiently via merge sort
      1. split list in 2 sub-lists
      2. sort sub-lists
      3. merge sorted sub-lists into single list

      def mergeSort(xs: List[Int]): List[Int] ={
       val n = xs.length / 2
       if (n == 0) xs
       else {
         // use nested patter matching that reflect the inherent symetry of the algotrithm
         def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, xy) match {
           case (Nil, ys) => xy
           case (xs, Nil) => xs
           case (x :: xs1, y :: ys1) => if (x < y) x :: merge(xs1, ys) else y :: merge(xs, ys1)
         }
         val (first, second) = xs splitAt n
         merge(mergeSort(first), mergeSort(second))
       }
      }

  ✔ Lecture 5.3 - Implicit Parameters (11:08) @done (14-05-29 17:59)

    Implicit parameter is infered by the compiler (not set explicitely in function call)

    How to use mergeSort function for other types that Int?
    Use type parameter + comparison function:
      def mergeSort[T](xs: List[T])(lt: (T,T) => Boolean) = ...
      mergeSort(List(1,6,3,5))((x,y) => x < y) // compiler infers types...
      // or use standard lib for ordering: math.Ordering which contains lt(x,y)
      def mergeSort[T](xs: List[T])(ord: Ordering) = ...
      mergeSort(List(1,6,3,5))(Ordering.Int)
      // or better, use implicit parameter
      def mergeSort[T](xs: List[T])(implicit ord: Ordering) = ...
      mergeSort(List(1,6,3,5)))
    
  ✔ Lecture 5.4 - Higher-Order List Functions (14:53) @done (14-05-30 17:19)

    several patterns: transform all elements, combine them, retrieve another list...

    map:
    apply function to all elements, return list (NB: works for all collections)
    xs map f

    filter:
    return list filtered by a function
    xf filter (x => x > 10)

    variations of filter: filterNot, partition (split in two lists), takeWhile, dropWhile, span (split in two lists)

  ✔ Lecture 5.5 - Reduction of Lists (15:35) @done (14-05-30 17:36)

    fold / reduce combinators

    reduceLeft/reduceRight:
    Cannot be applied to empty list  
    List(1,2,3) reduceLeft ((x,y) => x + y)
    // or:
    List(1,2,3) reduceLeft 0 (_ + _)    

    foldLeft/foldRight:
    Similar, can be applied to empty list because it has an accumulator param
    (List(1,2,3) foldLeft 0)(_ + _)    
    

  ☐ Lecture 5.6 - Reasoning About Concat (13:00)

  Proof techniques

  Laws of concat (++):
    associative: (xs ++ ys) ++ zs = xs ++ (ys ++ zs) 
    admit Nil neutral elem: xs ++ Nil = xs and Nil ++ xs = xs

  Natural induction:
    1. show property for base case n
    2. induce step n+1

  Referential transparency:

  Structural induction:

  ☐ Lecture 5.7 - A Larger Equational Proof on Lists (9:53)

 ☐ Week 6: Collections
   
  ✔ Lecture 6.1 - Other Collections (20:45) @done (14-06-02 09:01)
    Other immutable collections than List

                     Iterable
                /           |          \
            Seq        Set       Map
       /      |      \
  List  Vector Range

    Vector:
      is a Seq (sequence), like List
      implemented via array tree that progressively grows
        => get(i) = O(log(n))
      adapted to bulk operations (chunks in cache) like map, filter, etc...

      operations are similar to List, except the cons
        x +: xs // x is the 1st elem
        xs :+ x // x is the last elem

      construction is O(log(n)) due to object creation

      Range:
      lower bound + upper bound + step value)
      1 until 5 // 1,2,3,4
      1 to 5 // 1,2,3,4,5
      1 to 10 by 3 // 1,4,7,10

    Seq:
     Array ans String have same ops that Seq
     support ranges
     ops:
       xs exists p
       xs forall p
       xs zip ys   // returns a sequence of pairs
       xs unzip   // returns a flat seq from pairs
       xs.flatMap f // returns a seq containing all elements of xs with f applied
       xs.sum
       xs.product
       xs.max
       xs.min

       examples:
       // list all combinations (x, y):
       (1 to M) flatMap (x => (1..N) map (y => (x,y)))
       // product of scalar vectors (sum from i=1 to n = xi * yi):
       def scalarProduct(xs: Vector(Double), ys: Vector(Double)): Double =
         (xs zip ys).map(xy => xy._1 * xy._2).sum
       // or via pattern matching:
         (xs zip ys).map{ case (x, y) => x * y }.sum
       // is prime number?
       def isPrime(n: Int): Boolean = (2 until n) forall (d => n % d != 0)

  ✔ Lecture 6.2 - Combinatorial Search and For-Expressions (13:12) @done (14-06-02 20:33)
    handling nesting sequences, without loops

    for-expression is similar to imperative loop:
      for (s) => yield e 

    example 1:
    find all pairs of positive integers i, j such as j < i and i + j is prime
    the FP way: 1. generate pairs such as j < i
                2. filter pairs for which i + j is prime

    // via until + flatMap + map (a bit hard to read)
    (1 until n) flatMap (i => 
      (l until i) map (j => (i, j)))
        .filter(pair => isPrime(pair._1 + pair._2))

    // via for-expression (clearer):
    for {
      i <- 1 until n
      j <- 1 until i
      if isPrime(i + j)
    } yield(i, j)

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

  ✔ Lecture 6.3 - Combinatorial Search Example (16:54) @done (14-06-03 08:26)

    Sets are similar to sequences but:
      1. unordered
      2. no duplicate elements
      3. fundamental operation is "contains"

    Set examples:
      val fruits = Set("apple, banana", "pear")
      val nums = (1 to 2).toSet
      nums map (_ + 2)
      fruits filter(_.startsWith == "app")

    N-queens example:
    // place n queens on a board without "threatening" (in same row or column or diagonal)
    def queens(n: Int): Set[List[Int]] = {

      def isSafe(col: Int, queens: List[Int]) =  {
        val row = queens.length
        val queensWithRow = (row-1 to 0 by -1) zip queens
        queensWithRow forall {
          case (r, c) => col != c && math.abs(col - c) != row - r
        }
      }

      def placeQueens(k: Int): Set[List[Int]] =
        if (k == 0) Set(List())
        else 
          for {
            queens <- placeQueens(k - 1)
            col <- 0 until n
            if (isSafe(col, queens)
          } yield col :: queens
        placeQueens(n)
      }

      def show(queens: List[Int]) = {
        val lines = 
          for (col <- queens.reverse)
          yield Vector.fill(queens.length)("* ").updated(col, "X ").mkString "\n" + (lines mkString "\n")
      }
      // queens(4) map show
      // (queens(8) take 3) map show

  ✔ Lecture 6.4 - Queries with For (7:50) @done (14-06-03 09:05)
  More about for-expressions

   for-expression notation is similar to query languages for database

   // retrieve title of books which author name starts with "Bird":
   for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title

   // find authors who have written at least 2 books:
   {
     for {
       b1 <- books ; b2 <- books
       if (b1 != b2)
       a1 <- b1.authors ; a2 <- b1.authors
       if (a1 == a2)
     } yield a1
   }.distinct // remove duplicate names, if books is a list (but not needed it is a set)

  ✔ Lecture 6.5 - Translation of For (11:23) @done (14-06-03 13:52)
  Implementation of for-expressions

  related to HOF functions map, flatMap and filter
  * map, flatMap and filter can be implemented by for-expression
  * for-expressions are implemented by map, flatMap and filter:

   // example 1:
   for (x <- e1) yield e2
   // is translated by Scala  compiler to:
   e1.map(x => e2)

   // example 2:
   for (x <- e1 if f; s) yield e2
   // is translated by Scala  compiler to:
   for (x <- e1.withFilter(x => f); s) yield e2 // withFilter is lazy version of filter

   // example 3:
   for (x <- e1; y <- e2; s) yield e3
   // is translated by Scala  compiler to:
   e1.flatMap(x => for (y <- e2; s) yield e3)

   // example 4:
   for {
     i <- 1 until n
     j <- 1 until i
     if isPrime(i + j)
   } yield (i, j)
   // is translated by Scala  compiler to:
   (1 until n).flatMap(i =>
     (1 until i).withFilter(j => isPrime(i+j))
       .map(j => (i, j)))

   Exercise:
     // translate the following code
     for (b <- books; a <- b.authors if a startsWith "Bird")
     yield b.title

     // into a HOF:
     books flatMap ( b => 
       b.authors withFilter (a => a startsWith "Bird")
         map (y => y.title))

  ✔ Lecture 6.6 - Maps (22:39) @done (14-06-03 20:44)
  Map:
   maps associate key to value
   are iterable and are functions, in Scala

  Examples:
  // create map:
  val romanNumerals = Map("I" -> 1, "II" -> 2)
  // query value for a given key (error if absent):
  romanNumerals("II") // returns 2
  romanNumerals("not exists") // throws java.util.NoSuchElementException
  // query value option for a given key
  romanNumerals get "not exists" // Option: None
  romanNumerals get "I" // Option: Some(1)

  Option decomposition:
  // using pattern matching:
  def showNumber(roman: String) = romanNumerals.get(roman) match = {
  case Some(number) => number
  case None => 0
  }

  Sort / group-by:
  val fruits = List("banana", "apple")
  fruits sortWith (_ < length < _.length) // List("apple", "banana")
  fruits.sorted // List("apple", "banana")
  fruits groupBy (_.head) // Map(a -> List("apple"), b -> List("banana")

  Default value:
  val romanNumeral withDefaultValue -1
  val("I") // 1
  val("not exists") // -1


  Example - polynomial:
  // x^3 - 2 x + 5 can be represented by:
  Map(0 -> 5, 1 -> -2, 3 -> 1)

  // let's design a class Polynom that reprensent polynoms as maps:
  object Polynomials {
    class Poly(val terms0: Map[Int -> Double]) {
      
      val terms = term0 withDefaultValue 0.0

      def this(bindings: (Int, Double)*) // *: repeating parameter (vararg), as a sequence
        this(bindings.toMap)

      def + (other: Poly) = new Poly(terms ++ (other.terms map adjust))
      def adjust(term: (Int, Double)): (Int, Double) = {
        val (exp, coeff) = term
        exp -> (coeff + terms(exp))
      }

      // alternative implem that uses foldLeft (more efficient that '+'):
      def plus (other: Poly) =
        new Poly((other.terms foldLeft terms)(addTerm))
      def addTerm(terms: Map[Int, Double], term: (Int, Double)): Map[Int, Double] = {
        val (exp, coeff) = term
        terms + (exp -> (coeff + terms(exp)))
      }

      override def toString = 
        (for ((exp, coeff) <- terms.toList.sorted.reverse) 
          yield coeff + "x^" + exp) mkString " + "
    }
    val p1 = new Poly(Map(0 -> 5, 1 -> -2, 3 -> 1))
    val p2 = new Poly(0 -> 5, 1 -> -2, 3 -> 1)
    p1 + p2
 }

  ✔ Lecture 6.7 - Putting the Pieces Together (20:35) @done (14-06-03 21:24)
  Example: convert phone numbers to sentences (cf. Lutz Prechelt: An empirical comparison of seven programming languages)
  
  val words = Source.fromURL("http://xxx").getLines.toList
    filter (word => word forall (chr => chr.isLetter)) // filter words with chars such as "-"
  val mnemonics = Map('2' -> "ABC", '3' -> "DEF" ...)

  // produce all phrases that could be used as mnemonics:

  // "invert mnemonic map" (i.e. Map('A' -> '2', 'B' > '2'))
  val charCode: Map[Char, Char] = 
    for ((digit, str) <- mnemonics); ltr <- str) yield ltr -> digit

  // map a word to a digit string (i.e. "java" -> "5282")
  val charCode(word: String): String =
    word.toUpperCase map charCode

  // all words for a digit lists (i.e. "5282" -> List("java", "kata", ...))
  val wordsForNum: Map[String, Seq[String]] =
    words groupBy wordCode withDefaultValue(Seq())

  // i.e. "7225247386" -> Set("xxx yyuy zzzdz", ...)
  def encode(number: String): Set[List[String]] =
    if (number.isEmpty) Set(List())
    else {
      for {
        split <- 1 to number.length
        word <- wordsForNum(number take split)
        rest <- encode(number drop split)
      } yield word :: rest
    }.toSet

  // i.e. "7225247386" -> "xxx yyuy zzzdz"
  def translate(number: String): Set[String] =
    encode(number) map (_ mkString " ")

☐ Week 7: Lazy Evaluation

 ☐ Lecture 7.1 - Structural Induction on Trees (15:10)

 ✔ Lecture 7.2 - Streams (12:12) @done (14-06-09 12:34)
Streams

Stream: like list, but with lazy tail (on demand)

Usage example:
// find 2nd prime number, elegant way but not performant at all (all primes in range are computed):
((1000 to 10000) filter isPrime)(1)
// with stream:
(1000 to 10000).toStream filter isPrime)(1)

Stream construtors:
stream1 = Stream.cons(1, Stream.cons(2, Stream.empty))
stream2 = Stream(1, 2, 3)
(1 to 1000).toStream // REPL: Stream[Int] = (1, ?)

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

Stream methods:
Same methods as List: isEmpty, head, tail, filter, etc... but except cons "::" which always produces a list
"#::" produces a stream

Cons implem:
trait Stream {
  // Notice that tail param is a by-name parameter
  def cons[T] (hd: T, tl: => Stream[T]) = {
    def isEmpty = false
    def head = hd
    def tail = tl
  }
}

 ✔ Lecture 7.3 - Lazy Evaluation (11:38) @done (14-06-10 08:48)

 lazy evaluation:
 compute late and compute only once
 (like by-name evaluation, but compute once)
 => avoid performance issue if multiple recomputations

 Haskell uses lazy eval by default.
 Scala uses strict evaluation by default.

 def fooDef = { println "fooDef"; 0}
 val fooVal = { println "fooVal"; 0}
 lazy val  = { println "fooVal"; 0}

 Syntax: 
   lazy val x = expr

 Usage example, Stream improvement (lazy tail):
trait Stream {
  def cons[T] (hd: T, tl: => Stream[T]) = {
    def head = hd
    lazy val tail = tl
    // ...
  }
}

 ✔ Lecture 7.4 - Computing with Infinite Sequences (9:01) @done (14-06-10 09:10)
  Lazy vals allow infinite streams

  Basic usage:
  def from(n: Int): Stream[Int] = n #:: from(n+1)
  // all natural numbers:
  val naturalNumbers = from(0)
  // all multiples of 4:
  naturalNumbers map (_ * 4)

  Examples:

   Sieve of Eratosthenes (prime numbers):
    def sieve(s: Stream[Int]): Stream[Int] =
      s.head #:: sieve(s.tail filter (_ % s.head != 0))
    
    val primes = sieve(from(2))

    Square roots:
      def sqrtStream(x: Double): Stream[Double] = {
        def improve(guess: Double) = (guess + x / guess) / 2
        lazy val guesses: Stream[Double] = 1 #:: (guesses map improve)
        guesses
      }
      def isGoodEnough(guess: Double, x: Double) =
        math.abs((guess * guess - x) / x) < 0.0001

      sqrtStream(4) filter (isGoodEnough(_, 4))

 ✔ Lecture 7.5 - Case Study: the Water Pouring Problem (31:45) @done (14-06-10 21:09)

 (our solution can be compared to original Python's solution)

 Problem:
   measure a given water volume via several glasses that have distinct capacity

 Representation (state and moves):
   Glass: Int
   State: Vector[Int] (one entrey per glass)
   Moves: Empty(glass)
          Fill(glass)
          Pour(from, to)

   Solution: find all paths until a state contains our requested quantity

Implem:

  class Pouring(capacity: Vector[Int]) {

    // State:
    type State = Vector[Int]
    val initialState = capacity map (x => 0)

    // Moves:
    trait Move {
      def change(state: State): State
    }
    case class Empty(glass: Int) extends Move {
      def change(state: State): State = state updated (glass, 0)
    }
    case class File(glass: Int) extends Move {
      def change(state: State): State = state updated (glass, capacity)
    }
    case class Pour(from: Int, to: Int) extends Move {
      def change(state: State): State = {
        val amount = state(from) min (capacity(to) - state(to))
        state updated (from, state(from) - amount) updated (to, state(to) + amount)
      }
    }

    val glasses = 0 until capacity.length

    val moves = 
      (for (g <- glasses) yield Empty(g)) ++
      (for (g <- glasses) yield Fill(g)) ++
      (for (from <- glasses; to <- glasses if from != to) yield Pour(from, to))


    // optimization: compute end state once
    class Path(history: List[Move], val endState: State) {
      def extend(move: Move) = new Path(move :: history, move change endState)
      override toString() = (history.reverse mkString " ") + "--> " + endState 
    }

    val initialPath = new Path(Nil, initialState)

    def from(paths: Set[Path], explored: Set[Path]): Stream[Set[Path]] = 
      if (paths.isEmpty) Stream.empty
      else {
        val more = for {
          path <- pathes
          next <- moves map path.extend
          // prevent infinite search: do no visit explored state twice
          if !(explored contains next.endState)
        } yield next
        paths #:: from(more, explored ++ (more map (_.endState)))
      }

    val pathSets = from(Set(initialPath), Set(initialState))

    def solution(target: Int): Stream[Path] =
      for {
        pathSet <- pathSets
        path <- pathSet
        if path.endState contains target
      } yield path
  }

  Note:
    we could also naked data structures with functions (and not OO methods)

  Guidelines for good design:
    name everything you can
    put operations into natural scopes (use private functions, etc...)
    keep degrees of freedom for future refinements

 ✔ Lecture 7.6 - Course Conclusion (5:34) @done (14-06-10 21:18)

   what we've seen:
     higher-order functions
     case classes and pattern matching
     immutable collections
     absence of mutable state
     flexible evaluation strategies (strict/lazy/by name)
   => a useful toolkit + a different way to think about programs

   References:
    Laurent Poulain's Scala ref card
    Twitter's Scala school
    "Programming in Scala" (book)
    "Scala Tour" (web)
    Scala meetups
    Typesafe blog
    Cake solutions' blog

  Next?:
    FP and state (how to mix mutable and immutable?)
    parallelism
    domain specific languages

nice notes :)