함수형 프로그래밍의 Fold(FoldLeft, FoldRight의 차이점)

Fold 란?

fold란 고차 함수중 하나입니다.
재귀적으로 정의된 자료구조를 분석하고, 전달받은 명령을 사용하여 재결합하고, 재귀적으로 수행된 결과들로 반환값을 만들어내는 연산입니다. 

Fold (고차 함수) - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

하나하나 의미를 살펴봅시다.

 

재귀적으로 정의된 자료구조

sealed class List<out A> {
    companion object {
        fun <A> of(vararg aa: A): List<A> {
            val tail = aa.sliceArray(1..<aa.size)
            return if (aa.isEmpty()) Nil else Cons(aa[0], of(*tail))
        }
    }
}
object Nil : List<Nothing>()
data class Cons<out A>(val head: A, val tail: List<A>) : List<A>()

Cons는 멤버변수로 List 타입을 갖기 때문에 재귀적인 자료구조라고 할 수 있습니다.

전달받은 명령을 사용하여 재결합

fun <A, B> foldRight(xs: List<A>, z: B, f: (A, B) -> B): B =
    when (xs) {
        is Nil -> z
        is Cons -> f(xs.head, foldRight(xs.tail, z, f))
    }

fun main() {
    val list = Cons(3, Cons(6, Cons(9, Nil)))
    foldRight(list, 0) { a, b ->
        a + b
    }
}

foldRight함수에 명령으로 { a, b -> a + b } 람다를 전달했습니다. 
foldRight안에서는 f(xs.head, foldRight(xs.tail, z, f)) 를 통해 재결합 하고 있습니다. 

재귀적으로 수행된 결과들로 반환값을 만들어 낸다

is Cons -> f(xs.head, foldRight(xs.tail, z, f))

f연산은 { a, b -> a + b }입니다. 

xs.head + foldRight(xs.tail, z, f) 를 결과로 반환합니다.

xs.head + (xs.tail.head + foldRight(xs.tail.tail, z, f))
xs.head + (xs.tail.head + (xs.tail.tail.head + foldRight(xs.tail.tail.tail, z, f))) ...
이렇게 재귀적으로 계산되다가 Nil 조건을 만나면 반환값을 반들어냅니다. 

 

Fold 방향

fold는 "재귀적으로 수행" 을 어떤 방향으로 적용하는 지에 따라 FoldLeft와 FoldRight가 나뉘어집니다.

• FoldLeft 
  • 요소의 앞에서 부터 계산
  • (((1 + 2) + 3) + 4) +5
• FoldRight 
  • 요소의 뒤에서 부터 계산
  • 1 + (2 + (3 + (4 + 5)))

FoldLeft

sealed class List2<out A> {
    companion object {
        fun <A> of(vararg aa: A): List2<A> {
            val heads = aa.sliceArray(0..<aa.size - 1)
            return if (aa.isEmpty()) Nil2 else Cons2(of(*heads), aa.last())
        }
    }
}
object Nil2 : List2<Nothing>()
data class Cons2<out A>(val heads: List2<A>, val last: A) : List2<A>()

fun <ITEM1, ITEM2> foldLeft(list: List2<ITEM1>, defaultValue: ITEM2, combine: (ITEM2, ITEM1) -> ITEM2): ITEM2 =
    when (list) {
        is Nil2 -> defaultValue
        is Cons2 -> combine(foldLeft(list, defaultValue, combine), list.last)

    }

foldLeft를 구현하기위해 List2 자료구조를 새로 만들었습니다. 

// List
val list = Cons(3, Cons(6, Cons(9, Nil)))


// List2
val list1 = Cons2(Cons2(Cons2(Nil2, 1), 2), 3)

리스트를 정의할 때 차이점이 있습니다. 

첫번째 요소에 도달할 때 까지 재귀적으로 foldLeft를 호출하게 됩니다. 

List2를 새로 만들지 않고, foldLeft를 구현할 수 도 있습니다. 

tailrec fun <ITEM1, ITEM2> foldLeft(list: List<ITEM1>, defaultValue: ITEM2, combine: (ITEM2, ITEM1) -> ITEM2): ITEM2 =
    when(list) {
        is Nil -> defaultValue
        is Cons -> foldLeft2(list.tail, combine(defaultValue, list.head), combine)
    }

첫 번째 요소부터, defaultValue에 누적하면서 마지막요소까지 계산해갑니다

위의 List2의 예시는 틀렸습니다. 
앞에서 부터 계산하는지와 뒤에서 계산하는지와는 별개로 재귀적 호출된 함수의 결과를 언제 조합하냐가 핵심입니다. 

먼저 계산한 후 다음 재귀 호출을 하면, Left
모든 재귀호출이 끝난 후 콜스택을 돌아오면서 계산을 마치면 Right입니다. 

The laboratory of the wizard :: 재귀호출의 구분과 foldLeft/foldRight (tistory.com)

 

FoldRight

fun <ITEM1, ITEM2> foldRight(list: List<ITEM1>, defaultValue: ITEM2, combine: (ITEM1, ITEM2) -> ITEM2): ITEM2 =
    when (list) {
        is Nil -> defaultValue
        is Cons -> combine(list.head, foldRight(list.tail, defaultValue, combine))
    }

foldRight는 위에서 봤던 정의와 동일합니다. 

마지막 요소를 만날 때까지 재귀적으로 호출되다가, 다시 돌아오면서 combine되는 형식입니다. 

 

특징

꼬리 재귀

foldLeft는 꼬리 재귀로 만들 수 있지만, foldRight는 꼬리 재귀로 만들 수 없다. 

 

결합 법칙 성립하지 않는 연산

• FoldLeft 
  • 요소의 앞에서 부터 계산
  • (((1 + 2) + 3) + 4) +5
• FoldRight 
  • 요소의 뒤에서 부터 계산
  • 1 + (2 + (3 + (4 + 5)))

 

위에서 이런 정의를 했었습니다.
이 정의에서는 + 연산을 하였기 때문에 foldLeft, foldRight 모두 같은 결과가 나왔습니다. 

+연산은 결합법칙이 적용되기 때문인데, 결합 법칙이 적용되지 않는 ÷ 연산은 어떨까요?

4 -> 2 -> 2 리스트가 있다고 해보겠습니다. 

• foldLeft : ((4 / 2) / 2) = 1
• foldRight : (4 / (2 / 2)) = 4

이렇게 결합 법칙이 적용되지 않는 연산은 foldLeft와 foldRight의 결과가 다를 수 있습니다. 

FoldLeft와 FoldRight 제대로 알고 사용하기 | leeyh0216's devlog