함수형 프로그래밍 기초 - 재귀, 카테고리 이론, 모나드(Monad), 고차 함수(Java)

함수형 프로그래밍 기초

---

저번 포스팅에서 함수형 프로그래밍이란 무엇인지, 함수형 프로그래밍의 주요 개념인 불변성, 참조 투명성 등을 알아보았구요, 람다 함수의 기반을 이루는 람다 대수가 무엇인지 알아보았습니다. 그리고 JAVA에서 함수형 프로그래밍을 구현하는 방법인 함수형 인터페이스에 대해서도 간단히 살펴보았습니다. 자세한 내용은 아래 포스팅을 확인해주세요.

 https://porolog.tistory.com/19#comment17080166

함수형 프로그래밍 입문 with 람다 대수, 함수형 인터페이스 (Java)

이번 포스팅에서는 함수형 프로그래밍에서 상태의 변경을 지양하게 되면서 재귀 함수에 대한 의존도가 높아졌는데요, 이에 따른 재귀 함수의 시간 복잡도, 공간 복잡도 측면에서 단점과 이를 보완하기 위한 방법들을 알아보겠습니다. 그리고, 함수형 프로그래밍의 근간을 이루는 수학의 카테고리 이론을 간단하게 살펴보겠습니다.

재귀 함수의 사용

---

함수형 프로그래밍은 상태를 멀리하는 프로그래밍 패러다임이기 때문에, 조건문, 반복문의 사용을 지양합니다. 조건문, 반복문의 사용을 위해서는 상태를 저장해야하고, 상태를 변경해야할 필요성이 생기기 때문이죠. 그렇기에 함수형 프로그래밍에서는 반복문 대신 재귀 함수를 이용해서 반복을 구현합니다. 재귀 함수를 사용할 경우 기존 반복문에서 상태를 저장하고 변경하던 iterator로 사용되던 변수의 역할을 매개변수로 passing되는 인자가 맡게 됩니다. 더 이상 상태를 저장하는 변수가 필요없어지게 된 것이죠. 그렇지만, 재귀 함수를 사용하는 것이 장점만 있는 것은 아닙니다.

 

1. 공간 복잡도 측면 - Stack Overflow

재귀 호출으로 구현하면 상대적으로 공간 복잡도가 높아지게 됩니다. 콜 스택이 많이 쌓이면 런타임 중 스택오버플로우가 발생할 위험성이 있습니다. 기존의 반복문을 사용하는 형태보다 메모리 측면에서 좀 더 최적화가 필요하게 된 것이죠. 이러한 메모리 측면에서 단점을 보완해줄 수 있는 개선책이 꼬리 재귀 최적화, lazy evaluation 등이 있습니다.

 

1.1 꼬리 재귀 vs 재귀

재귀 함수의 반환 값을 매개변수로 passing해서 함수가 호출 되고 어떤 연산도 더 실행할 필요가 없는 재귀 함수의 구현을 꼬리 재귀라고 합니다. 즉, 재귀의 반환 위치가 함수의 끝에 있다고 해서 꼬리 재귀인 것이죠. 꼬리 재귀로 구현을 한다면 문제가 굉장히 단순해지는 효과가 있습니다. 기존 재귀에서는 재귀 함수 호출 전까지 실행하고, 함수의 반환 위치 정보를 스택에 저장해야하는데, 꼬리 재귀 문제에서는 단순히 함수를 순서대로 처음부터 끝까지 선형적으로 실행하고 값을 넘기면 됩니다. 이는 반복문의 실행과 로직이 동일해지는데요, 굳이 콜스택을 쌓을 필요가 없어지기 때문에 반복문으로 치환할 수 있습니다. 이런 경우 스택에 하나의 함수만 쌓이게 됩니다.

public int factorial(int n, int total){
    if(n == 1){
        return total;
    }
    return factorial(n - 1, n * total);
}

위의 꼬리 재귀의 형태로 구현한다면, 아래처럼 선형적인 반복문으로 변환할 수 있습니다. 이를 꼬리 재귀 최적화라고 합니다. 컴파일러가 꼬리 재귀 최적화를 지원한다면, 위의 꼬리 재귀의 형태로 함수를 작성하면 컴파일 타임에 내부적으로 아래 형태로 코드를 변경합니다.

