[3장 재귀] 3.7 실전 응용 - 멱집합 구하는 함수

꼬리 재귀 멱집합 구하는 버젼을 공부했다.

1. powerset 함수 기본 

fun <T> Set<T>.head() = first()
fun <T> Set<T>.tail() = drop(1).toSet()

fun <T> powerset(s : Set<T> ) : Set<Set<T>> = when {
    s.isEmpty() -> setOf(setOf())
    else -> {
        val head = s.head()
        val restSet = powerset(s.tail())
        restSet + restSet.map{ setOf(head) + it}.toSet()
    }
}

2. powerset 꼬리 재귀 버전 

tailrec fun <T> powersetTailrec(s : Set<T>, acc : Set<Set<T>>) : Set<Set<T>> = when {
    s.isEmpty() -> acc
    else -> {
        powersetTailrec(s.tail(), acc + acc.map{ it + s.head()  } )
    }
}

3. powerset 확장함수 버젼

tailrec fun <T> powersetTailrec(s : Collection<T>, acc : Set<Set<T>>) : Set<Set<T>> = when {
    s.isEmpty() -> acc
    else -> {
        powersetTailrec(s.tail(), acc + acc.map{ it + s.head()  } )
    }
}

fun <T> Collection<T>.head() = first()
fun <T> Collection<T>.tail() = drop(1)

fun <T> Collection<T>.powerset() : Set<Set<T>> = powersetTailrec(this, setOf(setOf()))

메인 함수 부분

fun main(){
    println(powerset(setOf(1,2,3)))
    println(powersetTailrec(setOf(1,2,3), setOf(setOf())))
    println(setOf(1,2,3).powerset())
}

솔직히 2. powerset 꼬리 재귀 부분을 저렇게 구현하는지 감이 오지 않았었는데, 읽어보고나서 이해했다. 꼬리 재귀가 함수형 프로그래밍에서 효율적으로 사용되는 만큼 많이 연습해보아야겠다.

 

참고 문헌

코틀린으로 배우는 함수형 프로그래밍 (조재용, 우명인 지음) 인사이트