스칼라 강의 (47) ADT (Algebraic Data Types) 이란? (feat. 타입클래스)

스칼라 강의 (47)  ADT (Algebraic Data Types) 이란? (feat. 타입클래스)

"ADT는 정해진 숫자의 타입 군을 구축하는 방법에 관한 이야기. 행동은 상관없다"
"타입클래스는 타입별로 행동을 다르게 하기 위한 이야기."

라고 개인적으론 희미하게 구분하고 있습니다. 참고로 타입클래스는 우리가 알고 있는 그 클래스가 아닙니다. 인터페이스와 비슷한 것으로서 하스켈에서 나온 개념입니다. =>  타입클래스 

죄송하지만 하스켈을 공부해서 ADT에 대한 감을 잡는게 빠른거 같습니다.
(아래 하스켈의 Sum 타입은 자바의 예를들고 있으므로 하스켈 몰라도 이해하기 쉬울 겁니다) 

- 하스켈의 Sum 타입
- [하스켈 기초][CIS194] 대수적 데이터 타입(Algebraic Data Type)

다음 블로그 글도 추천합니다.

스칼라의 대수적 자료형(Algebraic Data Types, ADT), exhaustivity-checking
TypeClass 와 Interface의 차이점 With Kotlin

스칼라에서는 대략 trait 와 케이스 클래스로 ADT 를 정의 하는데 , 아래 예를 보겠습니다.
스칼라는 아시다시피 하이브리드 함수형 언어라, 직접적(간략히)으로 만들 순 없고 먼가 OO틱하게 만들고 있습니다.

Option

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

Either

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]

Try

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

List

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] = ...
} 

다른곳에서 함부러 타입을 추가하지 못하게 제한을 하는 거 봐서 (sealed)  먼가 타입을 만드는데 있어서, 구조화 하고 제한 된 갯수의 타입을 만드는것 같습니다. (합(or) 혹은 곱(and)만큼) 정확한 타입은 패턴매칭을 통해서 분류 가능하고~
이런 ADT 를 이용해서 함수형 프로그래밍을 위한 복합 구성을 하는 것이고~

ADT 와 타입클래스는 어떻게 다른가요?  - 스택오버플로우 발췌

ADT (Algebraic Data Types)와 타입 클래스는 서로 다른 문제를 해결하는 완전히 다른 개념입니다.

ADT

다음과 같이 ADT는 말 그대로 대수적 데이터 타입의 약자이구요. ADT는 데이터를 구조화하는 데 필요합니다. 스칼라에서 가장 근접한 것은 내가 생각하기에, 케이스 클래스와  sealed traits 의 조합인데 이것은 Haskell에서 도 복잡한 데이터 구조를 구성하는 주요 수단입니다. ADT의 가장 유명한 하스켈 예가 아래에 있습니다.

data Maybe a = Nothing | Just a

이 타입은 Option이라고하는 표준 스칼라 라이브러리에 직접적으로 반영 됩니다.

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

이것은 Option이 표준 라이브러리에서 정의 된 방법과 정확히 같지 않지만 포인트를 집어줍니다.기본적으로 ADT는 몇 가지 명명 된 튜플 (0-ary, Nothing / None, 1-ary, Just a / Some (value))의 조합입니다.

다음 데이터 타입을 보세요.

-- Haskell
data Tree a = Leaf | Branch a (Tree a) (Tree a)

// Scala
sealed trait Tree[+T]
case object Leaf extends Tree[Nothing]
case class Branch[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]

이것은 간단한 이진 트리입니다. 이 두 정의는 기본적으로 다음과 같이 이해 할 수 있는데요. "이진 트리는 리프 또는 분기 중 하나이며, 분기인 경우 어떤 값과 두 개의 다른 트리가 포함됩니다". 이것이 의미하는 바는 Tree 타입의 변수를 가지고 있다면 Leaf 나 Branch 중 하나를 포함 할 수 있으며, 필요하다면 어느 것이 있는지 확인하고 포함 된 데이터를 추출 할 수 있다는 겁니다. 이러한 검사와 추출은 패턴매칭 통해서 수행합니다.

-- Haskell
showTree :: (Show a) => Tree a -> String
showTree tree = case tree of
  Leaf                    -> "a leaf"
  Branch value left right -> "a branch with value " ++ show value ++ 
                             ", left subtree (" ++ showTree left ++ ")" ++
                             ", right subtree (" ++ showTree right ++ ")"

