002 Functional Programming Example

코틀린으로 함수형 프로그래밍 시작하기 #

[고차함수 : 함수를 함수에 넘기기] #

함수형 프로그램을 작성할때 기본이 되는 몇가지 주제

  1. 함수도 값이다.
  2. 함수를 변수에 대입하거나 데이터 구조에 저장하거나 함수의 인자로 넘길 수 있다.

고차함수란? 다른 함수를 인자로 받는 함수

고차함수 예제 어떤 수의 절댓값과 다른 수의 계승(팩토리얼; factorial)을 출력하는 프로그램

  1. 루프를 함수적으로 작성하는 방법
  • n의 계승을 계산하는 함수를 추가한다.
  • 재귀(recursion)를 통해 순수 함수로 루프를 작성할 수 있다.
fun factorial(i: Int): Int {
    fun go(n: Int, acc: Int): Int = // <1>
        if (n <= 0) acc // 루프를 종료시키려면 재귀 호출을 하지 않고, 값을 반환한다.
        else go(n - 1, n * acc) // 재귀 호출
    return go(i, 1) // <2>
}

i=1 go(0, 1x1) i=2 go(1, 2x1) i=3 go(2, 3x2) i=4 go(3, 4x6) i=5 go(4, 5x24)

코틀린은 이런 식의(루프로 표현할 수 있는) 재귀를 수동으로 감지하지는 않지만 함수 앞에 tailrec 변경자를 붙이도록 요구한다. tailrec이 붙은 경우 컴파일러는 재귀 호출이 꼬리 위치(tail position)인 경우에 한해 while 루프로 작성했을 때와 같은 종류의 바이트 코드를 토해낸다. => “꼬리 위치에 있는 재귀 호출을 최적화해 while 루프 형태로 변환한다.”

  • 코틀린의 꼬리 호출
fun factorial(i: Int): Int {
    tailrec fun go(n: Int, acc: Int): Int = // <1>
        if (n <= 0) acc
        else go(n - 1, n * acc) // <2>
    return go(i, 1)
}

재귀적인 함수 호출을 하는 호출자가 재귀 함수 호출이 반환값을 즉시 호출하기만 하고 다른 아무일도 하지 않을때, 재귀 호출이 꼬리 위치에 있다고 말한다.

  • 꼬리 위치에 있다 : go(n-1, n*acc)
  • 꼬리 위치에 있지 않다 : 1 + go(n-1, n*acc)

어떤 함수의 모든 재귀 호출이 꼬리 위치에 있고 함수 앞에 tailrec 변경자가 붙은 경우 코틀린 컴파일러는 재귀를 이터레이션시 호출 스택을 소비하지 않는 반복적인 루프로 컴파일한다. => 이는 스택 오버플로우를 방지하고 메모리를 효율적으로 사용하는 데 도움이 된다.

첫번째 고차함수 작성하기

object Example {
    private fun abs(n: Int): Int =
        if (n < 0) -n
        else n

    private fun factorial(i: Int): Int { //<1> 계층함수(formatFactorial())를 추가했으므로 private로 변경
        fun go(n: Int, acc: Int): Int =
            if (n <= 0) acc
            else go(n - 1, n * acc)
        return go(i, 1)
    }

    fun formatAbs(x: Int): String {
        val msg = "The absolute value of %d is %d"
        return msg.format(x, abs(x))
    }

    fun formatFactorial(x: Int): String { //<2> 새로 추가한 함수 (결과 출력)
        val msg = "The factorial of %d is %d"
        return msg.format(x, factorial(x))
    }
}

fun main() {
    println(Example.formatAbs(-42))
    println(Example.formatFactorial(7)) //<3>
}

두 함수 formatAbs, formatFactorial은 거의 같다. 이 두 함수를 일반화해서 formatResult() 함수를 만들자.

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

고차함수

fun formatResult(name: String, n: Int, f: (Int) -> Int): String { ... }

f에 대해서도 타입을 지정한다. f가 정수를 인자로 받고 정수를 반환하는 함수라는 뜻이다.

abs()나 factorial()을 formatResult의 f 인자로 넘길 수 있다.

println(formatResult("factorial", 7, ::factorial))
println(formatResult("absolute value", -42, ::abs))

