# 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 백엔드에서만 꼬리 재귀가 지원된다.