// Scala
def showTree[T](tree: Tree[T]) = tree match {
  case Leaf => "a leaf"
  case Branch(value, left, right) => s"a branch with value $value, " +
                                     s"left subtree (${showTree(left)}), " +
                                     s"right subtree (${showTree(right)})"
}

이 개념은 매우 간단하지만 매우 강력한데요.

보시다시피 ADT는 닫힙니다. 즉, 타입을 정의한 후에 더 많은 명명된 튜플을 추가 할 수 없습니다. Haskell에서 이것은 구문적으로 시행되며, Scala에서는 다른 파일에서 하위 클래스를  정의하는 것을 허용하지 않는 sealed keyword를 통해 이 작업을 수행합니다.

그러한 이유로 이러한 타입을 algebraic 이라고합니다. 명명된 튜플은 합계(수학적 의미로도)로서 이러한 튜플의 곱 (수학적 의미에서) 및 '조합'으로 간주 될 수 있으며 이러한 생각은 심오한 이론적 의미를 갖습니다.

 For example, aforementioned binary tree type can be written like this:

Tree a = 1 + a * (Tree a) * (Tree a)

But I think this is out of scope for this question. I can search for some links if you want to know more.

---

타입클래스 

Type classes, on the other hand, are a way to define polymorphic behavior. Roughly type classes are contracts which certain type provides. For example, you know that your value x satisfies a contract which defines some action. Then you can call that method, and actual implementation of that contract is then chosen automatically.

Usually type classes are compared with Java interfaces, for example:

-- Haskell
class Show a where
    show :: a -> String

// Java
public interface Show {
    String show();
}

// Scala
trait Show {
  def show: String
}

Using this comparison, instances of type classes match with implementation of interfaces:

-- Haskell
data AB = A | B

instance Show AB where
  show A = "A"
  show B = "B"

// Scala
sealed trait AB extends Show
case object A extends AB {
  val show = "A"
}
case object B extends AB {
  val show = "B"
}

There are very important differences between interfaces and type classes. First, you can write custom type class and make any type an instance of it:

class MyShow a where
  myShow :: a -> String

instance MyShow Int where 
  myShow x = ...

But you cannot do such thing with interfaces, that is, you cannot make an existing class implement your interface. This feature, as you also have noticed, means that type classes are open.

This ability to add type class instance for existing types is a way to solve expression problem. Java language does not have means for solving it, but Haskell, Scala or Clojure have.

Another difference between type classes and interfaces is that interfaces are polymorphic only on first argument, namely, on implicit this. Type classes are not restricted in this sense. You can define type classes which dispatch even on return value:

class Read a where
  read :: String -> a

It is impossible to do this with interfaces.

Type classes can be emulated in Scala using implicit parameters. This pattern is so useful that in recent Scala versions there is even a special syntax which simplifies its usage. Here is how it is done:

trait Showable[T] {
  def show(value: T): String
}

object ImplicitsDecimal {
  implicit object IntShowable extends Showable[Int] {
    def show(value: Int) = Integer.toString(value)
  }
}

object ImplicitsHexadecimal {
  implicit object IntShowable extends Showable[Int] {
    def show(value: Int) = Integer.toString(value, 16)
  }
}

def showValue[T: Showable](value: T) = implicitly[Showable[T]].show(value)
// Or, equivalently:
// def showValue[T](value: T)(implicit showable: Showable[T]) = showable.show(value)

// Usage
{
  import ImplicitsDecimal._
  println(showValue(10))  // Prints "10"
}
{
  import ImplicitsHexadecimal._
  println(showValue(10))  // Prints "a"
}

Showable[T] trait corresponds to type class, and implicit objects definitions correspond to its instances.

As you can see, type classes are a kind of interface, but more powerful. You can even select different implementations of type classes, while the code which uses them remains the same. This power, however, comes at the cost of boilerplate and extra entities.

Note that it is possible to write Haskell equivalent of above Scala program, but it will require writing multiple modules or newtype wrappers, so I'm not presenting it here.

BTW, Clojure, a Lisp dialect working on JVM, has protocols, which combine interfaces and type classes. Protocols are dispatched on single first argument, but you can implement a protocol for any existing type.