Skip to content

Latest commit

 

History

History
263 lines (171 loc) · 9.48 KB

함수형 프로그래밍 Ⅱ.md

File metadata and controls

263 lines (171 loc) · 9.48 KB
Raw

함수형 프로그래밍Ⅱ

간단한 함수형 프로그래밍 복습

  • 순수함수를 조합해서 불변성(데이터가 변하지 않는 속성)을 이용해 프로그래밍을 만드는 방식

함수형 프로그래밍으로 어떤 방식이 있을까?

  • 커링
  • 메모이제이션
  • 재귀
  • 합성
  • 모나드

커링 (Curring)

  • 인자를 여러개 받는 함수를 분리하여, 인자를 하나 씩만 받는 함수의 체인으로 만드는 방법

  • 함수를 재사용하는데에 있어서 유용하게 쓰일 수 있는 방식

  • 자바스크립트 내부에는 커링이 내장되어 있지 않지만, 충분히 구현이 가능하다.

  • function greet(greeting, name) {
    console.log(greeting + , ", " + name)
}

  • 위의 함수가 제대로 동작하려면 greeting과 name을 전달받아야한다. 이 함수를 커링 함수로 수정하면

  • function greet(greeting) {
    return function(name) {
        console.log(greeting + , ", " + name)
    }
}

var hello = greet("hello");
hello("world"); // 'hello, world'
hello("john"); // 'hello, john'

  • 첫 번째(가장 바깥) 함수가 greeting을 인자로 받고, 반환하는 내부함수가 name을 인자로 받는 형태로 수정할 수 있다.

  • 어떤 함수를 호출 할 때, 인자가 항상 비슷하다면 유용하게 사용할 수 있다.

  • 외부함수 : 새로운 인자를 받지 않아도 되는 부분 / 내부함수 : 새로운 인자를 받야아 하는 부분

메모이제이션 (Memoization)

  • 반복되는 결과를 메모리에 저장하여 다시 계산할 필요없이 빨리 실행하는 기법

  • 캐싱과 같은 기능

  • // 피보나치 수열을 재귀 함수로 계산하는 함수
var count = 0;
var fibonacci = function(number) {
    count ++;
    return number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2);
}

for(var i = 0; i <= 10; i++) {
    console.log(fibonacci(i)); // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
}
console.log("count : " + count) // count : 453

  • 위와 같은 반복문으로 구현이 가능하지만, 매개변수로 10이라는 작은 수를 주어도 fibonacci 함수는 453번 이나 실행이 된다.

  • fibonacci(0) = fibonacci(0) fibonacci(1) = fibonacci(1) fibonacci(2) = fibonacci(0) + fibonacci(1) = fibonacci(0) + fibonacci(1) fibonacci(3) = fibonacci(1) + fibonacci(2) = fibonacci(1) + (fibonacci(0) + fibonacci(1)) fibonacci(4) = fibonacci(2) + fibonacci(3) = (fibonacci(0) + fibonacci(1)) + (fibonacci(1) + (fibonacci(0) + fibonacci(1)))

  • 위와 같이 반복적인 계산할 값을 메모이제이션 패턴을 이용하면 반복되는 계산을 줄일 수 있다.

  • var count = 0;
var fibonacci = function() {
    var memo = [0, 1];
    var fib = function(number) {
        count++;
        var result = memo[number];
        if(typeof result !== 'number') {
            result = fib(number - 1) + fib(number - 2);
            memo[number] = result;
        }
        return result;
    };
    return fib;
}();

for(var i = 0; i <= 10; i++) {
    console.log(fibonacci(i)); // 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
}
console.log("count : " + count) // count : 29

  • 첫 번째 연산함수는 453번 이 실행되었지만 메모이제이션 패턴을 사용하면 29번 만에 실행이 완료된다.

  • 메모이제이션은 속도면에서 큰 이점이 있지만, 메모리사용량이 소비되기 때문에 많은 RAM을 사용하는 함수를 처리해야하는 경우 영향을 준다.

재귀 (Recursive)

  • 1~n 까지 팩토리얼을 구하는 경우, 재귀함수와 for 반복문을 하는 경우 어떤 것이 더 빠를까?
  • 동일한 기능을 하는 경우 for 반복문을 작성하는 것이 더 빠르다.
  • 그럼 재귀함수를 써야하는 이유와 for 반복문와 비교해서 더 나은점이 무엇인가?

