4장 함수형 프로그래밍

코틀린 쿡북 4장을 요약한 내용 입니다.

알고리즘에서 fold 사용하기

반복 알고리즘을 함수형 방식으로 구현하고 싶을 경우 fold 함수를 사용해 시퀀스나 컬렉션을 하나의 값으로 축약시킬 수 있다.

fold 함수는 배열 또는 반복 가능한 컬렉션에 적용할 수 있는 축약 연산이다.

inline fun <R> Iterable<T>.fold(
    initial: R,
    operationL (acc: R, T) -> R
): R

fold는 2개의 인자를 받는다. 첫 번째는 누적자의 초기값이며 두 번째는 두 개의 인자를 받아 누적자를 위해 새로운 값을 리턴하는 함수다. fold의 대표적인 예제로 합(sum) 연산이 있다.

// 초기값이 0이고 2개의 인자를 받는 람다 함수를 제공한다.
fun sum(vararg nums: Int) =
    nums.fold(0) {acc, n -> acc + n }

다음은 fold 연산을 테스트한 결과이다.

// 구현한 sum 함수의 결과를 intArray에 정의된 sum 함수와 비교해보자
@Test
fun `sum using fold`() {
	val numbers = intArrayOf(3, 1, 4, 1, 5 ,9)
	assertEquals(numbers.sum(), sum(*numbers)) // true
}

재귀 연산으로 표현된 팩토리얼을 fold를 사용한 반복 연산과 비교해보자

// case1. 재귀로 구현한 팩토리얼
fun recursiveFactorial(n: Long) BigInteger = 
	when (n) {
		0L, 1L -> BigInteger.ONE
		else -> BigInteger.valueOf(n) * recursiveFactorial(n-1)
	}

// case2. fold로 구현한 팩토리얼
fun factorialFold(n: Long): BigInteger =
    when(n) {
        0L, 1L -> BigInteger.ONE
        else -> (2..n).fold(BigInteger.ONE) { acc, i ->
            acc * BigInteger.valueOf(i) }
    }

case2는 else의 조건문에서 입력 숫자 n까지 범위를 사용해서 BigInteger.ONE에서 시작하는 fold 연산을 적용한다.

fold를 사용해서 피보나치 수 계산하기

fun fibonacciFold(n: Int) =
    (2 until n).fold(1 to 1) { prev, curr), _ ->
        curr to (prev + curr) }.second

Pair의 first와 second 값은 모두 1이다. 그다음 람다는 계산 중인 인덱스를 고려하지 않고 누적 값을 위한 새로운 값을 생성할 수 있다. 이런 이유로 인덱스 대신 밑줄(_)이 위치 표시자(placeholder)로 사용되었다. 이 람다는 현재 값과 이전 값을 할당해 새로운 Pair를 생성하고 이전 값과 현재 값의 합과 동일한 curr 값을 만든다. 결국 출력되는 값은 마지막 Pair의 second 속성 값이다.

reduce 함수를 사용해 축약하기

컬렉션의 값을 축약하고 싶지만 누적자의 초기값을 설정하고 싶지 않을 경우 fold 대신 reduce 연산을 사용하라

reduce 함수는 fold 함수와 비슷하고 사용 목적도 같다. 가장 큰 차이점은 누적자의 초기값 인자가 없다는 것이 fold 함수와 다르다.

inline fun <S, T : S> Iterable<T>.reduce(
    operation: (acc: S, T) -> S
): S

따라서 reduce 함수는 누적자를 컬레겻ㄴ의 첫 번째 값으로 초기화할 수 있는 경우에만 사용할 수 있다.

fun sumReduce(vararg nums: Int) =
    nums.reduce { acc, i -> acc + i }

reduce를 잘못된 방법으로 사용하는 상황이 있다.

모든 입력 값을 서로 더하기 전에 모든 입력값을 수정하고 싶다고 해보자.

fun sumReduceDoubles(vararg nums: Int) =
	nums.reduce { acc, i -> acc + 2 * i }

{3, 1, 4, 1, 5, 9}를 더하는 동안 누적자의 값과 람다의 i 변수를 함께 출력한 결과는 다음과 같다.

acc = 3, i = 1
acc = 5, i = 4
acc = 13, i = 1
acc = 15, i = 5
acc = 25, i = 9

org.opentest4j.AssertionFailedError:
Expected : 46
Actual   : 43

테스트는 실패 했다. 리스트의 첫 번째 값 3은 누적자를 초기화하는 데 사용됐기 때문에 값이 2배가 되지 않는다.

그래서 코틀린 표준 라이브러리 디자이너는 reduce 연산이 비어 있는 컬렉션에서 예외를 던지게 했다.

꼬리 재귀 적용하기

재귀 프로세스를 실행하는 데 필요한 메모리를 최소화하고 싶을 경우에 tailrec 키워드를 추가하라

fun recursiveFactorial(n: Long): BigInteger =
    when(n) {
        0L, 1L -> BigInteger.ONE
        else -> BigInteger.valueOf(n) * recursiveFactorial(n - 1)
    }

개발자는 함수를 구현할 때 반복 알고리즘을 선호하는 경향이 있다. 그러나 각각의 새로운 재귀 호출은 콜 스택에 프레임을 추가하기 때문에 결국 이런 프로세스는 사용가능한 메모리를 초과하게 된다. (StackOverflowError)

꼬리 재귀로 알려진 접근법은 콜 스택에 새 스택 프레임을 추가하지 않게 구현하는 특별한 종류의 재귀다. 이렇게 하면 스택 프레임을 재사용할 수 있다.

@JvmOverloads
tailrec fun factorial(n: Long, acc: BigInteger = BigInteger.ONE): BigInteger =
    when (n) {
        0L -> BigInteger.ONE
        1L -> acc
        else -> factorial(n - 1, acc * BigInteger.valueOf(n))    // 꼬리 재귀 호
    }

tailrec 키워드가 없으면 컴파일러가 재귀를 최적화해야 하는지 알 수 없다. tailrec 키워드를 사용함으로써 해당 함수는 빠르고 효율적으로 반복하게 된다.

재귀 호출은 컴파일러에 의해 while 루프를 사용하는 반복 알고리즘으로 리팩토링되었다.

public static final BigInteger factorial(long n, BigInteger acc) {
	while(true) {
		BigInteger result;
		if ( n == 0L ) {
			result = BigInteger.ONE;
		} else {
			if ( n != 1L ) {
				result = result.multiply(BigInteger.valueOf(n));
				n = n - 1L;
				continue;
			}
		}
		return result;
	}
}

tailrec 변경자를 적용할 수 있는 함수의 자격 요건

• 해당 함수는 반드시 수행하는 마지막 연산으로서 자신을 호출해야 한다.

• try/catch/finally 블록 안에서는 tailrec을 사용할 수 없다.

• 오직 JVM 백엔드에서만 꼬리 재귀가 지원된다.