[Kotlin] 함수형 프로그래밍 시작하기

주요 개념

- 꼬리 재귀 함수를 이용한 루프 작성

- 고차 함수 (High-order function)

- 타입 추상화

 

순수함수 만을 사용하여 프로그래밍을 하는 것이 함수형 프로그래밍의 기본이다. 그럼 순수함수만 이용해서 루프를 구현하라고 하면 대부분의 사람들은 어려워할 것이다. 이를 위해서 우리는 꼬리 재귀 함수를 사용한다. 아래와 같이 피보나치 함수를 꼬리재귀를 이용해서 짜보자. 피보나치 말고도 구구단 출력이나 기타 수열 문제들을 꼬리 재귀를 통해서 해결해보도록 한다. 재귀함수는 오로지 매개변수만을 참조하여 처리하도록 구현한다. 즉, 순수함수를 이용한 재귀 호출로 루프를 구현하는 것이다.

fun factorial(i: Int): Int {
	fun go(n: Int, acc: Int): Int =
    	if (n <= 0) acc
        else go(n - 1, n * acc)
    return go(i, 1)
}

 

꼬리 위치에서 재귀 함수를 호출하여 이를 꼬리 재귀라고 부른다. 그런데 이처럼 재귀 호출을 사용하면 한가지 걱정이 들게 된다. Stack overflow이다. 재귀로 함수를 반복적으로 호출하면 매번 호출할 때마다 Stack을 할당하게 되고 이는 Stack oveflow로 이어진다. 이를 해결하기 위한 방안으로 TCO (Tail Call Obtimization)이라는 방식으로 코틀린 컴파일러는 최적화를 지원한다. 'tailrec'라는 키워드를 재귀 호출 대상이 되는 함수에 선언해주면, 코틀린 컴파일러는 Stack을 새로 할당하지 않고 루프로 이를 처리하게 된다.

fun factorial(i: Int): Int {
	tailrec fun go(n: Int, acc: Int): Int =
    	if (n <= 0) acc
        else go(n - 1, n * acc)
    return go(i, 1)
}

 

고차 함수는 함수를 매개변수로 받을 수 있고, 반환값으로 돌려줄 수 있는 한수를 말한다. 함수를 모듈 단위로 치환해서 사용 하는 것이 함수형 프로그래밍의 시작이라고 앞서 말한 바가 있다. 꼬리 재귀를 통해서 루프를 순수함수로 대체했다면, 이번에는 순수함수를 통해서 매개변수를 대체한다.  아래의 코드에서는 Int를 매개변수로 받고 Int를 반환값으로 돌려주는 함수 'f'를 매개변수로 받는 고차 함수 'formatResult'를 선언했다. 매개변수로 들어가는 함수의 타입은 '(Int) -> Int'로, 이와 타입이 동일한 모든 함수를 매개변수로 받을 수 있다. 아래의 코드에서도 factorial 함수와 abs함수 모두 타입이 동일하기 때문에 정상적으로 동작하는 것을 확인할 수 있다.

fun factorial(i: Int): Int {
	tailrec fun go(n: Int, acc: Int): Int =
    	if (n <= 0) acc
        else go(n - 1, n * acc)
    return go(i, 1)
}

fun formatResult(name: String, n: Int, f: (Int) -> Int): String {
	val msg = "The %s of %d is %d"
    return msg.format(name, n, f(n))
}

fun main() {
	println(formatResult("factorial", 7, ::factorial))
    println(formatResult("absolute value", -42, ::abs))
}

 

아래의 코드는 우리가 배운 꼬리 재귀를 이용해서 Array에서 key와 동일한 첫 값을 반환하는 로직을 짠 것이다. 이번 코드에서는 타입이 String으로 제한이 되어 있어서 재사용성이 다소 떨어진다. 이를 해결하기 위해서 타입 추상화를 시도해보자.

fun findFirst(ss: Array<String>, key: String): Int {
	tailrec fun loop(n: Int): Int =
    	when {
        	n >= ss.size -> -1
            ss[n] == key -> n
            else -> loop(n+1)
        }
    return loop(0)
}

 

아래는 'A'로 타입을 추상화한 코드이다. 위의 코드는 String만을 사용해서 재사용성이 떨어졌지만, 아래의 코드는 어떤 type의 element를 담은 Array라도 재사용이 가능하다. 타입의 추상화를 통해서 재사용성이 가능한 함수를 만들 수 있다.

fun <A> findFirst(ss: Array<A>, key: A): Int {
	tailrec fun loop(n: Int): Int =
    	when {
        	n >= ss.size -> -1
            ss[n] == key -> n
            else -> loop(n+1)
        }
    return loop(0)
}

 

꼬리 재귀를 이용한 루프 구현, 고차 함수를 사용한 함수의 매개변수 처리, 타입의 다형성을 이용하면 순수함수만을 이용한 함수형 프로그래밍에 대해서 보다 다양한 구현이 가능해질 것이다. 이를 이용해서 여러가지 알고리즘 등을 풀이하면서, 함수 단위로 비지니스 로직을 모듈화하고 추론이 쉬운 코드를 작성하는 연습을 해보도록 하자.

 

https://github.com/funfunStudy/algorithm