Functional Programming on Coursera

1 Lambda function

  • function is value, 
    val f = (x:Int) => x*x

    One difference between def f = ... and val f = ... is: def is evaluated on call and returns a new function instance every time. 

    val test: () => Int = {
    println("val")
    val r = util.Random.nextInt
    () => r
}
// returns the same result every time you call test(),
// "val" will be printed after definition

def test: () => Int = {
    println("def")
    val r = util.Random.nextInt
    () => r
}
// returns the difference results every time you call test(),
// "def" will be printed every time you call it.

val tt = test
// acts like the first example

val test = () => util.Random.nextInt
def test = () => util.Random.nextInt
// they are the same from behavior, you have to call the function by test()
// the def declaration actually defined a function that returns a function.
// if you type test without parenthesis, you will receive a function value.

def test = util.Random.nextInt
// this line directly assign the test function to the nextInt function,
// you can call the function directly by name without the parenthesis

    method/expression starts by def will be evaluated when you call obj.f while those starts by val will be evaluated once. In addition, if you declare a val that assigns to def, the def will be evaluated immediately, and the new val acts like the first case in the examples above.

  • Abbreviation: 
    val l = List(1,2,3)
l.map((x) => x*x)
l.map( x => x*x) // ignore the parenthese
l.map( _ % 2 == 0) // ignore the parameter, using the placeholder for expression
l.map(f(_)) // using the placeholder for function
l.map(f) // ignore the placeholder for function

2 Type hierachy

abstract class is like Java, trait is like interface in Java. However, trait can have parameters and defined methods. In addition, trait is not abstract class since it cannot has constructors.

  • Logical problem: is List<Parent> the parent of List<Childe>?

    It is not true for mutable collection. 

    var s = new Array[Man](new Man())
var t:Array[Human] = s
t[0] = new Woman()
var m:Man = s[0]// what is it? man or woman?

    But we can use imutable collection.

  • Covariant, Contvariant, Invariant
    • Covariant: defined by Class<+T>, Class<Parent> is the parent of Class<Child>
    • Contvariant: defined by Class<-T>, Function<Parent> is the child of Function<Child>

    The principle is: child type can do anything that can be done by parent type.

  • Check Rules and Boundary

    To avoid conflict, the compile force the +T can only be used for returned type, the -T can only be used for argument type. A method to by pass this problem is using boundary. 

    class List<+T>{
     def prepend[U >: T](U elem)
}

    Notice that in generic type definition, one can use A>:B and A<:B to add constraint to the meta type.

3 Pattern match

Case class enables you to make classes with different parameters 

abstract class CodeTree
case class Fork(left: CodeTree, right: CodeTree, chars: List[Char], weight: Int) extends CodeTree
case class Leaf(char: Char, weight: Int) extends CodeTree

For the classes listed above, you cannot directly access to any paramter (field) of Fork or Leaf. You have to use case Fork(a,b,_,_) to access to the paramters.

case match can also be used in lambda function as a short version. 

List.map(p => p._1 * p._2)

List.map({case (x,y) => x * y})
//List.map{case (x,y) => x * y} also works

Option calsss used for the condition that the returned type can be empty/null, etc.

If you want to match a variable in context, you have to weither use a capitalized variable name Variable or wrap it by backticks `variable`.

4 Collections

  • List is a chain while Vector is a tree that each node is an array that contains 32 elements. Vector groups in depth slowly log_{32}(N). Important functions: map, filter, reduceRight, reduceLeft, foldRight, foldLeft, flatten, flatMap, take, drop, takeWhile, =dropWhile, span, group, groupBy.

    Sequence as parameter list is represented by this(par: T*).

  • Map.
    • The + and ++ operations overwrite the existing key.
    • Initialized by Map(k1->v1, k2->v2, k3->v3)
    • Set default value by withDefaultValue, this function returns a new map (everything in this course are immutable).

5 Stream, Iterator, Generator and lazy

5.1 Stream

Stream, acts like sequence, but it does not evaluate until be called. It can be used to ignore unecessary computation and coding infinite concepts. 

val fibo:Stream[Int] = 1 #:: 1 #:: fibo.zip(fibo.tail).map(x=>x._1+x._2)
println(fibo.take(10).toList)

def from(n: Int): Stream[Int] = n #:: from(n+1) // infinite integer stream starts from n
// recursive stream
def sieve(s: Stream[Int]): Stream[Int] =
   s.head #:: sieve(s.tail filter (_ % s.head !=0)) // stream of primes 质数

val primes = sieve(from(2))
primes.take(10).toList // the first 10 primes starts from 2.

Three ways of using stream

  • Transform from other collections, then you use functions like map, etc. to generate new stream.
  • elem #:: Stream
  • Transform from iterator, use for loop to create an iterator with what you want and then convert it into a stream.

Because Stream has consistent API as List/Seq/Vector, you can use it as if you have a collection that contains everything.

5.2 Iterator

The difference between stream and iterator is stream memories the values while iterator doesn’t.

Iterator can be used in for-expression. For-expression can also use pattern match. 

for{ pattern(x) <- seq; pattern2(y) = x(k); ...} yield ...

As show in the example above, you can apply pattern to loop on the elements of sequence, you can even add some simple statements in the for-expression. It is equivalent to: 

seq.withFilter({case pattern(x) => true; case _ => false})
   .map({case pattern(x) => x(k)})
   .withFilter({case pattern2(y) => true; case _ => false})
   .map({case pattern2(y) => y})
   ...

The function withFilter returns a FilterMonadic, which provides four functions flatMap, map, foreach, withFilter. It works like list of call backs in programming point of view. From wikipedia: /In functional programming, a monad is a structure that represents computations defined as sequences of steps: a type with a monad structure defines what it means to chain operations, or nest functions of that type together.

5.3 lazy val

lazy val is only evaluated once when called. You can also define a lazy parameter by def myFUnc[T](param: => T), then the parameter will be evaluated when it is called in myFunc if the param is returned by an expression/function.