所以继续摸个鱼,用 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() << ' '; } }