PHpullh
학습 라이브러리/Kotlin/불변 데이터 구조 (Persistent Data)

KOTLIN · 함수형

불변 데이터 구조 (Persistent Data)

효율적인 불변 자료구조를 구현합니다. 구조 공유를 통해 수정 시 전체 복사를 피합니다.

함수형고급persistent-dataimmutable-liststructural-sharingfunctional

핵심 설명

효율적인 불변 자료구조를 구현합니다. 구조 공유를 통해 수정 시 전체 복사를 피합니다.

Kotlin code

// 불변 연결 리스트 (구조 공유)
sealed class PList<out T> {
    data object Nil : PList<Nothing>()
    data class Cons<T>(val head: T, val tail: PList<T>) : PList<T>()

    fun prepend(value: @UnsafeVariance T): PList<T> = Cons(value, this)

    fun <R> map(f: (T) -> R): PList<R> = when (this) {
        is Nil -> Nil
        is Cons -> Cons(f(head), tail.map(f))
    }

    fun toList(): List<T> = buildList {
        var current: PList<T> = this@PList
        while (current is Cons) {
            add(current.head)
            current = current.tail
        }
    }
}

fun <T> plistOf(vararg items: T): PList<T> =
    items.foldRight(PList.Nil as PList<T>) { item, acc -> PList.Cons(item, acc) }

fun main() {
    val list1 = plistOf(1, 2, 3)
    val list2 = list1.prepend(0)  // list1은 그대로

    println(list1.toList())  // [1, 2, 3]
    println(list2.toList())  // [0, 1, 2, 3]

    val doubled = list1.map { it * 2 }
    println(doubled.toList())  // [2, 4, 6]
}

학습 팁

불변 연결 리스트에서 prepend는 O(1)이지만 append는 O(n)입니다. 앞쪽 삽입이 빈번한 경우에 유리합니다.

주의할 점

깊은 재귀 순회 시 스택 오버플로가 발생할 수 있습니다. 대용량 데이터에는 tailrec이나 반복문으로 변환하세요.

자주 묻는 질문

불변 데이터 구조 (Persistent Data)란 무엇인가요?

효율적인 불변 자료구조를 구현합니다. 구조 공유를 통해 수정 시 전체 복사를 피합니다.

불변 데이터 구조 (Persistent Data) 학습 시 주의할 점은 무엇인가요?

깊은 재귀 순회 시 스택 오버플로가 발생할 수 있습니다. 대용량 데이터에는 tailrec 이나 반복문으로 변환하세요.