[다형적 함수 : 타입에 대해 추상화하기] #

다형적(polymorphic) 함수 : 고차 함수를 작성할때 어떤 타입이 주어지든 관계없이 동작하는 코드

예제

  1. 배열에서 어떤 문자열을 찾는 단형적 함수
fun findFirst(ss: Array<String>, key: String): Int {
    tailrec fun loop(n: Int): Int =
        when {
            n >= ss.size -> -1 // <1>
            ss[n] == key -> n // <2>
            else -> loop(n + 1) // <3>
        }
    return loop(0) // <4>
}
  1. 위 1)번의 단형적 함수를 다형적 함수로 변환
  • 술어 함수(predicate function)는 어떤 조건을 평가하여 참(true) 또는 거짓(false) 중 하나를 반환하는 함수
fun <A> findFirst(xs: Array<A>, p: (A) -> Boolean): Int { // <1> 원소 타입이 A인 배열에 작용, 배열의 각 원소에 작용하는 술어 함수를 파라미터로 받음
    tailrec fun loop(n: Int): Int =
        when {
            n >= xs.size -> -1
            p(xs[n]) -> n // <2> 술어 함수를 배열 원소에 적용하기
            else -> loop(n + 1)
        }
    return loop(0)
}

타입 변수 A를 사용하는 위치

  1. 배열의 원소는 모두 A 타입이어야 한다.
xs: Array<A>
  1. p 함수는 A 타입의 값을 인자로 받는다.
p: (A) -> Boolean

두 위치에서 같은 타입 변수를 참조한다는 사실은 findFirst()의 두 인자에서 해당 타입이 같은 타입이어야만 한다는 사실을 암시한다. 컴파일러는 findFirst()를 호출하는 코드가 이 두 부분에서 같은 타입을 사용하도록 강제한다.

[익명 함수를 사용해 고차함수 호출하기] # 

>>> findFirst(arrayOf(7, 9, 13), {i: Int -> i == 9}

{i: Int -> i == 9} 라는 구문을 함수 리터럴이나 익명 함수라고 한다.

[타입에 맞춰 구현하기] #

함수 시그니처에 의해 구현이 하나로 정해지는 예제를 살펴보자.

fun <A, B, C> partial1(a: A, f: (A, B) -> C): (B) -> C = TODO()
  • 부분 적용(partial application)을 수행하는 고차함수다.
  • partial1() 함수는 어떤 값과 함수(인자를 둘 받아서, 다른 결과를 내놓음)를 인자로 받는다.
  • 인자를 하나만 받아서 결과를 내놓는 함수를 반환한다.
  1. 고차함수
f: (A, B) -> C
  1. 반환타입 우리가 반환해야하는 대상의 타입이다.
(B) -> C
  1. 인자 타입이 B인 함수 리터럴을 작성한다. partial1()의 본문 안에서 a값을 자유롭게 사용할 수 있다. 마찬가지로 b도 익명함수의 인자이므로 함수 본문에서 자유롭게 사용할 수 있다.
fun <A, B, C> partial1(a: A, f: (A, B) -> C): (B) -> C =
    { b: B -> TODO() }
  1. 내부 함수가 C 타입의 값을 반환해야한다. C타입의 값을 어떻게 얻을까? C 타입 값은 f 고차함수의 결괏값이다. 따라서 C 타입 값을 얻는 유일한 방법은 f 함수에 A, B 타입 값을 넘기는 것뿐이다.
fun <A, B, C> partial1(a: A, f: (A, B) -> C): (B) -> C =
    { b: B -> f(a, b) }
  • 결과적으로 인자 2개를 받아서 부분적으로 적용해 돌려주는 고차함수가 생긴 것이다. => “A 그리고 A, B를 인자로 받아서 C를 생성해주는 함수가 있다면, A는 이미 인자에 있기 때문에 B만 제공한다면 C를 돌려주는 새로운 함수를 만들 수 있다.”
  1. 코틀린의 타입 추론 특성으로, 타입 애너테이션 생략이 가능하다.
fun <A, B, C> partial1(a: A, f: (A, B) -> C): (B) -> C =
    { b -> f(a, b) } // 여기서 타입 생략
Calendar December 2, 2023
Edit Edit this page