Scala Brown Bag Lunch Series

Day 1

Introduction to Developing in Scala

Setup of tool chain
Value Types
Simple functions

Day 2

Lists and Pattern Matching

List[T]
Creating a List using the cons operator
Creating a List using the apply method
List.filter
List.map
List.withFilter
Pattern matching to denature list into head and tail

Day 3

Talk about solution to factorial problem from the exercises. Another way to create lists:

List(1 to 10: _*)

More pattern matching on Lists:

val a :: b = "Hello World".split(" ").toList
// b is the tail, we don't want that
val a :: b :: _ = "Hello World".split(" ").toList

// Since split returns an Array, match directly
val Array(a, b, _*) = "Hello World".split(" ")

// or use the same syntax for List
val List(a, b, _*) = "Hello World".split(" ").toList

Note the two ways to use _*:

_* Pattern matches any number of elements
x: _* Unwraps the sequence x to a naked sequence

On to the factorial exercise for this week... Show non tail recursive form:

def factorial(n: Int) = n match {
  case 0 => 1
  case n => n * factorial(n - 1)
}

Note the use of match right after the equals sign. No need for extra braces in the compact style of Scala. You could have used a guard here to say:

case n if n <= 0 => 1

Right now, this is a partial function. It's not defined for numbers less than zero. Show this fails for large numbers with a stack overflow

Go over tail recursive form:

def factorial(n: Int) = {
  @tailrec
  def final accumulatingFactorial(acc: Int, n : Int): Int = {
    if (n == 0) acc
    else accumulatingFactorial(n * acc, n - 1)
  }
  // Notice how we could have used a match here:

  accumulatingFactorial(1, n)
}

A function call is said to be tail recursive if there is nothing to do after the function returns except return its value. Since the current recursive instance is done executing at that point, saving its stack frame is a waste. Specifically, creating a new stack frame on top of the current, finished, frame is a waste. A compiler is said to implement TailRecursion if it recognizes this case and replaces the caller in place with the callee, so that instead of nesting the stack deeper, the current stack frame is reused. This is equivalent in effect to a "GoTo", and lets a programmer write recursive definitions without worrying about space inefficiency (from this cause) during execution. TailRecursion is then as efficient as iteration normally is.

Why final? Scala compiler will optimize any tail recursion function only if it is sure that the same function will not be overridden. Since any sub class which overrides the function can change the implementation to a non-tail recursive code. Here we have achieved this by adding the final keyword. The other possible way is to make the function private, which will also prevent the function to be overridden; but this will also reduce the scope of that function. So whether to make it final or private will depend on the design of our code.

Explain how Ranges are like lists, basically Iterable (learn more) Use the foldLeft on the range to get the same results: Show this accumulating pattern as a fold:

Fold Demonstration

Have students stand in a line holding index cards with a number written on them, representing a list of Ints. Create an index card with the accumulator seed value. Pass the accumulator to the leftmost person in the line. Each student then adds the accumulator value and their value and writes it on a new card, which they pass to their left as the accumulator for the next person. When everyone is finished, the final value of the accumulator is the result of the fold. Contrast this with how imperatively we would have used a variable, an index card with a value, that we update by crossing out the number and replacing it with a new one. This is different from how we created a new accumulator value each time in the fold.

You can do the exercise again, but this time also passing the function to be performed along with the accumulator. We did addition, but any function of the form (Int, B) => B can be passed.

def factorial(n: Int) = (1 to n).foldLeft(1)((acc, n) => n * acc)

def factorial(n: Int) = (1 to n).foldLeft(1)(_ * _)

def factorial(n: Int) = (1 to n).product

Talk about the difference in foldLeft vs foldRight Introduce reduce over types that have an identity element

References:

Day 4

Collections Hierarchy and Inheritance

Traits - Behavior that can be mixed in. No constructor. Just collection of behaviors. Traits can have only type parameters. No constructors. They are layered in the order they are mixed in, shadowing variables and methods. A class can mix-in multiple traits.

Abstract Class - From Java. Classes where there are unimplemented methods. Abstract classes can have constructor parameters as well as type parameters. A class can inherit from only one Abstract Class.

Object - A singleton. Static data. Behaviors.

Class - A type of object that can be instantiated.

Case Class - Special type of class

Iterable A collection which you can iterate through Map, Seq, Set

Sequence A sequence is a kind of iterable that has a length and whose elements have fixed index positions, starting from 0. Linear Sequences: List, Queue, Stack, Stream Indexed Sequence: Range, Vector

Quickly go over other sequential collections. Why you should use the least specific class. (Is this true?) All the collection classes have a common pipeline interface of map, filter, etc.