함수형 프로그래밍 3편 - 불변성과 구조 공유, 퍼시스턴트 자료구조

함수형 프로그래밍은 상태를 바꾸지 않는다. 그렇다면 어떻게 변경을 반영할 수 있을까?

---

1. 불변성(Immutable)이란?

✅ 정의

한 번 만들어진 값은 절대 바뀌지 않는 성질

불변 객체는 생성 후 내부 상태가 변경되지 않는다. 값을 바꾸고 싶을 경우 기존 값을 복사한 새로운 객체를 생성한다.

val list1 = listOf(1, 2, 3)
val list2 = list1 + 4  // list1은 여전히 [1, 2, 3]

2. 왜 불변성이 중요한가?

📌 함수형의 핵심 전제 조건

• 순수 함수 → 외부 상태 변경 금지 → 불변성 요구
• 참조 투명성 보장 → 중간 상태가 변하지 않음

📌 동시성/병렬성에서의 안전성 확보

• 여러 스레드가 동시에 데이터를 읽어도 안전 (변하지 않음)
• Lock 없이도 병렬 처리가 가능함

3. 값이 바뀌어야 할 때는 어떻게 하나?

불변성은 변화 자체를 금지하는 것이 아니라, 변화가 "새 값"으로 나타나도록 요구하는 것이다.
즉, 원본 데이터를 직접 수정하는 대신, 변경사항이 반영된 새로운 데이터를 생성하는 방식이다,

예: 리스트에 요소 추가

val list1 = listOf(1, 2, 3)
val list2 = list1 + 4 // list1은 그대로, list2는 [1, 2, 3, 4]

📌 핵심은 "공유"

• 기존 리스트의 요소를 복사하지 않고 공유하고,
• 변경된 부분만 새롭게 생성한다 → 이를 구조적 공유(Structural Sharing) 라 한다.
• 각 list1, list2는 불변(읽기 전용)이기에 공유하는 값이 변경되는 문제는 걱정할 필요없다.

4. 구조적 공유(Structural Sharing)의 원리

✅ 개념 요약

"전체를 복사하지 않고, 바뀐 경로만 새로 만들고 나머지는 기존 데이터를 참조"

구조 공유는 크게 세 가지 방식으로 구현된다:

• Cons List: 앞쪽만 추가되며 나머지는 공유
• Path Copying: 트리 구조에서 바뀌는 경로만 복사하고 나머지 노드는 그대로
• Fat Node: 노드 안에 버전 기록을 유지 (버전 기반 공유)

이러한 방식은 모두 불변성과 성능을 동시에 확보하기 위한 전략이다

이 방식을 통해 불변성과 성능을 동시에 확보할 수 있다.

예: 연결 리스트 (Cons List)

list1 = [1] -> [2] -> [3]
list2 = [0] -> (list1)

• list2는 맨 앞 노드만 새로 만들고, list1을 그대로 참조
• list1과 list2는 중복 없이 메모리 공유 가능

5. 퍼시스턴트 자료구조(Persistent Data Structures)

✅ 시간/공간 복잡도 이점

• 구조 공유 없이 전체 복사 → O(n) 메모리, 시간 낭비
• 구조 공유 적용 → O(log n) 시간에 변경 가능 (트리 구조일 때)

v1 = [A][B][C]
v2 = [A][B][D] ← 변경된 블록만 새로 생성, A와 B는 공유

➡️ 성능상 큰 이점: 이전 상태 보존 + 메모리 절약

✅ 정의

이전 버전의 상태를 보존하면서 새로운 상태를 생성할 수 있는 자료구조

📌 특징

• 모든 수정 연산은 새로운 구조를 반환하며, 원본은 그대로 유지
• 복사 비용 없이 변경된 경로만 새로운 노드로 교체 (구조 공유)

실전 예: Clojure의 Persistent Vector

• 내부적으로는 트라이(Trie) 구조 활용
• 32진 트리 구조로 O(log₃₂ n) 시간 복잡도로 접근/수정 가능
• 이전 버전 공유를 통해 불변성 유지 + 메모리 효율 확보

(def v1 [1 2 3])
(def v2 (conj v1 4))  ;; v1 = [1 2 3], v2 = [1 2 3 4]

6. Kotlin에서의 불변성은?

✅ val과 immutable은 다르다

• val은 참조가 바뀌지 않는다는 의미지, 객체 내부가 바뀌지 않는다는 뜻은 아니다
• 예: 아래의 val 리스트는 내부 요소가 바뀔 수 있다

val mutableList = mutableListOf(1, 2, 3)
mutableList.add(4) // 내부 상태 변경 가능

Kotlin에서 구조 공유 구현은?

Kotlin 표준 컬렉션은 구조 공유 기반이 아니므로, 불변성과 성능을 함께 확보하려면 직접 구현하거나 외부 라이브러리를 고려해야 한다.

• 대표 라이브러리: Arrow, Persistent Collections for Kotlin

// kotlinx.collections.immutable 사용 예시
val v1 = persistentListOf(1, 2, 3)
val v2 = v1.add(4)  // v1은 그대로 유지됨

→ 실무에선 구조 공유 라이브러리 활용이 현실적 대안이 될 수 있다.

---

Kotlin 컬렉션의 오해

• listOf()는 읽기 전용(read-only)이지 진짜 불변(immutable)은 아니다
• 구조 공유 기반 컬렉션은 기본 제공되지 않음 (직접 구현하거나 외부 라이브러리 필요)

📌 참조 불변성과 진짜 불변성의 차이를 명확히 인식해야 한다

Kotlin 컬렉션

• val은 참조 불변일 뿐, 컬렉션 자체는 가변일 수 있음
• listOf() → 읽기 전용 List (진짜 불변은 아님)
• 구조 공유 기반 컬렉션은 기본 제공되지 않음 (하지만 구현 가능)

진짜 불변 구조 예시

data class Node(val value: Int, val next: Node?)

val list1 = Node(1, Node(2, Node(3, null)))
val list2 = Node(0, list1) // 앞에 하나 추가 (list1 불변 유지)

🔚 마무리 요약

개념	설명
불변성	값은 변경 불가, 변경 시 새 객체 생성
구조 공유	변경된 경로만 새로 생성하고 나머지는 기존 구조 참조
퍼시스턴트 자료구조	이전 상태를 보존하며 새로운 상태를 생성, 구조 공유로 구현됨
Kotlin에서의 불변 컬렉션	listOf()는 읽기 전용일 뿐 완전 불변은 아님. data class 기반 구현으로 가능

구조 공유는 시간/공간 복잡도 최적화의 핵심 전략이다.
단순히 '복사해서 새로 만든다'가 아니라 필요한 부분만 효율적으로 바꾸며 공유하는 설계가 불변성 구현의 열쇠다.