Burt.K

코코아를 좋아하는 프로그래머입니다 ;)

시그마와 Fold

알고리즘을 구현할 때, 루프(loop)는 꼭 필요하다. 루프를 사용한다는 것은 우리가 어떤 시퀀스, 즉 어떤 자료의 목록인 리스트를 다룬다는 것을 뜻한다. 수학에서 리스트를 다루는 가장 대표적인 루프는 시그마이다.

sigma_1to4

시그마는 리스트를 받아 리스트의 각 원소를 합하는 루프다. 우리에게 익숙한 명령형 언어로 시그마를 작성해 보면 아래와 같다.

func sigma1(n: Int) -> Int {
    var sum = 0
    for i in 1...n {
        sum = sum + i
    }
    return sum
}
sigma1(10)
 ==> 55

위의 sigma1을 보면 루프 내에서 sum의 상태와 i 변수의 상태가 변하는 것을 볼 수 있다. 순수 함수형 언어를 좋아하는 사람들에게는 위와 같은 상태 변화가 달갑지만은 않다고 한다. 그것은 어떤 함수 f가 있을 경우, 항상 같은 p가 함수에 입력되면 항상 같은 q가 출력되는 것이 수학적인 함수의 정의와 가깝고 부수효과(side effect)가 없는 참조무결성의 함수가 되기 때문이다.

위의 sigma1 함수는 간단한 예제이지만 명령형 언어에 존재하는 함수들은 대부분 함수 내에서 변수의 상태를 변경하는 대입문 = 을 가지고 있다. 멀티 코어, 멀티 스레드 프로그래밍이 일반화 되면서 이러한 대입문이 함수를 호출할 때마다 결과값이 달라질 수도 있는 부수효과를 만들어내고 있고 그 결과 참조무결성을 지킬 수 없는 함수가 될 수도 있게 되었다.

그렇다면 함수형 언어에서는 어떻게 부수효과가 없는 즉, 대입문이 없는 시그마 함수를 만들 수 있을까? 함수형 언어의 해법은 재귀를 사용하는 것이다.

func sigma2(n: Int) -> Int {
    if n == 1 {
        return 1
    }
    return n + sigma2(n-1)
}
sigma2(10)
 ==> 55

잠깐, 주의할 점은 어느 것이 더 좋다고 할 수 없는 것이다. sigma1의 경우에는 성능과 메모리의 이점이 있고 sigma2는 성능과 메모리 보다는 부수효과를 없게 만드는 것이다. 퀵정렬을 생각해 봐도 그렇다. 퀵정렬을 하기 위해서는 주어진 리스트 L을 파티션하는 것이 필수 인데 이것을 하는 방법은 재귀를 사용해 구현하는 방법과 리스트 L의 원소를 서로 스왑(swap)해서 파티션하는 in place partition 방법이 있다. 재귀를 사용하는 퀵정렬은 코드를 적게 써서 알고리즘을 간결하게 표현할 수 있지만 성능과 메모리 사용량은 in place partition보다 좋지 않다.

이제 다시 원 주제인 fold로 가기 위해 다시 sigma함수를 생각해 보자. 정수 n을 주는 것이 아니라 목록 L을 주면 어떻게 구현해야 할까?

func sigma3(list: [Int]) -> Int {
    if list.isEmpty { return 0 } // base case
    return list.first! + sigma3(Array(list.dropFirst()))
}
sigma3(Array(1...4))
 ==> 10

sigma3함수는 재귀함수의 기본골격을 그대로 사용해 주어진 리스트 L의 원소합을 구한다. 재귀함수의 기본골격은 base case라는 재귀 탈출 조건을 가지고 있고 그 다음은 자기 자신을 다시 호출하는 재귀 부분이다.

sigma3함수는 아래의 단계로 동작한다.

호출 과정을 나타내 보면 아래와 같다.

  1. sigma3([1,2,3,4])
  2. sigma3(1 + [2,3,4])
  3. sigma3(1 + 2 + [3,4])
  4. sigma3(1 + 2 + 3 + [4])
  5. sigma3(1 + 2 + 3 + 4 + [])
  6. sigma3(1 + 2 + 3 + 4 + 0)
  7. 1 + 2 + 3 + 4 + 0
  8. 10

Fold

fold는 함수형 언어의 리스트 연산 중 하나로 리스트가 주어졌을 경우, 재귀호출을 사용해 연산하는 과정을 패턴화 한 것이다. 이 패턴을 살펴보면,

  1. 초기값S와 리스트 L을 주어 함수를 호출한다.
  2. 텅빈 리스트가 base case다. 즉, 재귀의 탈출 조건이다.
  3. 리스트를 제일 첫 요소(head)와 그 나머지로 나눈다(tail, L’)
  4. 초기값과 head에 어떤 연산 OP을 해서 새로운 초기값 S’과 L’으로 자기 자신을 다시 호출한다.
  5. Base Case에 도달하면 겹겹이 쌓여온 초기값 S’을 반환한다.