위의 세 줄은 면접 때 받았던 질문들이라고 합니다. 어떤식으로 답변을 해야할 지 생각해보세용~

  • 재귀함수를 쓰는 이유

    1. 알고리즘 자체가 재귀적으로 표현하기 자연스러울 때 (가독성) ex) 하노이 탑, QuickSort 구현 등
    2. 변수 사용 을 줄일 수 있다.

  • 변수 사용을 줄일 수 있다는 것은 메모리에 대한 얘기가 아닌 mutable state (변경 가능한 상태) 를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄일 수 있다는 이야기이다.

    ps) 함수형 프로그래밍은 함수를 일급 객체로 취급하여 함수를 인자로 전달 및 반환하는 것과 비슷하다.

  • 하지만 재귀함수는 단점이 명확하기 때문에 사용하는데에 주의를 해야한다.

    • 메모리를 많이 차지하며, 성능이 반복문에 비해 느리다.
    • 매개변수, 지역변수, 리턴 값, 함수 종료후 돌아가는 위치 모두 스택에 저장되며 반복적으로 호출할 때 스택 메모리가 커지고 반복횟수가 많아지면 stackoverflow 가 발생한다.
    • 스택 프레임을 구성하고 해제하는 과정에서 반복문보다 오버헤드가 들어(필요하기 때문에) 성능도 느려진다.
    • 무한 루프에 빠지지않기 위해 기저 조건 (탈출 조건)이 무조건 있어야 한다.
    • 디버깅 및 실행 흐름을 파악하기 힘들다.

  • 위와 같은 단점이 있지만, 단점을 극복하기 위한 방법도 있다. 바로 꼬리 재귀 !!!

꼬리 재귀 (Tail Recursive)

  • 재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태

  • 기존 재귀의 문제점을 해결할 수 있는 방법이고 다음과 같이 설계해야 한다.

    1. 프로그래머가 재귀함수를 꼬리 재귀 방식으로 개발한다.

    2. 컴파일러가 꼬리 재귀 최적화를 지원해야 한다.

      ps) 컴파일러가 꼬리 재귀 최적화를 지원하지 않으면, 성능 및 메모리의 이점을 얻을 수 없다.

  • // 일반 재귀
int Recursive(int n) 
{
 if(n==1) return 1;
 return n + Recursive(n-1);
}

// 꼬리 재귀
int Tail_Recursive(int n, int acc)
{
 if(n==1) return acc;
 return Tail_Recursive(n-1, n + acc );
}

  • 일반 재귀는 return에 연산이 필요하지만, 꼬리재귀는 return에 연산이 필요없고 연산에 필요한 매개변수만 넘겨준다.

합성 (Composition)

  • y = f(x)
z = g(y)
즉, z = g(f(x)) 가능하다.

  • 함수의 반환값(return 값)이 다른 함수의 입력값으로 사용되는 것

  • 예제가 너무 길어서 링크로 남기겠습니다.

  • https://shoveller.tistory.com/85 (함수형 프로그래밍 합성 예제 , Javascript)

모나드 (Monad)

  • 보통 하스켈, 자바스크립트에서 주로 사용

  • 값을 캡슐화하고, 추가 기능을 더해 새로운 타입을 생성하는 구조체

  • 모나드의 개념

    • 값을 받아 한 번 더 감싼 타입

    • 순서가 있는 연산을 처리하는데 사용하는 디자인 패턴

    • 순수 함수형 프로그래밍 언어에서 부작용을 제어하기 위해서 사용

      • 부작용 : 함수가 결과값 이외에 다른 상태를 변경할 때

      함수가 전역변수, 정적 변수, 매개 변수를 수정하거나 IO작업을 수행할 때

    • Javascript같은 다중 패러다임 프로그래밍 언어에서 복잡도를 제어하기 위해서 사용함

    • Java의 Generic과 비슷한 개념

    • M[T] 로 표현 가능

      Maybe(2) ㅡ> Maybe[Number] 와 같은 꼴로 표현할 수 있음

  • 위 합성에서 예제는 쉽게 함수 합성이 이루어 질 수 있지만 만약 그렇지 않다면?

  • y = f(X * x)
z = g(X * y)
이러한 경우엔 어떻게 합성을 해야할까?

  • 이러한 경우 모나드가 필요하다. (이제부터 매우 어렵습니다....)

  • type Pure = <A>(a: A) => M<A>;
type Compose = <A, B, C>(f: (a: A) => M<B>, g: (a: B) => M<C>) => (a: A) => M<C>;

  • 어떤 타입 M 에 대해 위의 두 함수, Pure와 Compose 가 존재할 때, M은 모나드라고 한다.

  • // 제너릭 A를 갖는 어떤 타입의 Maybe는 A or null을 갖는다.
type Maybe<A> = A | null;

// 함수 pure는 제너릭 A를 갖고, A에서 value라는 이름으로 값을 하나씩 빼와서 Maybe<A>형식으로 값을 리턴해준다?????
function pure<A>(value: A): Maybe<A> {
  return value;
}

// 함수 compose는 제너릭 A, B, C를 갖고, 함수 f, g 를 인자로 가지며 A에서 a라는 이름으로 값을 하니씩 빼와서 Maybe<C>형식으로 리턴해준다...???

function compose<A, B, C>(f: (a: A) => Maybe<B>, g: (a: B) => Maybe<C>): (a: A) => Maybe<C> {
  return (a: A): Maybe<C> => {
    const ma = f(a);
  
    if (ma === null) return null;
    else g(ma);
  }
}

참고 블로그