U.Seung's Log

이전에 C#으로 SICP에 나온 Infinite Streams을 구현 해본적이 있는데
이번에는 C++로 구현 해보았습니다. 실제로 이런 Lazy한 기법들이 사용될 곳이 있을지는 생각을 더 해봐야 겠지만 일단은 공부 한다는 차원에서 .... 해볼만한 것 같습니다.


만든 Infinite를 사용하는 main코드는 아래와 같은 모양으로 생겼습니다.
(wcout를 쓰기 위해서 그냥 tchar를 사용하지 않았습니다.)

bool isEven(int i) { return (i%2 == 0); }

int wmain(int argc, wchar_t* argv[])

{

    fibs()->filter(isEven)->take(10)->out(std::wcout);

    return 0;

}

눈치가 빠르신 분들은 벌써 아셨겠지만 코드는...
피보나치수열(fibs)를 얻어서, 이 중 짝수만 걸러내서(filter) 그 중에서 제일 앞에 10개만(take) 출력(out)하겠다는 코드 입니다. 물론 C++에서 저렇게 exception처리도 없이 ->연산자를 중복해서 사용하는 것은 좋지 않지만 실제로 사용하는 코드가 아니니 이해해 주시기 바랍니다.

아무튼 그래서 피보나치 수열 중에서 짝수 중 앞에 10개는 아래와 같습니다.
위 코드가 아래와 같은 결과를 나오게 만들면 되겠지요?
시간 있으신 분들은 제가 한 방법 말고 다른 방법으로 구현 해보셔도 재미있을 것 같네요 ^^

2
8
34
144
610
2584
10946
46368
196418
832040

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
소스보기 :

istream.cpp

class fibo_stream : public make_stream<int>

{

public:

    fibo_stream()

        : make_stream<int>(1, 1)

    {}

    virtual IStream<int>* _tail()

    {

        IStream<int>* super_tail = make_stream<int>::_tail();

        return new fibo_stream(super_tail->head(),

                                  head()+super_tail->head());

    }

protected:

    fibo_stream(int head, int tail)

        : make_stream<int>(head, tail)

    {}

};

IStream<int>* fibs() { return new fibo_stream(); }

피보나치 수열 스트림의 포인트는 항상 두개의 값만 계산해 놓는다는 겁니다. 즉, 미리 앞서나가지 않는 것 입니다.


덧)
아래 wafe님의 지적을 받아서 표준이 아닌 문법을 고쳐서 g++에서도 컴파일 될 수 있도록 했습니다.

얼마전에 C# 3.0으로 만든 QuickSort를 포스팅한 이후로도 C#에 대한 생각을 평소 많이 하고 있다.
다만 C#을 Main 언어로 코딩한다면 좋겠지만 아직은 C++을 많이 쓰는 상황이라서 아쉬움이 많다.

C#의 새로운 Functional Feature들을 보면서 떠오르는 것은 단연 SICP였다.

static bool IsEven(this int num)

{

    return (num == 0) ? true : IsOdd(num - 1);

}

static bool IsOdd(this int num)

{

    return (num == 0) ? false : IsEven(num - 1);

}

public static bool IsPrime(this int num)

{

    Func<int, int> FindSmallestDivisor = divisor =>

    {

        if (divisor * divisor > num) return num;

        if (num % divisor == 0) return divisor;

        return FindSmallestDivisor(divisor+1);

    };

    return (FindSmallestDivisor(2) == num);

}

#3. 무한대 수열 다루기 - 자연수 만들기

LISP

static IEnumerable<T> ConsStream<T>(this T t, IEnumerable<T> ts)

{

    yield return t;

    foreach (var nextT in ts)

        yield return nextT;

}

static

IEnumerable<int> IntegerStrartingFrom(int num)

{

    foreach (var item in 
        num.ConsStream(IntegerStrartingFrom(num + 1)))

        yield return item;

}

static IEnumerable<int> Numbers()

{

    return IntegerStrartingFrom(1);

}

static IEnumerable<int> Primes()

{

    return Numbers().Where(n => n.IsPrime());

}

static IEnumerable<int> Fibs()

{

    foreach (var item in

        ConsStream(1,
        ConsStream(1, Fibs().Plus(Fibs().Tails()))))

        yield return item;

}

 

public static IEnumerable<int> Plus(this IEnumerable<int> ts1, IEnumerable<int> ts2)

{

    return ts1.Map(ts2, (t1, t2) => t1 + t2);

}

 

public static IEnumerable<T> Map<T>(this IEnumerable<T> ts1, IEnumerable<T> ts2, Func<T, T, T> Proc)

{

    foreach (var item in 
        Proc(ts1.Head(), ts2.Head())
        .ConsStream(Map(ts1.Tails(), ts2.Tails(), Proc)))

        yield return item;

}

#5. 공유 변수 - Counter 만들기

public static Func<int> MakeCounter(int initialNumber)
{
    return () => (++initialNumber);
}

static void Main(string[] args)
{
    Func<int> Counter = MakeCounter(10);
    Counter();
    Counter();
    Debug.WriteLine(Counter());
}

우리 학교 전산학과 2학년에 Scheme을 배우는 과목이 있다. Scheme은 Functional Programming을 지원하는 언어로 우리가 주로 사용하는 C, JAVA 등의 Procedural programming과 또 다른 세계를 보여준다. 오늘은 비슷한 결과를 낼 수 있는 Javascript로 Scheme 스타일을 좀 따라해봤다.

이 둘 사이에는 여러가지 차이가 있는데 가장 큰 차이는 Functional Language가 Referential transparency를 제공한다는 점에 있다. 자세한 사항을 알아서 찾아보시고;;;

일단 예제 코드를 보자.