Heterogeneous typed list로 살펴보는 타입레벨 프로그래밍

typelevel.scala

// 7.4.1 Heterogeneous typed list
/*
 Scala는 오버로딩과 오버라이딩 다형성을 안 좋아함. 
 오버로딩은 파라미터의 타입이 런타임시에 지워져 버림
 오버라이딩은 상속을 해야한다는 제한 있음.
 
 Scala는 타입 생성자를 이용한 다형성을 좋아함.
*/

sealed trait HList {}

// 헤드와 테일로 구성
final case class HCons[H, T <: HList](head : H, tail : T) extends HList {
  def ::[T](v : T) = HCons(v,this)
  override def toString = head + " :: " + tail
}

final class HNil extends HList {
  def ::[T](v : T) = HCons(v,this)
  override def toString = "Nil"
}

object HList {
  type ::[H, T <: HList] = HCons[H,T]
  val :: = HCons
  val HNil = new HNil
}

scala> val x = "Hello" :: 5 :: false :: HNil
// x: HCons[String,HCons[Int,HCons[Boolean,HNil]]] = Hello :: 5 :: false :: Nil

scala> val first :: second :: rest = x
// first: String = Hi
// second: Int = 5
// rest: HCons[Boolean,HNil] = false :: Nil

// 특정 인덱스에 삽입, 획득, 제거등을 위한 인덱스뷰
sealed trait IndexedView {
  type Before <: HList  // ex. Before = String :: Int :: HNil
  type After <: HList   // ex. After = HNil
  type At               // ex. At = Boolean
  def fold[R](f : (Before, At, After) => R) : R // 전체 리스트에서 주어진 값을 반환
  def get = fold( (_, value, _) => value) // fold를 사용해서 현재 인덱스의 값을 리턴
}

// 리스트의 한 인덱스에 대한 IndexView는 재귀적으로 만들 수 있음

// 기본 케이스: 리스트의 첫번째 인덱스
class HListView0[H, T <: HList](val list: H :: T) extends IndexedView {
  type Before = HNil  // 빈 리스트
  type After = T      // 현 리스트의 꼬리
  type At = H         // 현 리스트의 머리
  def fold[R](f: (Before, At, After) => R): R = f(HNil, list.head, list.tail)
}

// N번째 케이스: 재귀임, N개의 인덱스에는 N-1 + HListView0 개의 리스트가 있음
// H - 현재 헤드의 타입
// NextIdxView - 다음 IndexedView의 타입
// 예) 3개의 요소를 지닌 HList를 구성하기 위해서는 2개의 HListViewN 클래스와 1개의 HListView0 클래스가 필요함 
// HListViewN 클래스의 각 인스턴스는 HListView0에 리스트의 이전 타입을 하나씩 첨부함
// HListViewN 클래스는 리스트 요소를 참조하며 재귀적으로 리스트 부분들을 빌드함
// 문제는 인덱스가 깊어질수록 재귀호출가 증가함 
final class HListViewN[H, NextIdxView <: IndexedView](h: H, next: NextIdxView) extends IndexedView {
  type Before = H :: NextIdxView#Before // Before의 타입은 현재 타입 파라미터 + 다음 인덱스의 HList
  type At = NextIdxView#At              // 다음 인덱스의 At 타입
  type After = NextIdxView#After        // 다음 인덱스의 After 타입
  def fold[R](f : (Before, At, After) => R): R = 
    next.fold( (before, at, after) =>   // 현재 인덱스의 fold가 다음 fold를 호출, 다음 fold는 다다음 fold를 호출, 다다음 fold는 다다다다..
      f(HCons(h, before), at, after))
}

// HList의 임의의 깊이에 대한 IndexedView 클래스를 구성해 봄 
// 첫째, 리스트를 취해 그 리스트의 N번째 인덱스 뷰에 대한 타입을 빌드
// 둘째, 마지막 타입을 아는 경우 IndexView 타입을 재귀적으로 구성

sealed trait HList {
  // ViewAt 타입 생성자
  // 현재 리스트의 주어진 인덱스에 IndexedView를 생성하는 타입, 인자로 Nat 타입을 취함
  type ViewAt[Idx <: Nat] <: IndexedView 
}

// Nat는 자연수를 의미하는 타입
sealed trait Nat {
  // Expand는 3개의 매개변수를 취함
  //  NonZero[N <: Nat] - 람다 타입, Nat가 _0이 아닐 경우 이전 자연수에 대해 적용됨
  //  IfZero - 자연수가 _0일 경우, 반환되는 타입
  //  Up - 상위 바운드, 처음 두 개의 타입의 타입 추론을 이슈를 피하기 위함
  type Expand[NonZero[N <: Nat] <: Up, IfZero <: Up, Up] <: Up 
}

