[HKT] Value / Type / Kind 와 Higher Kinded Type (Feat. 고차함수)

 

시작 하기에 앞서서..

• 함수도 값이라는것을 이해해야 한다.
• 고차함수란 개념
• Order (일반적으로 차수) 란 일종의 단계이다 (Higher order function : 고차함수)
  이차함수의 차수는 2 다 -> 이차함수의 order는 2다
• 예시는 Kotlin , 일부 Scala

 

Value 의 세계

Value 와 타입

우리는 일반적으로 프로그래밍을 할때, Value(값) 를 다룬다, 이 Value 을 분류하는 방법을 Type 이라고 한다.

val intValue : Int = 5
val doubleValue : Double = 5.0
val functionValue : (Int) -> Int =  { x : Int -> x*2 }
val highOrderFunctionValue : ((Int) -> Int) -> Int =  { fn : (Int)-> Int -> fn(5) }

println(intValue)  // 5
println(doubleValue)  // 5.0
println(functionValue(5))  // 10
println(highOrderFunctionValue(functionValue))  // 10

 

너무 당연하지만, 변수는 값을 담는다

각 변수의 값과 타입은 다음과 같다

    val intValue : Int = 5
    // intValue 의 값은 5, 타입은 Int
  
    val doubleValue : Double = 5.0
    // doubleValue 의 값은 5.0, 타입은 Double
    
    val functionValue : (Int) -> Int =  { x : Int -> x*2 }
    // functionValue 의 값은 x -> x*2 , 타입은 Int -> Int
    
    val highOrderFunctionValue : ((Int) -> Int) -> Int =  { fn : (Int)-> Int -> fn(5) }
    // highOrderFunctionValue 의 값은 fn -> fn(5), 타입은 (Int -> Int) -> Int

(주석의 내용은 보다 일반적인 형태로 작성하였음)

우리는 함수를 파라미터로 받거나, 함수 자체를 리턴하는 함수를 고차 함수(Higher Order Function)라고 한다

 

차 (Order)

High Order Function : 함수는 함수인데 Order 가 높음

Type 을 기준으로  Order 를 살펴보면 다음과 같다.

• Order 0 : Int 나 Double 같은 타입. Order 0 타입(Type) 의 값은 5 또는 5.0 과 같다.
• Order 1: Int -> Int 같은 타입. Order 1 타입(Type) 의 값은 {x -> x*2 } 같은 일반적인 함수
• Order 2 : (Int -> Int) -> Int 같은 타입. Order 2 타입(Type) 의 값은 { fn -> fn(5) } 같은 고차 함수
• Order 3 : ((Int -> Int) -> Int) -> Int 같은 타입

여기서 Order 1 (first-order) 보다 큰 Order 2 이상을 일반적으로 우리는 Higher Order 라고 부른다.

따라서 함수를 받는 함수가 고차함수 (Higher Order 함수) 가 되는 것이다

당연하지만 파라미터 개수는 고차함수랑 아무 관련이 없다

fun plus (x:Int, y: Int): Int = x + y
// 아무도 이 함수를 고차함수라고 부르지 않는다

이 함수의 타입은 (Int, Int) -> Int  이므로 고차함수가 아니다.

 

함수가 하는일

일반적인 함수가 하는일을 살펴보면 다음과 같다.

val functionValue : (Int) -> Int =  { x : Int -> x*2 }
// functionValue 의 값은 x -> x*2 , 타입은 Int -> Int

val createdValueByFunction : Int = functionValue(5)
// createdValueByFunction 의 값은 10, 타입은 Int

println(createdValueByFunction) // 10

위 Function 은 Int 값 하나를 받아서 Int 값을 리턴한다.

따라서 createdValueByFunction 은 Int 값을 리턴받아서, 값은 10, 타입은 Int 이다.

즉 Function은, Value 를 받아서 Value를 만들어 준다. (여기선 5를 받아서 10을 만들었음)

Function 은 Value 를 만들어주니까 value constructor 이다

함수자체도 Value (값) 므로, 
함수를 받는(value constructor 를 받는) 고차 함수도 value constructor 이다.

 

종 (Kind)

Type 은 Value 를 분류했다.

Kind 는 Type을 분류한다.

필자가 지금까지 예시로 든 모든것이 * Kind 에 속하는 예시이다.

