cs210.md

CS210

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Fall 2014: Functional Programming

[TOC]

Functions & Evaluations

• imperative programming : modifying mutable variable, assignments, loops, too close to word by word (Von. Neumann)
• oriented-object programming : orthogonal to other paradigm
• functional programming : theory, data types, operations, laws between values and operation, no mutations
• non-primitive expression
  1. take leftmost operator
  2. evaluate its operands
  3. apply the operator to the operands
• primitive types : as in Java but capitalized
• call-by-value : def power(x: Double, y: Int): Double = ...
  1. evaluate all args (left to right)
  2. replace function application by the function
  3. replace formal parameters by actual args
• call-by-name : def power(x: => Double, y: => Int): Double = ...
  1. apply the function to unreduced args
• substitution model : reduce an expression to a value (no side effect) called $\lambda$-calculus
• if call-by-value terminates, then call-by-name terminates too
• def : by-name
• value : by-value
• return value : last element of block

Higher Order Functions

• rewriting rule : $[v_1/x_1,\ldots,v_n/x_n]B$ means expression $B$ in which all occurences of $x_i$ have been replaced by $v_i$
• tail recursion : if a function calls itself as its last action, stack can be reused, it is tail recursive (iterative), @tailrec
• anonymous function : (x: Int) => x*x is the short way (syntactic sugar) of defining def f(x: Int)=x*x;f
• high-order functions : take a function as or/and return a function
• currying : def f(arg1)...(argN)=E equivalent to def f = (arg1 => ... (argN => E))
  • def sum(f: Int => Int)(a: Int, b: Int): Int = ... has type (Int => Int) => (Int, Int) => Int
  • functional type associate to the right

Data & Abstraction

• override to force redefinition
• private member inside classes class Rational(x: Int, y: Int) { priate def... }
• self reference : this
• precondition : class ... { require(y > 0, "blabl") } throws an IllegalArgumentException
• assert : like precondition but emits a AsssertionError
• primary constructor : takes parameters of the class and executes all statements in the class body
• auxiliary constructors : def this(x: Int) = this(x, 1)
• infix notation : any method with a parameter can be used like an infix operator
• relaxed identifiers : alphanumeric, symbolic, underscore (x1 * +?%& vector_++)
• precedence rules : letters, |, ^, &, < >, = !, :, + -, * / %, others
• def unary_op is called when op(object)
• method terminating with a colon associate to the right (not left)
• abstract classes can contain members which are missing an implemenentation
• if no superclass, standard class Object in Java is assumed
• direct and indirect superclasses of a class are called base classes
• object : single-object class called singleton, this is a value
• programs : object Hello { defmain(agrs: Array[String]) = println("hw") }
• dynamic binding like in Java
• package and import : import week3.{Rational, Hello} or import week3._ (wildcard)
• traits : like interface but with concrete methods but cannot have value parameters
• types
  • Any : base type of all types (==, !=, equals, hashCode, toString)
  • AnyRef : base type of all reference types (java Object)
  • AnyVal : base type of all primitive types
  • Nothing : subtype of every other type
• exceptions : similar to Java's
• can be set to null if it is a subclass of Object (type is then Null)

Types & Pattern Matching

• value parameters abreviation : class Ex(val head: Int)
• type parameters : class Cons[T](val head: T) and singleton[T](elem: T) direclty inferred in most of the case
• function are treated as objects in Scala : a function A => B is an abbreviation for scala.Function1[A,B] which is trait Function[A,B] { def apply(x: A): B }
• types bounds : def f[S <: T](r: S) where <: means S subtype of T and >: means supertype of T (even mix both one after the other)
• Liskov Substitution Principle : 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
• variance : mutable is not covariant and are if some conditons are met, if A <: B
  • C[A] <: C[B] covariance C[+A]
  • C[A] >: C[B] contravariant C[-A]
  • C[A] nothing C[B] nonvariant C[A]
  • in general : function contravariant in args and covariant in result trait Function1[-T,+U] { def apply(x: T): U }
  • covariant type may appear in lower bound
  • contrevariant type may appear in upper bound
• case classes : define companion objects with apply methods
• pattern match : e match { case Number(n) => n; case Sum(e1, e2) => ... }
• forms of pattern : contructors, variable (always lowercase), wildcard (_), constants

Lists

• immutable, recursive, homogeneous type
• empty list object Nil
• constrution operation :: : 1 :: 2 :: Nil same as Nil.::(2).::(1)
• list operations
  • head : first element
  • tail : list composed of all elements except first
  • isEmpty
  • length
  • last
  • init : list consisting of all elements exception the last one
  • take n : n first element of the list
  • drop n : rest of list after having taken n
  • (n) : element n
  • ++ ys : add a list to another
  • reverse
  • updated(n, x)
  • indexOf x
  • contains x
  • splitAt n
• pattern match : Nil, p :: ps, List(p1,...,pN)
• tuple : val tuple = (e1,...eN), access to element tuple._i, can be pattern matched
• implicit parameters : avoid passing some type argument msort(implicit ord: Ordering)
• high-order list operations
  • map f
  • filter f
  • filterNot f
  • partition f : (filter f, filterNot f)
  • takeWhile f
  • dropWhile f
  • span f : (takeWhile f, dropWhile p)
• wildcard function : ((x, y) => x*y) is equivalent to (_*_)
• list reduction operation
  • reduceLeft op : ((x1 op x2) op ...) op xN
  • foldLeft z op : ((z op x1) op ...) op xN
  • foldRight z op : x1 op (... (xN op z))
• structural induction : to prove a property P(xs) for all lists xs, show P(Nil) holds (base case), for a list xs and some element x show if P(xs) holds then P(x :: xs) also holds (induction step)

Collections

• vector : better balanced than List
  • +: : add new element in front
  • :+ : add new element at end
• base class of List and Vec are Seq and Iterable
• Arrays and Strings support same operations as Seq but come from Java so no subclass
• Range : evenly spaced integers
  • x until y
  • x to y
  • r by s
• more on Seq :
  • exists p
  • forall p
  • zip ys : pairs down elements
  • unzip
  • flatMap f
  • sum
  • product
  • max
  • min
• pattern match on map : x.map(xy => xy._1*xy._2) is equivalent to x.map{ case (x,y) => x*y }
• for-expression : p filter (i => i > 20) map (i => i.name) is equivalent to `for ( i <- p if i > 20) yield i.name
• for translation
  1. for (x <- e1) yield e2 is e1.map(x => e2)
  2. for (x <- e1 if f; s) yield e2 is for (x <- e1.withFilter(x => f); s) yield e2
  3. for (x <- e1; y <- e2; s) yield e3 is e1.flatMap(x => for (y <- e2; s) yield e3)
• Set : unordered, no duplicates, contains is the fundamental operation- for queries
• Map
  • constructor Map("i" -> 1, "j" -> 2)
  • tuple iterable
  • are function type key => value : capitalOfCountry("US") gives NoSuchElementException is not found
  • result of get is Option value : Some(x) and None
  • default values : withDefaultValue turns map into a total function
• repeated parameter : Polynom(bindings: (Int, Double)*) get all parameters
• queries
  • sortWith p
  • sorted
  • groupBy e

Lazy Evaluation

• streams : like List but tail elements is computed on demand
  • #:: to replace ::
• by-name evaluation : everything in recomputed
• strict evalutation : normal parameters and val definition (default evaluation)
• lazy evaluation : delay until asked lazy val x = expr
• infinite streams : def from(n: Int): Stream[Int] = n #:: from(n+1)