public int FactorialTail(int n){
	int acc = 1;
    
    do{
    	if(n == 1) return;
        acc = acc * n;
        n = n - 1;
    } while(true);
}

1.2 Lazy Evaluation vs Eager Evaluation

Evaluation은 compiler가 코드를 보고 결과를 평가하는 과정, 혹은 함수를 실행하는 과정입니다. 먼저 아래 예제를 살펴보겠습니다.

def func(x, y):
    return x + 1
func(3, 3 + 2)

위 예제에서 내부에서 쓰이지 않는 두번째 매개변수를 평가할 필요가 없습니다. 굳이 3 + 2를 계산하여 리소스를 낭비할 필요가 없습니다. 함수의 실행이 필요한 상황이 오면 함수를 평가 하는 것을 lazy evaluation이라고 합니다. 반면, 위와 같은 상황에서 불필요하더라도 호출시에 모든 함수를 평가하는 것을 (eager)strict evaluation이라고 합니다. eager evaluation은 함수가 할당되자마자 연산을 시작합니다. 기본적으로 자바는 eager evaluation을 사용합니다. 그렇지만 java 8부터는 일부 lazy evaluation을 지원하기 시작했습니다.

• Functional Interface는 Lazy Evaluation을 지원한다.
  • functional interface는 구현 함수가 실행될 때, 평가가 발생합니다.
• Stream API는 Lazy Evaluation을 기반으로 합니다.

public mySet filter(Predicate<T> filterFunction) {
        List<T> arr = Collections.unmodifiableList(elements);
        return new mySet(arr.stream().filter(filterFunction).collect(Collectors.toUnmodifiableList()));
    }
    
public static void main(String[] args) {
	Predicate<Integer> getEvenIndexFunction = (index) -> (index % 2 == 0); //even filter

	mySet.filter(getEvenIndexFunction); //평가 발생
}

위의 예시로 이해해보겠습니다. mySet이라는 객체를 정의하고, 필터 함수를 인자로 받아서 mySet을 반환하는 filter 함수를 구현했습니다. 이 때, stream API로 구현되어있기 때문에, mySet의 원소는 각각 filter -> collect의 실행이 완료된 후에 다음 원소의 평가가 이어집니다. 메모리 측면에서는 한 원소에 대해 filter -> collect를 실행하고 원소의 메모리 공간을 해제할 수 있으므로 효율적입니다. 모든 원소를 메모리에 로딩시킨 후 filter와 collect를 실행하게 되면 메모리에서 많은 공간이 동시에 필요로 하겠죠. 즉, 지금 실행되고 있는 것만 메모리에 할당하는 것입니다. 이것이 Stream API가 lazy evaluation을 기반으로 한다고 할 수 있는 이유입니다.

다음으로, filterFunction이라는 함수형 인터페이스의 Predicate 구현체를 매개 변수로 받는데, 이 함수의 평가는 함수의 선언에 발생하는 것이 아니라, mySet에서 filter 메서드를 실행할 때 평가가 발생합니다.

lazy evaluation의 장점

• 메모리에 필요한 값만 할당하고 사용이 끝나면 해제할 수 있기 때문에 공간 복잡도가 개선됩니다.
• 무한 자료 구조, 재귀적으로 무한으로 list를 생성하는 재귀가 가능합니다.

def addOne(n):
    [n] + addOne(n + 1)

list = addOne(1) // [1, 2, 3, 4, 5, 6, …]

lazy evaluation의 경우 재귀의 모든 depth가 아닌 현재 실행되는 depth만 평가하므로, 위와 같은 상황에서 메모리 문제가 발생하지 않습니다. 

 

2. 시간 복잡도 측면 - 동일 연산의 반복

재귀 호출로 실행하면 같은 호출의 결과를 저장하지 않기 때문에 같은 연산의 반복성이 높아집니다.

