3. 함수형 데이터 구조 - Functional Programming in Kotlin

함수형 프로그래밍에서는 변수를 갱신하거나 가변 데이터 구조를 변경하지 않는다고 얘기했다.

그러면 어떤 유형의 데이터 구조를 사용해야할까?

3.1  함수형 데이터 구조 정의하기

함수형 데이터 구조는 순수함수만으로 조작된다. 순수함수는 제자리에서 데이터를 변경하거나 부수 효과를 만들어내면 안된다.

불변이어야한다. 빈 리스트는 영원히 비어있고 변하면 안된다. 
리스트 두 개를 이어붙이면 원래 리스트 2개는 그대로 있고 새로운 리스트가 생겨야한다.

변경을 못한다면 데이터 복사를 더 많이 해야한다는 것일까? "아니다."

함수형 데이터 구조의 예시로 단일 연결 리스트를 보자. 

sealed class List<out A>

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

sealed 클래스로 List를 만들고 빈리스트를 의미하는 Nil과 데이터를 담고있는 Cons를 정의했다. 

Cons는 첫 번째 원소 head와 나머지 원소 리스트인 tail로 이뤄진다. 

List에 타입 파라미터로 <out A>를 사용해 다형적인 데이터 타입을 만들었다.
out은 타입 파라미터가 공변적이라는 것이다.  X가 Y의 자식 클래스라면 List<X>도 List<Y>의 하위타입이라는 것이다. 

https://yoonda.tistory.com/22

[Kotlin] Generics 공변성, 반공변성(out, in)

 

val nil: List<Double> = Nil
val a1: List<Int> = Cons(1, Nil)
val a2: List<String> = Cons("a", Cons("b", Nil))

이런식으로 데이터를 만들 수 있다.

Nil은 List<Nothing> 타입이다. Nothing은 모든 타입의 하위타입이므로, 어떤 타음의 리스트로도 캐스팅 될 수 있다. 

이제 이 함수형 데이터 타입을 이용하면, Nil일 때와 Cons 일 때를 구분해서 동작을 하게 할 수 있다. 이를 위해 사용되는 패턴 매칭에 대해 알아보자. 

3.2 함수형 데이터 구조 다루기

List를 쉽게 생성할 수 있는 of 함수를 만들자.

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

val list = List.of(1, 2, 3, 4, 5, 6)

가변인자와 Spread 연산자를 이용해서 of함수를 정의하였다. 
List라는 자료구조 자체가 tail로 List 형을 갖고있는 재귀적인 타입이므로, 생성하는 연산도 재귀함수로 작성하였다. 
재귀적인 자료구조에 대한 연산은 재귀적으로 작성하는 것이 일반적이다. 

코틀린에서는 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 -> 0.0
        is Cons -> doubles.head + product(doubles.tail)
    }

이런 식으로 원소들의 합과 곱을 계산하는 함수를 정의할 수 있다. 

3.3 함수형 데이터 구조 안의 데이터 공유

함수형 데이터 타입은 데이터가 불변이다. 바꿀 수 없다면, 리스트에 원소를 추가하거나 삭제는 어떻게 해야할까?

기존 리스트 xs가 있다면 Cons(1, xs) 처럼 앞에 붙이거나 xs.tail을 해서 첫 번째 요소를 제외한 리스트를 반환할 수 도 있다. 

불변이기 때문에 참조가 같아도 된다. 다른 곳에서 변경될 일이 없기 때문이다. 

두 리스트를 이어붙이는 함수를 보자.

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))
    }

a1의 마지막 포인터를 바꿀 수 없기 때문에 a1의 원소들을 다 복사해야한다. a1을 다 복사하고 나면 a2로 참조만 하면 되므로 시간복잡도는 a1의 길이에 따라 결정된다. 

연습문제 3.1

List의 첫 번째 원소를 제거하는 tail함수 구현. 상수 시간에 끝나야 함.

fun <A> tail(xs: List<A>): List<A> =
    when (xs) {
        is Nil -> Nil
        is Cons -> xs.tail
    }

연습문제 3.2

리스트의 첫 원소를 다른 값으로 대치