*, pronounced "type", is the kind of all data types seen as nullary type constructors, and also called proper types in this context. This normally includes function types in functional programming languages. - 위키피디아

우리가 변수로 선언할 수 있으면 대게 * 에 속하는 타입이라고 보면된다

* Kind 는 일반적으로 변수에 넣어서 사용 할 수 있다 (개인적인 생각임..)

 

Type 의 세계

Type 과 Kind

우리는 일반적으로 프로그래밍을 할때 Type(타입) 을 다루는것도 가능하다.

우리가 자주 사용하는 Class 가 대표적이 예시다.

Class 는 대표적인 사용자 정의 자료형 (== 타입) 이다.

// X는 * Kind 에 속하는 사용자 정의 Type
class X {} 

// Y는 * Kind 에 속하는 사용자 정의 Type
data class Y (val name:Int)

// Z는 * Kind 에 속하는 사용자 정의 Type
object Z {}

 

제너릭 (Generic)

List<T> 같은 타입은,  List<Int>, List<Double> 과 같이 내가 원하는 타입과 함께 사용한다. Generic 덕분이다.

제너릭이 하는 일

일반적인 제너릭한 타입이 하는일을 살펴보면 다음과 같다.

val intList : List<Int> = listOf(1,2,3)
// intList 의 값은 [1, 2, 3], 타입은 List<Int>, Kind 는 *

val doubleList : List<Double> = listOf(1.0,2.0,3.0)
// doubleList 의 값은 [1.0, 2.0, 3.0], 타입은 List<Double>, Kind 는 *

List의 인터페이스 정의는 List<T> 이다.
(T는 제네릭, 실 정의는 아마 공변/반공변의 의도로 E 로 되어있지만 Type임을 뜻하기 위하여 T 로 설명함)

근데 intList 의 타입은? List<Int> 타입이다.

근데 doubleList의 타입은? List<Double> 타입이다.

List<Int> 와 List<Double> 은 다른 타입이다.

List<Int> 와 List<Double> 각각 타입이다.

여기서 우리는 제네릭이 하는 일을 알수있다.

List<T> 는 Int 라는 타입 그 자체를 받아서 List<Int> 라는 타입을 만들어준다.

즉 Generic 이 적용된 타입 List<T> 는 은 Type 을 받아서 Type 을 만들어 준다 (여기선 Int 또는 Double 을 받아서 List<Double> 또는 List<Double> 를 만듬)

List<T> 와 같이 제네릭이 적용되어있는 Type 은, Type 을 받아서 Type을 만들어주니까 Type constructor 이다.

Int 의 Kind 는 * 이다, List<Int> 의 Kind 는 * 이다

그럼 타입을 받기전, List<T> 자체의 Kind는? * -> * 이다.

 

차 (Order)

Value 를 다루는 세상에는 다음과 같은 개념이 있었다.

- Higher Order Function : 함수는 함수인데 Order 가 높은 함수를 고차 함수라고 했다.
- 여기서 Order 1 (first-order) 보다 큰 Order 2 이상을 일반적으로 우리는 Higher Order 라고 부른다고 했다.

이 개념을 고대로~~ Type 의 세상에 적용해보자

High Order Type: 타입은 타입인데 Order 가 높음

Kind 를 기준으로 Order 를 살펴보면 다음과 같다.

• Order 0 : * 같은 Kind. 
• Order 1 : * -> * 같은 Kind. (List <T>, Option<T> 같은)
• Order 2 : (* -> *) -> * 같은 Kind

고차함수의 개념을 잘 생각해보자.

함수를 받는 (value constructor 를 받는) 고차 함수도 value constructor 이다.
-> value constructor 를 받는 value constructor 는 고차 함수다.

그렇다면?
type constructor 를 받는 type constructor 는 고차 타입이 된다

그리고 Higher Order Type 을, Higher Kinded Type 이 라고 한다. (Order 가 높으니까 높은 Kinded)

당연하게도 파라미터의 개수가 고차함수랑 전혀 상관없듯이.. 제네릭 개수는 고차 타입이랑 아~~~무 상관없다. (Map<T,U> 도 그냥 * -> * Kind 이다)

 

Higher Kinded Type (aka HKT)

HKT 라는 개념은 알았다.

