Just for fun: Compile time fibonacci

所以继续摸个鱼,用 C++ 模版编程写个 fibonacci 计算

当然一开始只是顺手玩玩了,因为 C++ 这里的模版匹配其实挺像函数式编程的(似乎还有人曾用 C++ 的模版匹配来做过 SAT solver 的样子)

先把 C++ 编译时的放在下面,一会儿再补一个正经函数式编程的代码,然后再加一个更优雅的函数式实现(Elixir),最后用 Python 和 C++ 再模仿一下函数式的吧~

#include <iostream>

/**
 fibonacci(n)
 */
template <std::size_t n>
struct fib {
    static constexpr uint64_t cal() {
        return fib<n - 1>::cal() + fib<n - 2>::cal();
    }
};

/**  base case, fibonacci(0)  */ template<> struct fib<0> { static constexpr uint64_t cal() {         return 0; } }; /**  base case, fibonacci(1)  */ template<> struct fib<1> { static constexpr uint64_t cal() {         return 1; } }; int main(int argc, const char * argv[]) { std::cout << fib<10>::cal() << std::endl; }

函数式编程的话,就选 Elixir 好了,先是一个不那么优雅的版本

defmodule Fib do
  def fib(0) do
    0
  end

  def fib(1) do
    1
  end

  def fib(n) do
    fib(n - 1) + fib(n - 2)
  end
end

更为优雅的写法则是

Stream.unfold({0, 1}, fn {f1, f2} -> {f1, {f2, f1+f2}} end)
  |> Enum.take(10)

那既然都写到 generator 了,就顺便写个 python 的

def unfold(state, func):
    while True:
        stream_value, state = func(state)
        yield stream_value

def fib(state):
    f1, f2 = state
    return [f1, [f2, f1 + f2]]

p = unfold([0, 1], fib)

print([next(p) for i in range(10)])

不过都写到这里了,就让 C++ 的再更好玩更有用一些吧,用 C++ 写个 unfold,并且模仿一下 Elixir 的 Stream 或者 Python 的 Generator

#include <array>
#include <functional>
#include <iostream>
#include <tuple>

/**
 unfold

 @param state current state
 @param func  a function that accepts current state and produces {yield_value, new_state}
 @return generator
 */
template<typename Y, typename S>
auto unfold(S state, std::function<std::tuple<Y, S>(S current_state)> func) {
    // save current state
    std::array<int, 2> _state = state;
    // return a function as generator
    return [=]() mutable {
        // declaration
        Y yield_value;
        S new_state;

        // receive {yield_value, new_state} from current state
        std::tie(yield_value, new_state) = func(_state);

        // save new state
        _state = new_state;

        // yield value corresponding to previous state
        return yield_value;
    };
}

int main(int argc, const char * argv[]) {
    // fibonacci starting state
    std::array<int, 2> state{{0, 1}};

    auto&& fib = unfold<int, decltype(state)>(state, [](auto current_state) {
        // fib(n) = fib(n - 1) + fib(n - 2)
        // i.e. the value which would be yield
        int value = current_state[0] + current_state[1];

        // new state from {fib(n - 1), fib(n - 2)} is
        // {fib(n - 2), fib(n - 1) + ib(n - 2)}
        // i.e. {current_state[1], value}
        return std::tuple<int, decltype(current_state)>(value, {current_state[1], value});
    });

    for (int i = 0; i < 10; i++) {
        std::cout << fib() << ' ';
    }
}
声明: 本文为0xBBC原创, 转载注明出处喵~

Leave a Reply

Your email address will not be published. Required fields are marked *