예를 들면 fibonacci 수열의 3번째 값은 f(3) = f(2) + f(1) = f(1) + f(0) + (f1)로 계산되는데, 위 과정에서 f(1)의 값을 이미 알고있지만 함수를 호출해서 f(1)의 값을 확인하는 연산을 반복적으로 실행합니다. 피보나치 수열의 n 수가 높아지면 동일 연산의 반복도가 훨씬 높아질 것입니다. 이미 계산한 결과를 또 계산하는 경우를 줄이기 위해 memoization이라는 기법을 사용합니다. 같은 연산의 결과를 메모리에 임시 저장하여 저장된 값을 사용하며 시간 복잡도를 개선합니다.

 

이번에는, 함수형 프로그래밍의 근간을 이루는 또 다른 수학 체계이론인 카테고리 이론에 대해서 간단히 살펴보겠습니다.  원래는 많은 분량으로 작성해야하는 수학 이론인데 읽기가 쉽지 않고 또 대략적인 내용만 인지하면 되는 부분이라 부담없이 읽어주시면 될 것 같습니다. 수학의 카테고리 이론을 함수형 프로그래밍의 type에 적용하게 되었는데요, monad라는 개념까지 배워보겠습니다.

 

 

카테고리 이론

---

카테고리 이론이란?

제일 먼저 카테고리란 무엇인지 정의해야합니다. 카테고리는 수학에서 집합과 유사한 개념이지만, 집합의 element 뿐만 아니라, 원소간의 관계까지 포함하는 개념입니다. 즉, 대상과 사상으로 이루어져 있습니다.

• 카테고리의 정의
  • 대상(Object, 점으로 표현)
  • 사상(Morphism, 화살표로 표현) : 대상들 사이에 관계에 대한 정보
    • 두 대상 사이에 몇 개든 존재 가능

그렇지만 대상과 관계가 있으면 무조건 카테고리가 될 수 있느냐하면 그것은 아닙니다. 수학적인 카테고리가 되기 위한 조건을 알아보겠습니다. 우선, 카테고리는 합성이 가능해야 합니다. 조금 더 수학적으로 풀어서 쓰면 아래와 같습니다.

 

1. 모든 사상은 자신으로가는 항등 사상이 있어야 합니다.

항등 사상과 다른 사상(f)의 합성은 f와 같은 사상이여야 합니다. 즉, 항등원이 성립해야합니다.

 

2. 임의의 두 사상에 대해 둘을 합성한 사상이 반드시 존재해야 합니다. 즉, 임의의 두 대상에 대해 사상 f,g는 반드시 존재해야 하며, f, g를 각각 mapping한 것과 구분 불가해야합니다. 

 

조금 복잡하죠? 카테고리 이론이란 범주들에 공통적으로 적용할 수 있는 이론을 추상화 한 학문입니다. 즉 어떤 자연 현상을 추상화한 학문이 아닌, 추상화한 학문을 분석할 때 사용하는 추상화한 개념들이 이루는 체계를 추상화한 것입니다. 그렇기에 고도의 추상화가 이루어져있기에 이해가 쉽지는 않습니다. 자연을 합성 관계를 통해 분석하고, 분석을 통해 생성되는 카테고리에 대한 이론으로, 카테고리는 수학의 여러 다른 분과에서 찾아지는 공통적인 구조를 찾기 위한 메타수학이론이라고 정의할 수 있습니다.

• 달라야할 분야들이 공유하는 공통된 구조, 대상/대상 간의 합성 가능한 관계가 존재
• 수학적 구조로 만들어 연구하여 여러 분야에 적용할 수 있는 정리

사상 (morphism)

수학에서 선형대수학, 미분기하학, 위상수학, 집합론 등 수학의 분야마다 다루는 대상이 다 다르죠. 수학적 구조(공리계)가 다르다고 이야기합니다. 이러한 관계를 일반화하기 위한 개념으로 사상(map)이 등장합니다. 수학적인 구조를 반영한 함수를 사상이라고 합니다. 값이 대응되는 함수의 개념이 아닌 광의의 개념입니다. 

 

프로그래밍에서 카테고리 이론을 사용하는 이유

그래서 프로그래밍과 상관없어보이는 카테고리 이론을 배워야하는 이유가 무엇일까요?

