Scala 7 - Datatypes2

스칼라 튜토리얼, scala datatypes part2

---

Pattern Matching

• A way to use algebraic datatypes

Syntax:

e match {
  case C1(...) => e1
  ...
  case Cn(...) => en
}

• Example :

sealed abstract class IList
case class INil() extends IList
case class ICons(hd: Int, tl: IList) extends IList
def x: IList = ICons(2, ICons(1, INil()))

def length(xs: IList) : Int =
  xs match {
    case INil() => 0
    case ICons(x, tl) => 1 + length(tl)
  }

length(x)   // result will be 2

By using pattern matching, it gives us the length of x with recursion.

---

Advanced Pattern Matching

e match {
  case P1 => e1
  ...
  case Pn => en
}

One can combine constructors and use _ and | in a pattern.
(E.g) case ICons(x, INil()) | ICons(x, ICons(_, INil())) => …
When you use | pattern, you should use _ to ...

The given value e is matched against the first pattern P1.
If succeeds, evaluate e1.
If fails, e is matched against P2.
If succeeds, evaluate e2.
If fails, …

The compiler checks exhaustiveness(ie, whether there is a missing case).

• Example :

sealed abstract class IOption
case class INone() extends IOption
case class ISome(some: Int) extends IOption

def secondElmt(xs: IList) : IOption =
    xs match {
        case INil() | ICons(_, INil()) => INone()
        case ICons(_, ICons(x, _)) => ISome(x)
    }

secondElmt(ICons(3, INil()))
secondElmt(ICons(3, ICons(2, INil())))

What if we write code like this?

def secondElmt(xs: IList) : IOption =
    xs match {
        case ICons(_, INil()) => INone()
        case ICons(_, ICons(x, _)) => ISome(x)
    }

It causes error : INil() is missing... We have to define pattern mathcing exhaustive(Consider all cases possible when you run pattern mathcing)!

And what if this case?

def secondElmt(xs: IList) : IOption =
    xs match {
        case INil() | ICons(z, INil()) => ISome(z)
        case ICons(_, ICons(x, _)) => ISome(x)
    }

It gives error because when we use certain variable, we have to use it in all of patterns divided by |. Therefore, we can't modify above code as

def secondElmt(xs: IList) : IOption =
    xs match {
        case INil() => ISome(z)
        case ICons(_, ICons(x, _)) | ICons(z, INil())  => ISome(x)
    }
// cannot use variable appearing in only one of the matching test.

Instead, we should write code like

def secondElmt(xs: IList) : IOption =
    xs match {
        case INil() => ISome(z)
        case ICons(_, ICons(x, _)) | ICons(x, INil())  => ISome(x)
    }

It makes sense, since same variable x is used in sinle line, both matching test divided by |.

So, this is legal to use.

def secondElmt(xs: IList) : IOption =
    xs match {
        case INil() => ISome(z)
        case ICons(x, ICons(z, _)) | ICons(x, ICons(z, ICons(_, _)))  => ISome(x)
    }

• Another example :

def secondElmt2(xs: IList) : IOption =
xs match {
  case INil() | ICons(_,INil()) => INone()
  case ICons(_, ICons(x, INil())) => ISome(x)
  case _ => INone()
}

case _ => INone() can be used like else of switch in C language.

---

Pattern Matching on Int

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

// Not safe. If negative value is put, It will loop forever!
def fib(n: Int) : Int =
  n match {
    case 0 | 1 => 1
    case _ => fib(n-1) + fib(n-2)
  }

// More safe code.
def fib(n: Int) : Int =
  n match {
    case _ if n <= 0 => 1
    case _ => fib(n-1) + fib(n-2)
  }

---

Pattern Matching with If

def f(n: Int) : Int = 
  n match {
    case 0 | 1 => 1
    case _ if (n <= 5) => 2
    case _ => 3
  }

def f(t: BTree) : Int =
  t match {
    case Leaf() => 0
    case Node(n, _, _) if (n <= 10) => 1
    case Node(_, _, _) => 2
  }

---

Exercise

Write a function find(t: BTree, x: Int) : Boolean that checks whether x is in t.

• My solution :

def find(t: BTree, x: Int) : Boolean = 
  t match {
    case Leaf() => false
    case Node(n, _, _) if (n == x) => true
    case Node(n, l, r) if (n < x) => find(r, x)
    case Node(n, l, r) if (n > x) => find(l, x)
  }

• Given solution :

def find(t: BTree, i: Int) : Boolean =
  t match {
    case Leaf() => false
    case Node(n,lt,rt) =>
      if (i == n) true
      else find(lt, i) || find(rt, i)
  }

Second solution needs more computation than the first, since it needs to check left BTree even though i > n.

What if we want to return subtree with found value i is the root?

def t: BTree = Node(5,Node(4,Node(2,Leaf(),Leaf()),Leaf()),
    Node(7,Node(6,Leaf(),Leaf()),Leaf()))

def find2(t: BTree, x: Int) : Option[BTree] =
    t match {
        case Leaf() => None
        case Node(n, _, _) if (n == x) => Some(t)
        case Node(n, l, r) if (n < x) => find2(r, x)
        case Node(n, l, r) if (n > x) => find2(l, x)
    }

find2(t, 4)
// res : Option[BTree] = Some(Node(4,Node(2,Leaf(),Leaf()),Leaf()))

In purely functional programming, nothing is copied. Instead, it returns pointer therefore it makes data sharing safe and fast. Writing programs with modification is hard.

---

Type Checking & Inference

• Typed Programming

def id1(x: Int): Int = x
def id2(x: Double): Double = x

At run time, type information is erased(ie, id1 = id2). Typed programming is good for detecting error.

• Untyped Programming

def id(x) = x

It does not care about types at compile time. But, many such languages check types at run time paying cost. Without run-time type check, errors can be badly propagated.

• What is compile-time type checking for?

It can detect errors at compile time, and increase readability. Well-typed programs raise no type errors at run time.

---

Type Checking and Inference

• Type Checking

Syntax : x1: T1, x2: T2, ..., xn: Tn |- e : T

def f(x: Boolean): Boolean = x > 3
// => Type error

def f(x: Int): Boolean = x > 3
// => OK. f: (x: Int) Boolean

• Type Inference

Syntax : x1: T1, x2: T2, ..., xn: Tn |- e : ?

def f(x: Int) = x > 3
// => OK by type inference. f: (x: Int) Boolean

Too much type inference is not good.