코틀린으로 배우는 함수형 프로그래밍을 보고 정리하는 내용입니다.
코틀린의 콜렉션(collection)들은 여러 고차 함수를 제공하는데, 이러한 고차 함수들을 콤비네이터(combinator)라고 부르고 컬렉션의 데이터를 여러 가지 형태로 조작하는데 사용된다.
여러 콤비네이터 소개하고 또 직접 작성해보는 시간을 가져보려고 한다.
리스트 자료구조 만들기
함수형 언어에서 리스트는 Constructor 라고 하며 줄여서 Cons라고 불리는 구성 요소를 갖는다. 이때 각 Cons의 tail은 다른 하나의 Cons의 head를 가르키는 링크드 리스트 형태를 띄는데, 마지막 Cons의 tail은 값이 없는 상태인 Nil을 가르킨다.
FunList 만들기
이를 코틀린으로 작성하면 다음과 같다.
sealed class FunList<out T> {
object Nil: FunList<Nothing>()
data class Cons<out T>(val head: T, val tail: FunList<T>): FunList<T>()
}Nil일 때 FunList는 아무것도 가지지 않은 Nothing 객체를 포함하고 Cons일 때는 T타입의 값 head와 또 다른 FunList인 tail 값을 가진다.
순수 함수형 언어의 리스트는 기본적으로 lazy evaluation이 되나 코틀린의 리스트나 FunList는 lazy evaluation을 하지 않는다.
FunList를 사용해 값 1,2를 가진 리스트를 생성해보면 다음과 같다.
val list: FunList<T> = Cons(1, Cons(2,Nil))addHead
fun <T> FunList<T>.addHead(head: T): FunList<T> = FunList.Cons(head,this)FunList 클래스의 extension function(본 글에서는 이제 확장 함수라고 하겠다.)으로 addHead를 추가했다.
콤비네이터의 체이닝 형태로 컬렉션의 데이터를 조작하기 위해 확장 함수를 사용했다.
리스트의 맨 압에 head를 추가하면 head에 인자로 들어간 값이 새로운 리스트의 head가 되고 원본 리스트를 tail로 지정해주기만 하면 된다. 시간복잡도 O(1)에 새로운 리스트를 head에 추가할 수 있는 함수를 만들었다.
함수형 컬렉션에서 제공하는 함수들은 불변성을 지키고 부수효과를 최소화 하기 위해 원본 데이터를 변경하지 않고 가공된 데이터를 매번 새로 만들어 반환하는 특성을 가진다.
매번 데이터를 새로 만들기 때문에 생성 비용을 최소화하기 위해서 lazy evaluation(이제부터 게으른 평가라고 하겠다.)와 내부 캐싱을 사용한다.
addHead는 tail에 원본 리스트를 재사용하면서 새로운 Cons만 추가로 연결함으로 내부 캐싱을 사용했다고 할 수 있다.
appendTail 함수 만들기
fun <T> funList<T>.appendTail(value: T): FunList<T> = when(this) {
FunList.Nil -> Cons(value, Nil)
is FunList.Cons -> Cons(head, tail.appendTail(value))
}FunList가 Cons인 경우는 head 값은 Cons의 첫번째 매개변수로 넣어 유지하고 tail 값은 tail.appendTail(value)로 재귀 호출한 결과를 넣는다.
FunList가 Nil일 때는 Cons(value, Nil)을 반환해 head에는 value, tail에는 Nil을 넣고 재귀를 종료한다.
위 함수는 꼬리 재귀가 아니라 스택에 안전하지 않아 아래처럼 재작성했다.
tailrec fun <T> FunList<T>.appendTail(value: T, acc: FunList<T> = Nil): FunList<T> = when (this) {
FunList.Nil -> Cons(value, acc).reverse()
is FunList.Cons -> tail.appendTail(value, acc.addHead(head))
}acc.addHead(head) 함수 호출을 통해 acc에 원본 리스트의 값을 반대의 순서로 넣는다.
FunList.Nil을 만나는 시점에 처음 입력받은 value를 head에 넣고 반대 순서로 연결시킨 acc을 tail로 넣고 reverse 함수를 호출시킨다.
아래는 reverse 함수다. 이름에서 느껴지지만 리스트의 방향을 거꾸로 바꾸는 함수이다.
tailrec fun <T> FunList<T>.reverse(acc: FunList<T> = FunList.Nil): FunList<T> = when(this) {
FunList.Nil -> acc
is FunList.Cons -> tail.reverse(acc.addHead(this))
}꼬리 재귀로 작성한 appendTail 함수는 스택도 안전하고 O(n)이기 때문에 성능상에도 문제가 없다.
getTail 함수 만들기
fun <T> FunList<T>.getTail(): FunList<T> = when (this) {
FunList.Nil -> throw NoSuchElementException()
is FunList.Cons -> tail
}리스트가 비어 있을 때는 가져올 꼬리 리스트가 없으므로 예외를 발생 시키고, 리스트가 비어있지 않을 때는 tail을 그대로 반환하도록 했다.
컬렉션 데이터 걸러 내기
명령형 방식 vs 함수형 방식
리스트에서 짝수만 걸러내는 함수를 명령형 방식으로 작성했다.
fun imperativeFilter(numList: List<Int>): List<Int> {
val newList = mutableListOf<Int>()
for (num in NumList) {
if (num % 2 == 0) {
newList.add(num)
}
}
}아래는 함수형 방식이다.
fun functionalFilter(numList: List<Int>): List<Int> = numList.filter { it % 2 == 0 }함수형 방식은 다음과 같은 장점이 있다.
- 코드가 간결하다
- 결과값을 저장하기 위해 별도의 리스트를 생성할 필요가 없다
- 비즈니스 로직에 집중할 수 있다. (how가 아니라 what)
- 버그가 발생할 확률이 적다 (sideEffect 최소화)
- 테스트가 용이하다.
- 유지보수가 용이하다
filter 함수 만들기
tailrec fun <T> FunList<T>.filter(acc: FunList<T> = FunList.Nil, p: (T) -> Boolean): FunList<T> = when (this) {
FunList.Nil -> acc.reverse()
is FunList.Cons -> if (p(head)) {
tail.filter(acc.addHead(head),p)
} else {
tail.filter(acc, p)
}
}이제 쬐끔은 눈에 익을 수도 있을 것 같은데,
먼저 함수 체이닝이 가능할 수 있또록 확장 함수로 작성하고 p(head)가 참일 경우에는 새로운 FunList인 acc에 head를 추가하여 생성하고 나머지 tail에 대해서는 filter를 호출하여 재귀 호출한다. 리스트를 모두 순회했다면 조건 p에 맞는 리스트들만 모인 acc을 reverse하여 반환한다.
컬렉션 데이터 변경하기
명령형 프로그래밍에서는 변경 가능한 컬렉션일 경우 setter 함수를 호출하여 해당 인덱스의 값을 변경한다. 컬렉션 내의 모든 값에 특정 함수를 적용할 때는 for, while등을 사용한다.
fun imperativeMap(numList: List<Int>): List<Int> {
val newList = mutableListOf<Int>()
for (num in numList) {
newList.add(num + 2)
}
return newList
}아래는 함수형 방식으로 재작성한 것이다. 새로운 리스트를 만들어서 반환하기 때문에 부수효과가 없다.
fun functionalMap(numList: List<Int>): List<Int> {
return numList.map { it + 2 }
}map 함수 만들기
map 함수를 본격적으로 만들어보기 전에 FunList의 value에 3을 더하거나 곱하는 함수를 만들어보려고 한다.
fun add3(list: FunList<Int>): FunList<Int> = when (list) {
FunList.Nil -> Nil
is FunList.Cons -> FunList.Cons(list.head + 3, add3(list.tail))
}
fun product3(list: FunList<Double>): FunList<Double> = when (list) {
FunList.Nil -> Nil
is FunList.Cons -> FunList.Cons(list.head *3, product3(list.tail))
}두 함수의 차이는 리스트에 포함된 값들에 어떤 연산을 하는지와 FunList의 타입이다.
타입은 제너릭으로, 연산은 함수로 각각 매개변수를 받는다면 일반적인 함수를 만들 수 있을 것 같다.
tailrec fun <T, R> FunList<T>.map(acc: FunList<R> = FunList.Nil, f: (T) -> R): Funlist<R> = when (this) {
FunList.Nil -> acc.reverse()
is FunList.Cons -> tail.map(acc.addHead(f(head)), f)
}꼬리 재귀를 통해 기존 함수보다 스택 안정성을 확보했고, 연산에 따라 원본 리스트의 타입과 반환 타입이 변경될 수 있기에 원본 리스트 값과 반환 리스트 값의 타입을 제너릭으로 받았습니다.
마지막으로 연산도 매개변수로 받아 연산 로직과의 의존성을 분리했습니다.
fun main() {
val intList = funListOf(1,2,3)
val doubleList = funListOf(1.0, 2.0, 3.0)
printFunList(intList.map { it + 2 })
printFunList(doubleList.map { it * 3})
}
fun <T> funListOf(vararg elements: T): FunList<T> = elements.toFunList()
private fun <T> Array<out T>.toFunList(): FunList<T> = when {
this.isEmpty() -> FunList.Nil
else -> FunList.Cons(this[0], this.copyOfRange(1, this.size).toFunList())
}컬렉션 데이터 단계별로 줄이기
리스트를 다루는 함수를 구현하는데 재귀를 주로 사용하고 있는데, 일반적으로 종료조건을 빈 리스트로 하고 리스트이 첫번째 값인 head와 나머지 값들이 리스트 tail으로 나누어 처리했다.
재귀를 순회할 때마다 컬렉션을 종료조건으로 수렴시키는 작업을 폴드 함수로 대신할 수 있는데 폴드 함수는 매핑 함수의 일종으로 컬렉션을 단일 값으로 줄여준다.
다음은 FunList에 포함된 모든 값을 더해주는 sum 함수이다.
fun sum(list: FunList<Int>): Int = when (list) {
FunList.Nil -> 0
is FunList.Cons -> list.head + sum(list.tail)
}foldLeft 함수 만들기
앞서 본 함수와 같이 하나의 값으로 줄이는 작업을 일반화하여 만든 고차 함수가 폴드 함수이다.
함수 sum 처럼 컬렉션의 값들을 왼쪽에서부터 오른쪽으로 줄여 나가는 함수를 foldLeft라고 한다.
tailrec fun <T,R> FunList<T>.foldLeft(acc: R, f: (R, T) -> R): R = when(this) {
FunList.Nil -> acc
is FunList.Cons -> tail.foldLeft(f(acc,head), f)
}작성한 foldLeft함수를 사용해 sum 함수를 재작성해보자
fun main() {
val intList = funListOf(1, 2, 3)
println(sumByFoldLeft(intList)) // 6
}
fun sumByFoldLeft(list: FunList<Int>): Int = list.foldLeft(0) { acc, x -> acc + x }