리스트

리스트 연산에서 데이터 공유하기

불변성(Immutable)은 함수형 프로그래밍의 중요한 개념 중 하나다. 불변 데이터 구조를 사용할 때, 데이터를 수정하는 대신 새로운 데이터 구조를 반환하여 이전 데이터 구조를 변경하지 않는다. 그러나 불변성을 유지하는 것이 항상 성능을 저하시킬 수 있다는 걱정이 있다. 특히 리스트와 같은 데이터 구조에서는 원소를 추가하거나 수정할 때마다 데이터의 복사본을 만들어야 하기 때문에 성능에 영향을 미칠 수 있다.

하지만 데이터 공유라는 기법을 활용하면 성능 저하를 최소화하면서 불변성도 유지할 수 있다. 데이터 공유는 이전 데이터 구조의 일부를 그대로 사용하고, 변경된 부분만 새로운 객체로 생성하는 방식이다. 이를 통해 리스트의 연산에서 메모리와 성능을 최적화할 수 있다.

불변 리스트의 구조

불변 리스트는 기본적으로 연결 리스트(Linked List) 구조를 가진다. 연결 리스트에서 새로운 원소를 추가하거나 수정할 때마다 기존 리스트의 일부는 공유되고, 변경된 부분만 새로운 객체로 만들어진다. 이렇게 하면 불변성을 유지하면서도 리스트의 연산에서 성능을 향상시킬 수 있다.

예를 들어, 코틀린에서는 Nil과 Cons를 사용하여 불변 리스트를 구현할 수 있다. Nil은 빈 리스트를 나타내고, Cons는 첫 번째 요소와 나머지 리스트를 포함하는 노드다.

1. cons 함수 구현하기: 리스트의 맨 앞에 원소 추가하기

Cons 함수는 리스트의 맨 앞에 원소를 추가하는 함수다. 새로운 원소를 추가할 때마다, 원래 리스트의 일부는 그대로 공유하고, 첫 번째 원소만 새로운 원소로 바꾼다.

 

• List는 sealed class로 정의되어 있으며, Nil은 빈 리스트를 나타내고, Cons는 리스트의 첫 번째 요소(head)와 나머지 리스트(tail)를 포함하는 클래스다.
• prepend 함수는 element를 받아서 Cons 객체를 생성하고, 기존 리스트를 tail로 설정한다. 이 방식으로 리스트의 맨 앞에 원소를 추가할 수 있다.

 

sealed class List<out T> {
    object Nil : List<Nothing>() // 빈 리스트
    data class Cons<out T>(val head: T, val tail: List<T>) : List<T>() // 첫 번째 요소와 나머지 리스트
}

fun <T> List<T>.prepend(element: T): List<T> {
    return List.Cons(element, this)
}

2. setHead 함수 구현하기: 리스트의 첫 번째 원소 변경하기

setHead 함수는 리스트의 첫 번째 원소를 새로운 값으로 바꾸고, 나머지 리스트는 그대로 유지하는 함수다. 이를 통해 리스트의 첫 번째 요소만 변경된 새로운 리스트를 반환할 수 있다.

 

• 리스트가 Nil일 경우에는 변경할 첫 번째 요소가 없으므로 빈 리스트를 그대로 반환한다.
• 리스트가 Cons일 경우에는 newHead를 새로운 첫 번째 요소로 설정하고, tail을 그대로 복사하여 새로운 Cons 객체를 반환한다.

 

fun <T> List<T>.setHead(newHead: T): List<T> {
    return when (this) {
        is List.Nil -> List.Nil // 빈 리스트에서는 변경할 수 없음
        is List.Cons -> List.Cons(newHead, this.tail)
    }
}

3. drop함수 구현하기: 리스트의 맨 앞에서 n개의 원소를 제거하기

drop 함수는 리스트에서 첫 번째 n개의 원소를 제거한 것처럼 동작하지만, 실제로 원본 리스트에서 원소를 삭제하지 않고, 새로운 리스트를 반환하는 함수다. 이 함수는 불변 리스트에서 중요한 연산으로, 새로운 리스트를 생성하지만 기존 리스트는 그대로 유지되는 방식으로 작동한다.

drop 함수는 주어진 리스트에서 첫 번째 n개의 원소를 건너뛰고 나머지 원소들로 구성된 새로운 리스트를 반환한다. 실제로 리스트의 원소를 제거하지는 않지만, 결과적으로 제거된 것과 같은 결과를 얻을 수 있다.

우리는 List를 Nil과 Cons로 구성한 불변 리스트로 가정하고, 첫 번째 n개의 원소를 건너뛰는 방식으로 drop 함수를 구현할 수 있다. drop 함수는 리스트를 순차적으로 순회하면서 n번 만큼 첫 번째 원소를 건너뛰고 나머지 원소들로 구성된 새로운 리스트를 반환한다.

sealed class List<out T> {
    object Nil : List<Nothing>() // 빈 리스트
    data class Cons<out T>(val head: T, val tail: List<T>) : List<T>() // 첫 번째 요소와 나머지 리스트
}

// drop 함수: 첫 번째 n개의 원소를 건너뛰고 새로운 리스트 반환
fun <T> List<T>.drop(n: Int): List<T> {
    return when {
        n <= 0 -> this // n이 0 이하이면 원본 리스트 그대로 반환
        this is List.Nil -> this // 빈 리스트에서는 아무것도 반환할 수 없음
        this is List.Cons -> this.tail.drop(n - 1) // 첫 번째 원소를 건너뛰고 tail에 대해 drop 실행
    }
}