대수적 자료형(ADT)를 시작할 때 참조한 문서를 기반으로 공부했다. 

http://tpolecat.github.io/presentations/algebraic_types.html







스칼라 문서를 보다보면, Algebraic Data Types, ADT(대수적 자료형)이 언급된다. 

ADT를 이해하려면 카테시안 곱의 이해를 배경으로 한다.  먼저 수학적인 집합부터 얘기해 본다.


(참조)

https://en.wikipedia.org/wiki/Algebraic_data_type




먼저 Ordered Set(순서 집합)이라는 것을 보자.

Ordered Set은 2 개 이상의 변수가 순서를 가진 함수 또는 레코드를 표현한 타입이다. 

(x, y) 이런 형태를 가지고 있다. 




이제, Cartesian Product(카테시안 프로덕트, 카테시안 곱, 곱 집합)을 이해해 보자. 


SQL에서 Join을 다룰 때 나오는 용어와 같은데, 두 집합 A와 B의 원소가 있을 때, 이를 통해 만들어지는 모든 순서쌍 (a, b)들의 집합이다. 수학적으로 표현하면, 'a∈A 이고 b∈B 인 모든 순서쌍 (a,b)들의 집합'이라 할 수 있겠다.

그리고, AxB라고 한다. 


A = { 1, 2}, B = {x, y} 라면, A x B = { (1,x), (1,y), (2,x), (2,y) }이다. 





이제, 스칼라로 집중해 본다.


스칼라의 특정 타입에 대한 '값의 개수'를 가진다. Nothing은 없고, Unit은 1개, Boolean은 true와 false, Byte는 256개, String은 엄청나게 많은 값의 개수를 가진다. 


카테시안 곱을 사용하면, 아래와 같은 타입을 가질 때 가질 수 있는 모든 타입의 개수는 다음과 같다. 


(Unit , Boolean) = 1 × 2 = 2 

(Byte , Boolean) = 256 × 2 = 512



ADT는 합성된 타입(Composit Type)을 기반으로 유한한 값의 개수와 잘 정해진 타입으로 이루어지는 형태를 말한다. 즉, 집합적 개념에서 보면, 모두 합쳐면 모든 세상을 만들 수 있는 것을 말한다. 


Option이 대표적인 ADT라 할 수 있다. Option은 다양한 값을 표현하는 Some과 아무 것도 없음을 의미하는 None으로 만들어져 있다. 이와 비슷하게 Either와 Try가 있고, List는 Lil과 일반 리스트가 존재한다. 



sealed trait Option[+A] case object None extends Option[Nothing] case class Some[A](a: A) extends Option[A]



sealed trait Either[+A, +B] case class Left[A](a: A) extends Either[A, Nothing] case class Right[B](b: B) extends Either[Nothing, B]




sealed trait Try[+A] case class Success[A](a: A) extends Try[A] case class Failure[A](t: Throwable) extends Try[A]




sealed trait List[+A] case object Nil extends List[Nothing] case class ::[A](head: A, tail: List[A]) extends List[A] object List { def apply[A](as: A*): List[A] = ... }







스칼라에서 ADT는 sum type을 의미한다. 


아래 코드 처럼 Pet이라는 sealed trait가 있고, Pet은 딱 3 종류의 타입 Cat, Fish, Squid만 존재하게 한다. ADT에서 말한대로 한정된 타입이 존재한다. 


스칼라에서 Pet 하위 클래스를 사용할 때, ADT와 스칼라 컴파일러 간의 연관성을 확인해 본다.


sealed trait Pet
case class Cat(name: String) extends Pet
case class Fish(name: String, color: String) extends Pet
case class Squid(name: String, age: Int) extends Pet

val bob: Pet = Cat("matt")

스칼라에서의 ADT 타입은 sum type을 의미하는데, 특정 상위 클래스를 상속한 여러 case class 클래스로 만드는 경우를 의미한다. 


Encoding을 Pet <-- Cat, Fish, Squid로 진행하고,

Decoding을 Pet match { ... } 으로 진행하는 경우이다. 



sum type은 tagged_union(태그 유니온, 혹은 꼬리가 붙은 유니온)이라 불린다.  자세한 내용은 위키를 참조한다. 


(참고)

https://en.wikipedia.org/wiki/Tagged_union






예문을 실행해본다.



Pet의 하위 클래스인 Cat과 Squid에 대한 패턴 매칭을 시행한다. 

object Pet {
sealed trait Pet
case class Cat(name: String) extends Pet
case class Fish(name: String, color: String) extends Pet
case class Squid(name: String, age: Int) extends Pet
}

object Main extends App {

import com.google.Pet._

val bob: Pet = Cat("Matt")

def sayHi(pet: Pet): String =
pet match {
case Cat(n) => "Meow " + n + "!"
case Fish(n, _) => "Hello fishy " + n + "."
case Squid(n, _) => "Hi ssss " + n + "."
}

println(sayHi(Cat("Bob")))
println(sayHi(Squid("Steve", 10)))
}

결과는 다음과 같다. 


Meow Bob!

Hi ssss Steve.




하지만, Squid 에 주석을 달면 컴파일 에러가 난다. 



object Pet {
sealed trait Pet
case class Cat(name: String) extends Pet
case class Fish(name: String, color: String) extends Pet
case class Squid(name: String, age: Int) extends Pet
}

object Main extends App {

import com.google.Pet._

val bob: Pet = Cat("Matt")

def sayHi(pet: Pet): String =
pet match {
case Cat(n) => "Meow " + n + "!"
case Fish(n, _) => "Hello fishy " + n + "."
//case Squid(n, _) => "Hi ssss " + n + "."
}

println(sayHi(Cat("Bob")))
println(sayHi(Squid("Steve", 10)))
}


런타임 아닌 컴파일 타임 때 exhautive 에러를 발생한다. (전문 용어로 패턴 매칭의 Exhaustiveness Checking 이라 한다) 컴파일러로 하여금 코드를 신뢰성 있게 개발할 수 있도록 도와준다.

 

Warning:(39, 5) match may not be exhaustive.

It would fail on the following input: Squid(_, _)

    pet match {








ADT에 대해서 감이 잡혔으면, 아래 블로그로 공부하면 감이 더욱 잡힌다.


https://bertails.org/2015/02/15/abstract-algebraic-data-type/




Posted by '김용환'
,