프로그래밍 언어 사이에 나타나는 공통적인 개념, 관계가 위에서 언급했던 카테고리 조건에 부합하여, 카테고리의 이론을 적용할 수 있습니다.

• 모든 프로그래밍 언어에는 타입이 존재합니다.
• 타입 간에는 합성 가능한 관계(함수, 사상)이 존재합니다.

 

즉, 모든 타입을 대상(Object)으로, 타입 간의 함수를 사상(morphism)으로 하는 카테고리 이론이 적용가능해진 것입니다.

 

Functor(함자)

카테고리 간 대응시킬 수 있는 수단(사상)을 Functor라고 합니다. 함수와 이름이 비슷하죠. 함수와 구분을 한 이유는 함수처럼 f(A) = B가 성립하는 값 대응의 개념이 아니기 때문입니다. 함자는 한 카테고리의 대상과 사상을 다른 카테고리의 대상과 사상에 대응시키는 관계를 의미합니다. 대응은 대상과 사상 간에 관계를 보존합니다.

 

Endofunctor(자기 함자)

여기서부터 프로그래밍에 의미있는 개념이 등장합니다. 정의역과 공역이 같은 함자, 즉 카테고리 C에서 C로 대응시키는 함자를 endofunctor라고 정의합니다. 프로그래밍에서는 카테고리 이론의 대상을 타입, 사상을 타입 간의 함수로 대응시킨다고 했었죠.  아무리 대응시켜도 타입이 변하지 않는 함자를 자기 함자라고 볼 수 있습니다. 

Monad(모나드)

모나드는 자기 함자를 구현하기 위한 개념입니다. 대응이 발생해도 타입이 변하지 않는 함자가 자기 함자라고 했죠. 함수에서 어떤 실행 결과를 반환할 때 타입이 변한다면 이는 사이드 이펙트(부수효과)가 발생한 것입니다. 즉, 입력에 따라서 결과의 집합이 바뀔 수 있는 가능성이 있습니다. 예를 들어, 정수를 인자로 받아 그대로 반환하고, 0이면 에러를 throw하는 함수를 생각해봅시다. 0이 아닌 정수인 경우 반환되는 타입은 항상 int입니다. int -> int로 대응되는 함자라고 볼 수 있습니다. 그런데, 0이 입력되는 경우에는 에러가 생기므로 int -> error로 순수성이 깨지게 됩니다. 이러한 순수성을 보장하기 위해 등장한 개념이 모나드입니다. 모나드 구현체는 error와 정상 출력의 집합을 추상화한 타입으로 묶어 monad -> monad의 자기 함자가 될 수 있도록 합니다. 대표적인 예시가 java에서는 Optional입니다. Optional<Integer> 타입은 null 타입과 Integer를 묶어 null, Integer 반환에 상관없이 Optional 타입의 반환을 보장합니다. 즉, 순수함수가 아닌 것을 자기 함자로 구현함으로써 순수함수로 만들 수 있게 된 것입니다.

Monad -> Monad로 반환되므로 합성 함수로 구현이 가능합니다. Monad -> Monad -> Monad ... -> Monad처럼 연산의 합성이 가능해집니다. 모나드로 정의되는 서브루틴들은 합칠 수 있는 연산의 정의하고 추상화하는 개념이라고도 볼 수 있습니다. 

고차함수 Filter, Map 구현해보기

Monadic Map 함수와 Filter 함수, 출력을 위한 display 함수를 자바로 구현해보겠습니다. 먼저 다룰 객체 집합인 SquadSet을 정의합니다. SquadSet은 수학의 집합 개념과 비슷합니다. 내부적으로는 제네릭의 배열을 가지게 했고, 합집합, 차집합, 교집합과 getter를 stream으로 구현했습니다.

 

public class SquadSet <T,R> {
    private final List<T> elements;

    SquadSet(List<T> elements) {
        this.elements = elements;
    }

    public List<T> sum(SquadSet other) {
        List<T> arr = Collections.unmodifiableList(elements);
        List<T> otherArr = Collections.unmodifiableList((List<T>)other.getElements());

        return Stream.concat(arr.stream(), otherArr.stream()).distinct().collect(
                Collectors.toUnmodifiableList());
    }

