hanbzu

// We want to compute the total length of a buffer
var totalLength = 0;
for (var i = 0; i < buffers.length; i++) {
    totalLength += buffers[i].length;
}

// We can do this with map-reduce
var totalLength = buffers.
    map(function (chunk) { return chunk.length; }).
    reduce(function (prev, curr) { return prev + curr; }, 0);

hanbzu

// Scala lists
val xs = "Apple" :: "Mango" :: "Watermelon" :: Nil
xs.length // 3
xs.head // "Apple"
xs.last // "Watermelon"
xs.init // All except last one: List("Apple", "Mango") -- Slower than tail!!
xs.tail // All except first one: List("Mango", "Watermelon") -- Slower than head!!
xs take 2 // It takes the first 2 elements. List("Apple", "Mango")
xs drop 2 // The rest after taking two: List("Watermelon")
xs(2) // xs apply 2 -- Element at position 2: List("Watermelon")

hanbzu

// Pairs are a subset of Scala tuples
val pair = ("answer", 42)
val label = pair._1
val (label, value) = pair // Pattern binding

// Merge sort
// * Separate the list into two sub-lists,
//   each containing around half of the elements of the original list
// * Sort the two sub-lists
// * Merge the two sorted sub-lists into a single sorted list

hanbzu

// We want to be able to sort on lists of any type.
// PARAMETRISATION OF SORT: The most flexible design is to make
// the function polymorphic and to pass the comparison operation
// as an additional parametre
def msort[T](xs: List[T])(lt: (T, T) => Boolean) = {
  val n = xs.length / 2
  if (n == 0) xs
  else {
    def merge(xs: List[T], ys: List[T]) = ???
    val (fst, snd) = xs splitAt n

hanbzu

// An operation for each of the elements in a list
def scaleList(xs: List[Double], factor: Double) = xs match {
  case Nil     => xs
  case y :: ys => y * factor :: scaleList(ys, factor)
}

// A simple way to define map
// In reality it's more complicated because:
// * It works for arbitrary collections, not only lists
// * Its tail recursive

hanbzu

// Filtering elements in a list (here they're kept if positive)
def posElems(xs: List[Int]): List[Int] = xs match {
  case Nil     => xs
  case y :: ys => if (y > 0) y :: posElems(ys) else posElems(ys)
}

// A simple way to define filter
// In reality it's more complicated because:
// * It works for arbitrary collections, not only lists
// * Its tail recursive

hanbzu

// Reduction: We can sum all the elements
// with the usual recursive schema
def sum(xs: List[Int]): Int = xs match {
  case Nil     => 0
  case y :: ys => y + sum(ys)  
}

// But this can be abstracted out using 'reduceLeft'
// That will perform these operations LINKING to the left
def sum(xs: List[Int]) = (0 :: xs) reduceLeft ((x, y) = x + y)

hanbzu

// Vectors, externally, are similar to Lists
val nums = Vector(1, 2, 3, -88)

// But instead of :: we use:
9 +: nums // Vector(9, 1, 2, 3, -88)
nums :+ 9 // Vector(1, 2, 3, -88, 9) -- : always points to the sequence

// Arrays and String support the same ops as Seq,
// but are not a Seq (because they come from Java),
// but can be converted to a Seq

hanbzu

// Ways to create Streams
val xs = Stream.cons(1, Stream.cons(2, Stream.empty))
val ys = Stream(1, 2, 3) // Using Stream as a factory
(1 to 1000).toStream // Stream(1, ?) -- Tail not yet evaluated

// Comparing Streams to Lists
def streamRange(lo: Int, hi: Int): Stream[Int] =
  if (lo >= hi) Sream.empty
  else Stream.cons(lo, streamRange(lo + 1, hi))
def listRange(lo: Int, hi: Int): Stream[Int] =

hanbzu

class Pouring(capacity: Vector[Int]) {

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

  // Moves
  trait Move {
    // A method that defines state changes
    def change(state: State): State