[Kotlin] 함수형으로 데이터 구조 만들기

주요 개념

- 함수형 개념을 사용하여 List를 구현

    - 순수 함수 (Pure function)

    - 꼬리 재귀 (Tail recursion)

    - 고차 함수 (High order function)

- 패턴 매칭 & 코틀린 매칭

- 이진트리를 직접 구현

 

아래의 코드는 단일 연결리스트의 구조 정의로, 비어있는 리스트와 값이 들어가 있는 리스트를 생성할 수 있는 형태이다. 값을 넣는 head와 리스트를 연결할 수 있는 tail 형태로 이루어져있다. 다형적으로 사용하기 위해서 A로 타입을 추상화 했다. 

sealed class List<out A>
object Nil: List<nothing>()
data class Cons<out A>(val head: A, val tail: List<A>): List<A>()

 

아래는 companion object를 통해서 Java의 정적 메소드와 같은 호출을 사용한다.

sealed class List<out A> {
	companion object {
    	fun <A> of(vararg aa: A): List<A> {
        	val tail = aa.sliceArray(a until aa.size)
            return if (aa.isEmpty()) Nil else Cons(aa[0], of(*tail))
        }
    }
}

>>> List.of(1,2)
res0: Cons(head=1, tail=Cons(head=2, tail=Nil))

 

위의  companion object에 아래의 두 함수를 추가해보자. 두 함수는 when을 사용한 매칭기법을 쓴다. 리스트를 탐색할 때는 역시 루프를 사용하지 않고, 함수적으로 해결하기 위해서 꼬리 재귀를 사용하도록 한다. type matching은 when을 사용하여 처리한다.

fun sum(ints: List<int>): Int = 
	when (ints) {
	    is Nil -> 0
        is Cons -> ints.head + sum(ints.tail)
    }

fun product(doubles: List<Double>): Double =
	when (doubles) {
    	is Nil -> 1
        is Cons -> 
        	if (doubles.head == 0.0) 0.0
            else doubles.head * product(doubles.tail)
    }

 

패턴 매칭은 Kotlin의 when에서 사용하는 매칭과 다르게 '값의 추출 및 구조 분해'가 가능하다. 이는 함수형에서 매우 중요한 기술이다. Kotlin에서는 언어의 복잡성 때문에 이를 도입하는 것에 대해 어려움이 있다. 아래의 코드에서 when으로 구현한 sum 함수와 패턴 매칭을 통해서 구현된 의사코드를 비교해보자. 당연히 의사 코드는 실행 방식만 표현할 뿐 빌드할 수 없다. when은 type에 대한 smart cast만 진행할 뿐 실제로 ints의 값을 추출하거나 분해할 수가 없다. 하지만 패턴 매칭을 사용할 경우에는 type에 대한 처리뿐만 아니라, 내부의 값을 추출 및 분해하여 직접 사용이 가능하다.

// when 사용
fun sum(ints: List<int>): Int = 
	when (ints) {
	    is Nil -> 0
        is Cons -> ints.head + sum(ints.tail)
    }
    
// 패턴 매칭 사용
fun sum(ints: List<int>): Int {
	case Nil -> 0
    case Cons(head, tail) -> head + sum(tail)
}

 

불변의 데이터를 사용하는 함수형에서 값을 바꾸기 위해서는 새로운 데이터를 생성하여 돌려주면 된다. 리스트에 새로운 데이터를 추가할 때는 기존의 모든 데이터를 새로운 리스트에 복사하여 사용하도록 한다. 값을 복사해서 쓰지 않게 되면 공유 자원이 생김으로써 함수형 매커니즘에서 벗어나게 된다.

 

고차 함수를 구현하여 원소에 대한 구체적 처리 대신에 일반화를 해보자. 타입에 따른 함수를 매개변수 f로 바인딩하여 처리는 보다 유연하고 확장적으로 할 수 있다. 

fun <A, B> foldRight(xs: List<A>, z: B, f: (A, B) -> B): B =
	when (xs) {
    	is Nil -> z
        is Cons -> f(xs.head, foldRight(xs.tail, z, f))
    }

 

위의 내용들을 바탕으로 함수적으로 동작하는 이진 트리를 직접 구현해보자!! 구조 정의는 아래와 같다.

sealed class Tree<out A>
data class Leaf<A>(val value: A): Tree<A>()
data class Branch<A>(val left: Tree<A>, val right: Tree<A>): Tree<A>()