class 라는게 지원되어야 class 로 사용자 정의 타입을 정의할 수 있듯,

generic 이라는게 지원되어야 generic 으로 사용자 정의 type constructor 를 정의할 수 있듯

HKT 도 언어적으로 지원되어야 사용자 정의 HKT 를 정의할 수 있다.

 

일단 Java / Kotlin / C# / F#... 등 다양한 언어가 HKT 를 지원하지 않는다. (함수형 언어인 F# 조차 도!)

서드파티로 지원을 할 수는 있는데, 공식적인 기능은 아니므로, 문법이 좀 괴랄해진다.

 

Scala 는 지원한다, Haskell 은 뭐... 당연히 지원한다.

아래는 Scala 의 Functor HKT 예시 이다.

trait Functor[F[_]]:
  def map[A, B](x: F[A], f: A => B): F[B]

딱봐도 제네릭처럼 생긴 F[_] 을 보자.  scala 에서는 type constructor 를 _ 로 표현한다고 하니까,
Functor 는 F[_] 를 받으니까 HKT 이다.

먼차이냐.. 다시 확인해보자

- Int 나 string 는 타입이다.

- Option 은 type constructor 이다, int 같은걸 받으면 Option[int], string 을 받으면 Option[string]

그럼 List[A[_]] (HKT 활용) 과 List[T] (제네릭 활용) 이 있다고 하면 다음과 같은 차이를 보인다

// HKT List[A[_]]
case class List[A[_]](list: List[A[Int]])
val list: List[Option] = List(Option(1), Option(2), Option(3))
// List(Some(1), Some(2), Some(3))


// Generic List[T]
case class List[T](list: List[T])
val list: List[Int] = List(1, 2, 3)
// List(1, 2, 3)

// Generic List[T] 에서는 HKT 같은 방식이 불가능하다. 
val list: List[Option[int]] = List(Option(1), Option(2), Option(3))
// 위와 같이 아예 타입인 Option[int] 가 들어가야한다.
// 그러나 HKT 를 이용한 방식에는 그냥 A <- 여기에 Option 자체가 들어간것을 알수있다.

 

 

 

실제 실용적 예시는 Baeldung (아마 scala 2.5?)에서 가져온 예시를 확인해보자 (Monad로 설명하려 했으나, 범위를 넘어가는거 같기도 하고, Scala 가 3.0 이 되고 문법이 변경되어서 이해가 잘 안됨...)

//BatchRun 은 HKT
trait BatchRun[M[_]] {
  def write[A](item: A, db: M[A]): M[A] = transform(item, db)
  def transform[A](item: A, db: M[A]): M[A]
}

//List는 type constructor
val listDb: List[String] = List("data 1", "data 2")

//type constructor 를 받는 BatchRun
//List<T> 로 선언된 클래스를 사용할 때 타입 Int 를 넣어  List<Int> 로 만들듯이
//HKT 인 BatchRun 은 사용할때  type constructor 인 List 를 넣어 BatchRun[List] 로 
var listBatchRun = new BatchRun[List] {
  def transform[A](item: A, db: List[A]): List[A] = db ::: item :: Nil
}

val savedList = listBatchRun.write("data 3", listDb)
assertEquals(savedList, List("data 1", "data 2", "data 3"))

val seqDb: Seq[Int] = Seq(1, 2)


//type constructor 를 받는 BatchRun
//Seq<T> 로 선언된 클래스를 사용할 때 타입 Int 를 넣어  Seq<Int> 로 만들듯이
//HKT 인 BatchRun 은 사용할때  type constructor 인 Seq 를 넣어 BatchRun[Seq] 로 
val seqBatchRun = new BatchRun[Seq] {
  def transform[A](item: A, db: Seq[A]): Seq[A] = db :+ item
}

val savedSeq = seqBatchRun.write(3, seqDb)
shouldEqual(savedSeq, Seq(1, 2, 3))

 

Value 의 세계에서 고차함수를 사용하여 다양한 문제를 해결하듯이,

Type 의 세계에서는 HKT 를 사용하여 다양한 문제를 해결 할 수 있다.

 

Ref

• Higher-Kinded Types | Baeldung on Scala
• generics - What is a higher kinded type in Scala? - Stack Overflow
• Kind (type theory) - Wikipedia