이를 바탕으로 시그마를 다시 구현해 보면 아래와 같다.

func sigma4(S: Int, L: [Int]) -> Int {
    if L.isEmpty { return S }
    return sigma4(S + L.first!, L: Array(L.dropFirst()))
}
sigma4(0, L: [1,2,3,4])

위의 sigma4를 보면 초기값 S = 0 이고 어떤 연산 OP는 (+) 이다. 이 두가지를 내 마음대로 변경할 수 있다면 아주 다양한 리스트 연산을 만들 수 있는데 그렇게 할 수 있게 만든 것이다 바로 fold다.

이제 fold를 구현해 보자.

func fold<S,L>(s: S, _ l: Array<L>, _ op: (S, L) -> S) -> S {
    if l.isEmpty { return s }
    return fold(op(s, l.first!), Array(l.dropFirst()), op)
}

fold를 사용해 sigma를 표현하면 아래와 같다.

fold(0, [1,2,3,4], (+))
 ==> 10

위의 fold 함수의 구현을 좀 더 명확하게 표현하기 위해서 Array에 head및 tail확장을 만들어 다시 작성해 보자.

extension Array {
    func empty() -> Bool {
        return self.count == 0
    }
    
    var head: Element? {
        get {
            return self.first
        }
    }
    
    var tail: Array<Element>? {
        get {
            if self.empty() { return nil }
            return Array(self.dropFirst())
        }
    }
}
func fold<S,L>(s: S, _ list: Array<L>, _ op: (S, L) -> S) -> S {
    if list.empty() { return s }
    return fold(op(s, list.head!), list.tail!, op)
}

이제 fold연산자를 사용해서 또 다른 리스트 연산자를 만들어 보자.

리스트 L의 합은 sigma에서 보았듯이 아래처럼 구현할 수 있다.

func sum(L : [Int]) -> Int {
    return fold(0, L, (+))
}
sum([1,2,3,4])
 ==> 10

리스트 L에서 최대값도 구할 수 있다.

func maximum(L: [Int]) -> Int {
    return fold(0, L, max)
}
maximum([1,2,3,4])
 ==> 4

리스트 L에서 최소값도 구할 수 있다.

func minimum(L: [Int]) -> Int {
    return fold(L.first!, L, min)
}
minimum([1,2,3,4])
 ==> 1

리스트 L에 담긴 값이 모두 true인지 검사할 수 있다.

func isItTruth(L: [Bool]) -> Bool {
    return fold(true, L, { $0 && $1 })
}
isItTruth([true, true, true, true])
 ==> true
isItTruth([true, true, false, true])
 ==> false

리스트 L에 담긴 값 true인 값이 존재하는지 검사할 수 있다.

func canItBeTruth(L: [Bool]) -> Bool {
    return fold(false, L, { $0 || $1 })
}
canItBeTruth([false, false, false, false])
 ==> false
canItBeTruth([false, false, true, false])
 ==> true

리스트 L을 역순으로 만들 수 있다.

extension Array {
    func push(e : Element) -> Array<Element> {
        var result = Array(self)
        result.insert(e, atIndex: 0)
        return result
    }
}

func reverse<T>(L: Array<T>) -> Array<T> {
    return fold(Array<T>(), L, { return $0.push($1) })
}
reverse([1,2,3,4])
 ==> [4,3,2,1]

리스트 L의 필터 연산을 만들 수 있다.

func _filter_<T>(L: Array<T>, predicate: (T -> Bool)) -> Array<T> {
    return fold(Array<T>(), L, { predicate($1) ? $0._append_($1) : $0 })
}
_filter_([1,2,3,4], predicate: { $0 % 2 == 0 })
 ==> [2,4]

리스트 L의 원소 E에 어떤 연산을 할 수 있는 map 연산을 만들 수 있다.

func _map_<A, B>(L: Array<A>, op: (A -> B)) -> Array<B> {
    return fold(Array<B>(), L, { $0._append_(op($1)) })
}
_map_([1,2,3,4], op: { $0 * 100 })
 ==> [100, 200, 300, 400]

눈여겨 볼 점은 reverse, map, filter 연산이 모두 새로운 리스트를 만들어 반환한다는 것이다. 이것은 부수효과가 없는 참조무결성의 함수를 만들기 위함이기 때문이다.

fold연산은 left fold와 right fold로 나뉜다. 이를 줄여 foldl과 foldr로 부른다. foldl과 foldr의 차이점을 간략히 얘기하면 리스트를 왼쪽부터 처리하는냐 아니면 오른쪽부터 처리하느냐이다. 위키피디아의 그림을 첨부하면 아래와 같다.

foldlfoldr

foldr이 중요한 이유는 Lazy Evaluation과 결합하여 무한 리스트에 foldl보다 더 효율적으로 연산 할 수 있게 만들어 주기 때문이다. foldl과 foldr의 자세한 내용은 헤스켈 책을 참고하는 것이 좋다.

참고자료

← Swift와 C언어의 Pointer
Swift로 즐기는 이미지프로세싱 →