fun <A> setHead(xs: List<A>, x: A): List<A> =
    when (xs) {
        is Nil -> Nil
        is Cons -> Cons(x, xs.tail)
    }

연습문제 3.3

tail을 일반화한 drop을 작성하라. 리스트의 앞에서부터 n개의 원소를 제거한다. 

fun <A> drop(l: List<A>, n: Int): List<A> =
    if (n == 0) l else drop(tail(l), n - 1)

연습문제 3.4

dropWhile을 구현하라. List의 맨 앞부터 주어진 술어를 만족하는 연속적인 원소를 삭제한다. 

fun <A> dropWhile(l: List<A>, f: (A) -> Boolean): List<A> =
    when (l) {
        is Nil -> Nil
        is Cons -> {
            if (f(l.head)) {
                dropWhile(l.tail, f)
            } else {
                l
            }
        }
    }

연습문제 3.5

마지막 원소를 제외한 리스트를 반환하는 init함수를 정의하라.

fun <A> init(l: List<A>): List<A> = 
    when (l) {
        is Nil -> Nil
        is Cons -> {
            if (l.tail is Nil) {
                Nil
            } else {
                Cons(l.head, init(l.tail))
            }
        }
    }

3.4 고차함수로 일반화

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 -> 0.0
        is Cons -> doubles.head + product(doubles.tail)
    }

앞에서 본 sum과 product는 거의 차이가 없다.

이 함수들을 고차함수로 일반화 해보자.

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))
    }

fun sum2(ints: List<Int>): Int =
    foldRight(ints, 0) { a, b -> a + b }

fun product2(dbs: List<Double>): Double =
    foldRight(dbs, 1.0) { a, b -> a * b }

foldRight라는 값을 누적해서 계산하는 함수를 일반화하였다.

Nil이면 z라는 Cons는 f로 치환해 치환모델을 적용할 수도 있다. 

Cons(1, Cons(2, Nil)) -> f(1, f(2, z))

foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0, { x, y -> x + y })
-> 1 + foldRight(Cons(2, Cons(3, Nil)), 0, {x, y -> x + y })
-> 1 + 2 + foldRight(Cons(3, Nil), 0, {x, y -> x + y})
-> 1 + 2 + 3 + foldRight(Nil, 0, {x, y -> x + y})
-> 1 + 2 + 3 +0

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

코틀린의 기본 라이브러리 List는 read only인 List와 읽기 쓰기가 가능한 MutableList가 존재한다. 
하지만 내부적으로는 모두 가변 리스트(java의 ArrayList)를 사용한다. 

이로 인해 순수함수가 읽기 전용 List 를 다뤄도 데이터 오염이 발생할 수 있다. 

3.5 트리

앞에서 살펴본 함수형 데이터 타입인 List는 ADT(Algebraic Data Type; 대수적 데이터 타입)에 속한다.

ADT는 하나 이상의 데이터 생성자로 정의된 데이터 타입을 뜻한다.

Algebraic Data Type 이란?

ADT는 다른 자료형의 값을 가지는 자료형이다. 

예를 들어 아래와 같은 데이터 클래스가 있다. 

data class Person(val name: String, val age: Int, val email: String)

String, Int 자료형의 값을 가지는 Person 자료형이다. 

그리고 kotlin 의 enum과 sealed class 도 ADT라고 할 수 있다.

enum class Job {
    DOCTOR, OFFICER, DEVELOPER
}

sealed class Programmer {
    data class MobileProgrammer(val language: String): Programmer()
    data class ServerProgrammer(val language: String): Programmer()
}

enum과 sealed 클래스는
Job = DOCTOR or OFFICER or DEVELOPER,
Programmer = MobileProgrammer or ServerProgrammer 와 같이 or로 표시할 수 있다.

이런 타입을 합타입이라고 한다.

Person의 경우 name, age, email 등의 값이 정해져 있는 게 아니다. 
name: String 의 개수 * age: Int의 개수 * email: String의 개수 로 표현된다. 

이런 타입을 곱타입이라고 한다.

 

앞에서 정의한 List와 아래 Tree 등이 ADT에 속한다.

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>()

 

 

대수적 데이터 타입이(algebraic data type)이란? With Kotlin