## Scala 7 - Datatypes2 본문

Tutorials/Scala

### Scala 7 - Datatypes2

머니덕 2019. 4. 23. 19:02

스칼라 튜토리얼, 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.

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

#### 'Tutorials > Scala' 카테고리의 다른 글

 Scala 9 - Sub Types  (0) 2019.04.23 2019.04.23 2019.04.23 2019.04.23 2019.04.23 2019.04.23