Scala Study Notes

Table of Contents

1 Functional Programming on Coursera

1.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 = {
        val r = util.Random.nextInt
        () => r
    // returns the same result every time you call test(),
    // "val" will be printed after definition
    def test: () => Int = {
        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) => x*x) x => x*x) // ignore the parenthese _ % 2 == 0) // ignore the parameter, using the placeholder for expression // using the placeholder for function // ignore the placeholder for function

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

1.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. => p._1 * p._2)
{case (x,y) => x * y})
//{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`.

1.4 Implicit

1.4.1 Implicit Parameter

Implicit parameter looks similar to default parameter, but their principles are completely different. Default parameter has a default value to be used when the parameter is not given. Implicit parameter will search the context to get an appropriate value/variable as parameter.

abstract class Logger {def log(s: String)}
class FileLogger extends Logger {
  def log(s: String) {println("Log in file: " + s)}
class StdoutLogger extends Logger {
  def log(s: String) {println("Stdout: " + s)}
def Add(a: Int, b: Int)(implicit logger: Logger) {
  val sum = a + b
  logger.log("%d + %d = %d".format(a, b, sum ))
implicit val log = new FileLogger
Add(2,3)(new StdoutLogger) //you may do it explicitly

If there is no implicit val log = new FileLogger, the compiler will report error. It is similar to injection by type.

Question: what if there are two possible candidates in the context?

1.4.2 Implicit Function

1.4.3 Implicit class

1.5 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


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

1.6 Stream, Iterator, Generator and lazy

1.6.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 #::>x._1+x._2)
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.

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

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

2 Principles of Reactive Programming on Coursera

2.1 Monad

Honestly, I don't understand it. But I collect my thoughts about it here. First, the monda is used to chain operations and if the first (preceding) operation fails, the whole chain stops. An example that I understand is the usage of for-expression with pattern match. If the pattern matches, go next operation, else skip this element.

Another point of view is about the unit operation. A monad flatMap with its unit operation will return the monad itself.

My conclusion:

A monad is a container that supports operation chain and follows the monad laws. The basic operations of this container are flatMap and unit, where flatMap actually accepts a function that maps each element to a container, then binds these containers together; unit returns a container given an element. Monad laws guarantee the reliability of operation chain on these contains.

Monad seems like a design pattern that enables the operation chain along with pattern match in functional programming. Because flatMap chain with different functions is equivalent to nested flatMap, the for-expression is a syntax sugar based on flatMap chain. The advantage of this design pattern is avoding side effect.

Generator is created by yield as well as for-expression. Pay attention, there is no generator class/type/trait. The genrator created through for-expression has the same type of the sequence/iterator/stream used in for-expression. That proves the for-expression is a syntax sugar of monad types. So, guess what will happen when we create a for-expression using both list and stream?

val fibo:Stream[Int] = 1 #:: 1 #::>x._1+x._2)
val l = List(1,2,3,4,5)
val lsg = for{x <- l; fib <- fibo} yield (x,fib)// infinite loop, crash the software/your machine
val slg = for{fib <- fibo; x <- l} yield (x,fib)// return a stream

Following the definition of Monad, the first mixture lsg actually makes l flatMap (x => fibo), which returns a List that tries to expand infinite stream fibo, hence block your machine. The second mixture slg returns a Stream that expand the list l, hence, works well. Besides, I have to clarify one thing: different monads demonstrated above all accept GenTraversableOnce as parameter and return monad of their own type. That is why they can be mixed together and the first expression decides the type of the final output of for-expression.

2.2 ScalaCheck & ScalaTest

It is a tool for property-based testing for scala. It has NO external dependencies and integrated in the test frameworks ScalaTest. It can also be used standalone, with its built-in test runner.

2.2.1 Tutorial of ScalaCheck

First, create a class that extends class org.scalacheck.Properties with the name of data object that you want to test. It is used for the library to generate test data to test your algorithm.

Second, create test case by

property("NAME_OF_FUNCTION") = forAll{

forAll is the function org.scalacheck.Prop.forAll.

Third, to run the tests, you can put the properties in src/test/scala then use test task to check them.

2.2.2 ScalaTest

In the example provided by the oneline course, they used JUnit, ScalaTest and ScalaCheck together, which is much more complext than the tutorial. In their example, the class of Properties is in src/main/scala and is called by another class defined under src/test/scala. In the class under test folder, many instances of the Properties class are created to check different children classes of the target class.

class QuickCheckSuite extends FunSuite with Checkers {
  def checkBogus(p: Prop) {
    var ok = false
    try {
    } catch {
      case e: TestFailedException =>
        ok = true
    assert(ok, "A bogus heap should NOT satisfy all properties. Try to find the bug!")
  test("Binomial heap satisfies properties.") {
    check(new QuickCheckHeap with BinomialHeap)
  test("Bogus (1) binomial heap does not satisfy properties.") {
    checkBogus(new QuickCheckHeap with Bogus1BinomialHeap)
  test("Bogus (2) binomial heap does not satisfy properties.") {
    checkBogus(new QuickCheckHeap with Bogus2BinomialHeap)
  test("Bogus (3) binomial heap does not satisfy properties.") {
    checkBogus(new QuickCheckHeap with Bogus3BinomialHeap)
  test("Bogus (4) binomial heap does not satisfy properties.") {
    checkBogus(new QuickCheckHeap with Bogus4BinomialHeap)
  test("Bogus (5) binomial heap does not satisfy properties.") {
    checkBogus(new QuickCheckHeap with Bogus5BinomialHeap)
  • This class uses the junit framework for unittest. JUnit will invoke the class with @RunWith annotation (extend by type hierarchies) to run the tests. The annotation parameter in the example is a class of the type JUnitRunner. In fact, any class extends Runner is acceptabel. Notice that function classOf acts the same as obj.getClass().
  • The annotation uses class of JUnitRunner as parameter. This class is provided by scala-test framework. TODO
  • org.scalatest.FunSuite and org.scalatest.prop.Checkers.

Author: Xiao LIU

Created: 2015-02-28 Sat 22:40

Emacs 24.4.1 (Org mode 8.2.10)