불변 컬렉션/Immutable Collections (Kotlin 함수형 프로그래밍 #5)

불변 컬렉션

앞에서 보았듯이 함수형 프로그래밍에서는 항상 불변값과 대수적 타입으로 값을 다룬다. 이는 컬렉션의 경우에도 마찬가지이다. 리스트의 가장 기본적인 구현을 보면 아래와 같다.

// sealed 키워드를 통해 패키지 안에서만 상속 가능하도록
sealed class List<out A>

// Empty를 표현
object Nil : List<Nothing>()

// 비어 있지 않는 리스트
data class Cons<out A>(val head: A, val tail: List<A>) : List<A>()

 

데이터 공유

불변 리스트 xs에 1이라는 원소를 추가한다면 Cons(1, xs) 새로운 리스트를 반환하면 된다. 삭제를 한다면 tail을 반환하면 됨. 이를 데이터 공유라고 한다. 데이터 변경이나 오염을 피하기 위해서 복사본을 만들 필요가 없다. 데이터 구조가 불변이기 때문에 복사본은 불필요하다.

함수형 데이터 구조는 영속적(Persistent)이다. 영속적이라는 말은 존재하는 참조가 데이터 구조에 대한 연산을 수행한 다음에도 바뀌지 않고 원래대로 남는다는 것이다.

데이터 공유의 효율

두 리스트를 연결하는 연산을 생각해보자. 실행 시간과 사용량은 a1의 길이에 의해서만 결정된다. 배열로 구현한다면 두 배열의 모든 원소를 배열에 복사해야 한다. 불변 리스트가 훨씬 유리하다.

fun <A> append(a1: List<A>, a2: List<A>): List<A> =
    when (a1) {
        is Nil -> a2
        is Cons -> Cons(a1.head, append(a1.tail, a2))
    }

 

 

코틀린 표준 라이브러리의 리스트

 

사실 불변 리스트가 아닌 읽기 전용 리스트이다. 내부적으로 ArrayList를 사용하며, 변경/삭제 연산을 제공하지 않는 것일 뿐이다.

 

Arrow Collections

애로우에서는 불변 리스트를 다루기 위한 다양한 타입 및 도구들을 제공한다.

Non-Empty Collections

nullable 타입은 값이 null일 수 있다는 것을 표현할 수 있다. 하지만 어떤  시나리오에서는 반드시 하나의 엘리먼트가 존재해야 한다는 경우도 있을 수 있다. 이를 위해 애로우는 NonEmptyList와 NoEmptySet을 제공한다. 예를 들어 에러를 집계할때 타입은 Either<List<Problem>, Result>로 일반적으로 표현할텐데 , Left에 Empty리스트가 있다면 비정상적인 상황이라고 할 수 있다. 이럴 경우 Either<NonEmptyList<Problem>,Result>와 같은 타입으로 대체할 수 있다.

 

Collectors

일반적으로 리스트의 평균을 계산하는 연산을 살펴보자

val average = list.sum() / list.size​

 

문제는 리스트를 두 번 탐색한다는 것이다. 컬렉터는 집계연산에 대한 description과 실제 연산을 분리한다.

import arrow.collectors.Collectors
import arrow.collectors.collect
import arrow.collectors.zip

fun divide(x: Int, y: Int): Double = x.toDouble() / y.toDouble()

val averageCollector = zip(Collectors.sum, Collectors.length, ::divide)
val average = list.collect(averageCollector)

 

Recursive functions

함수형에서는 알고리즘 루프보다는 재귀를 사용한다. 하지만 재귀를 사용하다보면 스택오버플로우을 종종 만나게 된다. 

Stack-safe deep recursive functions

코틀린은 빌트인으로 DeepRecursiveFunction을 제공한다. 이럴경우 콜스택을 유지하기 위해 평소보다 훨씬 큰 메모리를 힙에 유지한다.

fun fibonacciWorker(n: Int): Int = when (n) {
   0 -> 0
   1 -> 1
   else -> fibonacciWorker(n - 1) + fibonacciWorker(n - 2)
}

fun fibonacci(n: Int): Int {
   require(n >= 0)
   return fibonacciWorker(n)
}

fun example() {
   fibonacci(6) shouldBe 8
}

 

스택 세이프하게 변경하면 다음과 같다.

val fibonacciWorker = DeepRecursiveFunction<Int, Int> { n ->
   when (n) {
      0 -> 0
      1 -> 1
      else -> callRecursive(n - 1) + callRecursive(n - 2)
   }
}

Memoized recursive functions

위 피보나치의 개선사항은 같은 연산을 메모이제이션을 할 수 있다는 것이다. 순수 함수는 항상 입력에 대한 출력이 같으므로 메모이제이션에 유리하다.애로우에서는 해당 해법으로 MemoizedDeepRecursiveFunction을 제공한다.

import arrow.core.MemoizedDeepRecursiveFunction

val fibonacciWorker = MemoizedDeepRecursiveFunction<Int, Int> { n ->
   when (n) {
      0 -> 0
      1 -> 1
      else -> callRecursive(n - 1) + callRecursive(n - 2)
   }
}

Memoization takes memory

캐쉬를 적용할 수도 있다. Eviction 정책은 각 캐시 정책 지정할수도 있다.

import arrow.core.MemoizedDeepRecursiveFunction
import arrow.core.Cache4kMemoizationCache
import arrow.core.buildCache4K

val cache = buildCache4K<Int, Int> { maximumCacheSize(100) }

val fibonacciWorker = MemoizedDeepRecursiveFunction<Int, Int>(
   Cache4kMemoizationCache(cache)
) { n ->
   when (n) {
      0 -> 0
      1 -> 1
      else -> callRecursive(n - 1) + callRecursive(n - 2)
   }
}

 

정리

• 불변 데이터 구조를 이용해 데이터를 공유하면 데이터 구조의 내용을 방어적으로 복사히지 않아도 데이터를 안전하게 처리할 수 있다.
• 불변 리스트의 연산은 루프보다 재귀가 많다. 재귀를 위한 다양한 도구를 애로우에서 제공한다.

참조 : https://www.yes24.com/Product/Goods/120236288?pid=123487&cosemkid=go16903580741098008&utm_source=google_pc&utm_medium=cpc&utm_campaign=book_pc&utm_content=ys_240530_google_pc_cc_book_pc_12306%EB%8F%84%EC%84%9C&utm_term=%EC%BD%94%ED%8B%80%EB%A6%B0%ED%95%A8%EC%88%98%ED%98%95%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D&gad_source=1&gclid=CjwKCAiAm-67BhBlEiwAEVftNp4rJHRMrNaBE2YyQCT-r4Gxu_X9K6NdakIvehx_Mxsi48Jj3rZ45BoCbUsQAvD_BwE

코틀린 함수형 프로그래밍 - 예스24

https://arrow-kt.io/

Arrow