Tag: notes

Scala Notes: Pattern Matching

Pattern matching lets you automatically execute code based on some piece of data. Scala uses pattern matching often, such as when you parse XML or pass messages between threads. Basic syntax of pattern matching is as follow.

    target match { case _ => result }

Following are the important aspects of pattern matching:

Pattern matching works a bit like a switch statement.

def dochore(chore:String):String = chore match{
    case "A" => "A"
    case "B" => "B"  
    case  _  => "C"
}

A pattern matches a target if it is structurally equivalent to the pattern in question. If multiple pattern matches the target, Scala chooses the first matching case.

List(1,2,3) match { case _ => 42} // => 42
List(1,2,3) match { case h::t => h}    // => 1 
List(1,2,3) match { case h::t => t}     // => List(2,3)

If none of the patterns matches with the target, MatchError occurs. A MatchError indicates that the none of the cases in a match expression matched the target.

List(1,2,3) match {case Nil => 42}     // => `MatchError` at runtime.

Next, we outline few concrete examples.

Examples

Example1: Computing Factorial. To compute a factorial in Scala, we specify a condition in a guard for each match statement.

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

Example 2: Computing summation of a given List as an argument. To do this, we need to define a function with signature: def sum(l:List[int]) and implement it as follows.

def sum (list:List[Int]) = {
    def sumAux (xs:List[Int], res:Int):Int = xs match {
      case Nil   => res
      case x::xt => sumAux(xt, res+x) <span class="bullet rounded">1</span>
    }

    sumAux (list, 0)
}

Example 3: Computing Product is taken from Functional Programming in Scala book.

sealed trait List[+A]
case object Nil extends List[Nothing]
case class(head: A, tail:List[A]) extends List[A]

def product(ds: List[Double]): Double = ds match{
    case Nil => 1.0
    case Cons(0,0,_) => 0.0 
    case Cons(x, xs) => x * product(xs)   
}
Advertisement

Gist: Scala Set

In Scala, an instance of Set can be declared as follows.

val s = (1 to 6).toSet

Principle difference between sets and sequences are three:

  • Sets are unordered
val s = (1 to 6).toSet
//> s : scala.collection.immutable.Set[Int] = Set(5, 1, 6, 2, 3, 4)
  • Sets do not have duplicate elements
s map (_ % 2 ==0)
//> res8: scala.collection.immutable.Set[Boolean] = Set(false, true)
  • The fundamental operation on set is contains.
s contains 5
//> res9: Boolean = true

Scala Notes: Fold

Fold is a general purpose operation on list (e.g., List[A]), which involves iterating (over each element) and applying a binary function–

f: A -> B -> B

to reduce the list to a single result, i.e., B. The initial value of B is provided as an argument and then at each stage of the operation, f is applied to the successive elements of List[A], with B that has been accumulated so far.

In this post, we implement and explain key characteristics of foldRight and foldLeft.

Fold Left

Following diagram illustrates generic foldLeft, where the initial value is given by a.

foldLeft

As the name suggests, the iteration starts from the left. Evidently, the signature of the function follows–

foldLeft: A List -> B -> (A -> B -> B) -> B

Tail-recursive implementation of foldLeft is outlined next.

  def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B =
    l match {
      case Nil => z // contains result
      case x :: xs => foldLeft(xs, f(z, x))(f)
    }

The above length can be implemented using foldLeft as follows:

def lengthTR[A](l: List[A]) = foldLeft(l, 0)((acc, _) => acc + 1)

Fold Right

foldRight is quite similar to foldLeft, yet there are some subtle differences. To begin with, the unwinding phase starts from the end of the list. In effect, iteration direction is from the right to left. As a result, foldRight is not a tail-recursive function. Following illustrates foldRight function —

foldLeft

We can implement foldRight as follows.

def foldRight[A,B](l:List[A], z:B)(f: (A,B) => B): B =
    l match{
        case Nil => z
        case x::xs => f(x, foldRight(xs, z)(f))
    }

To show how it works, let’s apply it in implementing length of a List.

def length[A](l: List[A]) = foldRight(l, 0)((x,y)=> y+1)

As noted earlier, we can see that the unwinding phase start after reaching at the end of the List and thus, foldRight is not a tail-recursive function.

During the execution of foldRight, Nil gets replaced by the value of z, the second argument of foldRight, whereas every Con gets replaced by an invocation of f.

References

The images used to explain foldLeft and foldRight are taken from “Elements of Functional Programming” by Chris Reade.

Scala Notes: Functions

Functions in Scala can be defined simply as follows:

def fnname (args)={ 
  // function body
}

def double(i:Int) = i*2

Implementing loop can be done in following manner.

def whileLoop{
  var i = 1
  while (i<=3) {
    println (i)
  }
}

Function that takes other functions as a parameter, or that returns a function as the result, are called higher order function. One thing that is particular to functional programming is that it treats function as value. This provides a flexible way to compose programs.

def totalResultOverRange(number:Int, codeBlock: Int => Int):Int = {
    var result = 0;

    for ( i <- 1 to number) {
     result = result + codeBlock(i)
    }

    return result;
}                                               //> totalResultOverRange: (number: Int, codeBlock: Int => Int)Int


totalResultOverRange(11, i => i)                //> res0: Int = 66

totalResultOverRange(11, i =>if (i%2 == 0) 0 else 1)
                                              //> res1: Int = 6

totalResultOverRange(11, i => 1)                //> res2: Int = 11