    public List<T> complement(SquadSet other) {
        List<T> arr = Collections.unmodifiableList(elements);
        List<T> otherArr = Collections.unmodifiableList((List<T>)other.getElements());

        return arr.stream().filter(e -> !otherArr.contains(e)).collect(Collectors.toUnmodifiableList());
    }

    public List<T> intersect(SquadSet other) {
        List<T> arr = Collections.unmodifiableList(elements);
        List<T> otherArr = Collections.unmodifiableList((List<T>)other.getElements());

        return arr.stream().filter(otherArr::contains).collect(Collectors.toUnmodifiableList());
    }

    public List<T> getElements() {
        return Collections.unmodifiableList(elements);
    }
}

그리고 함수를 인자로 받아 전달할 수 있는 고차함수인 filter, map과 출력 함수 display를 구현했습니다.

filter : filter 함수를 인자로 받아 true인 값만 객체로 반환합니다. SquadSet -> SquadSet

map : map 함수를 인자로 받아 각 element에 적용하여 객체로 반환합니다. SquadSet -> SquadSet

display : 출력 함수를 인자로 받아 출력합니다. SquadSet -> (void)

 

filter 함수는 SquadSet을 받아서 항상 부수효과 없이 SquadSet으로 반환하기 때문에 모나드라고 할 수 있습니다. map 함수도 마찬가지로 map 함수에 의해 type이 <T> -> <R>로 매핑되기는 하지만 SquadSet은 타입을 제너릭으로 선언해서 포괄하기 때문에 마찬가지로 모나딕하다고 볼 수 있습니다. 반면 display 함수는 SquadSet을 인자로 받아 출력되기 때문에 display 함수 이후에는 더 이상 함수를 합성해서 사용할 수 없습니다. 위의 모나드에서 모나드란 '합성 가능한 연산의 정의'라고도 하는 것이 이런 의미에서입니다.

public SquadSet map(Function<T,R> mapFunction) { // Type T->R
        List<T> arr = Collections.unmodifiableList(elements);
        return new SquadSet(arr.stream().map(mapFunction).collect(Collectors.toUnmodifiableList()));
    }

    public SquadSet filter(Predicate<T> filterFunction) {
        List<T> arr = Collections.unmodifiableList(elements);
        return new SquadSet(arr.stream().filter(filterFunction).collect(Collectors.toUnmodifiableList()));
    }

    public void display(BinaryOperator<T> reducer, Consumer<T> consumer) {
        List<T> arr = Collections.unmodifiableList(elements);
        arr.stream().reduce(reducer).ifPresent(consumer);
    }
}

 

Java는 함수를 인자로 전달하기 위해서는 함수형 인터페이스를 구현해서 사용해야합니다. 저는 집합에서 각 원소를 제곱한 후 짝수 인덱스의 원소만 출력하는 함수를 구현했습니다. 함수의 인자의 형태, 반환 값 형태에 따라 Function, Predicate, BinaryOperator, Consumer, Supplier 등이 있습니다. 모나드 구현체를 선언해서 각 함수를 구현한 후 최종적으로 stream을 사용하는 것처럼 여러 함수의 합성들로 결과를 구할 수 있었습니다. 원소 -> 제곱한 값과 짝수인 인덱스의 원소를,

원소 -> 제곱한 원소 -> 인덱스가 짝수인 원소 -> 출력처럼 함수들의 합성으로 함수들을 구현하는 고차함수를 구현해보았습니다.

public static void main(String[] args) {

        SquadSet a = new SquadSet(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9));
        
        Function<Integer, Integer> squareFunction = (map) -> (map * map); //square function
        Function<Integer, String> toStringFunction = (num) -> Integer.toString(num); // toString Function
        Predicate<Integer> getEvenIndexFunction = (index) -> (index % 2 == 0); //even filter
        BinaryOperator<String> reducer = (str1, str2) -> str1 + ", " + str2; // reducer
        Consumer<String> consumer = (str) -> System.out.println(str); //출력

        a.map(squareFunction).filter(getEvenIndexFunction).map(toStringFunction)
            .display(reducer, consumer);
        //제곱, 짝수 인덱스, 스트링 변환, 출력
        }
    }
}