object Nat {
  
  // _0는 모든 자연수의 시작점인 `영`을 의미  
  sealed trait _0 extends Nat {
    // 일종의 함수 호출, 2번째 파라미터를 반환 
    type Expand[NonZero[N <: Nat] <: Ret, IfZero <: Ret, Ret] = IfZero 
  }

  sealed trait Succ[Prev <: Nat] extends Nat {
    // 이전 Nat 타입에 대해 타입 생성자를 1번째 매개변수로 전달하는 일종의 함수 호출
    // NonZero의 타입 속성으로 사용되는 타입을 전달해서 재귀적으로 타입을 빌드하는 트릭.. 토나와..
    type Expand[NonZero[N <: Nat] <: Ret, IfZero <: Ret, Ret] = NonZero[Prev] 
  }
  
  type _1 = Succ[_0]
  type _2 = Succ[_1]
  type _3 = Succ[_2]
  type _4 = Succ[_3]
  type _5 = Succ[_4]
  type _6 = Succ[_5]
  type _7 = Succ[_6]
  type _8 = Succ[_7]
  type _9 = Succ[_8]
  type _10 = Succ[_9]
  type _11 = Succ[_10]
  type _12 = Succ[_11]
  type _13 = Succ[_12]
  type _14 = Succ[_13]
  type _15 = Succ[_14]
  type _16 = Succ[_15]
  type _17 = Succ[_16]
  type _18 = Succ[_17]
  type _19 = Succ[_18]
  type _20 = Succ[_19]
  type _21 = Succ[_20]
  type _22 = Succ[_21]
}


// 적용예
final case class HCons[H, T <: HList](head: H, tail: T) extends HList {
  ..
  // Expand의 첫 번째 타입 파라미터는 재귀 타입 파라미터임
  //    타입 생성자는 HListViewN[H, T#ViewAt[P]]로 정의되는데,
  //      현재 머리 타입을 구성하는 HListViewN 타입과 이전 자연수 N-1번째에 적용된 꼬리의 ViewAt 타입 => P
  // 종국에는 _0 타입에 대한 ViewAt이 호출되는데, Expand의 두 번째 타입 파라미터로 전달되어 HListView0[H,T]를 반환함. 
  
  type ViewAt[N <: Nat] = N#Expand[
    ({ type Z[P <: Nat] = HListViewN[H, T#ViewAt[P]] })#Z,
      HListView0[H,T], IndexedView]
}

// 두 개의 임플리시트 함수
// index0: HList를 취해 0번째 인덱스의 index view를 반환 
// indexN: HList와 리스트 꼬리의 암묵 변환를 취해 전체 리스트의 IndexView를 반환
// 
// 예) 
// Function1[Int :: Boolean :: Nil, HListViewN[Int, HListView0[Boolean, HNil]]] 에 대해 
// H = Int 와 T = Boolean :: HNil 와 Prev = ? 의 indexN 함수가 호출됨
// 컴파일러는 Function1[Boolean :: Nil, ? <: IndexedView]의 임플리시트를 찾고, 
// index0 임플리시트와 HListView0[Boolean, HNil]로 채워지는 Prev 타입으로 결정됨.
object IndexedView {
  implicit def index0[H, T <: HList](list : H :: T) : HListView0[H,T] = 
    new HListView0[H,T](list)
    
  implicit def indexN[H, T <: HList, Prev <: IndexedView](list: (H :: T))(implicit indexTail: T => Prev): HListViewN[H,Prev] = 
    new HListViewN[H, Prev](list.head, indexTail(list.tail))
}

// 전체 임플리시트 값을 발견하면, HList의 IndexedView 생성자를 이용할 수 있게 됨.
trait HCons[H, T <: HList] extends HList {
  
  type FullType = HCons[H,T]
  
  def viewAt[Idx <: Nat](implicit in: FullType => FullType#ViewAt[Idx]) =
    in(this.asInstanceOf[FullType])
  // ...
}

scala> val x = 5 :: "Hi" :: true :: HNil
// x: HCons[Int,HCons[java.lang.String,HCons[Boolean,HNil]]] = 5 :: Hi :: true :: HNil

scala> x.viewAt[Nat._1].get
// res3: java.lang.String = Hi

Generics of a Higher Kind - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.135.575&rep=rep1&type=pdf
Scala for Generic programmers - http://ropas.snu.ac.kr/~bruno/papers/ScalaGeneric.pdf
Type Constructor Polymorphism for Scala: Theory and Practice - https://lirias.kuleuven.be/bitstream/1979/2642/5/thesis_adriaan_moors_archive.pdf