Реализация генератора чисел Фиббоначи

test.erl

%%% @file test.erl Реализация генератора чисел Фиббоначи.
%%% Результатом работы генератора должна
%%% быть пара {очередное_число, генератор_следующего_числа}.
%%% 
%%% Для ускорения счета используется классическая рекурсивная мемоизация.
%%% Она Реализована через оператор неподвижной точки.
%%% Крайне эффективна для рекурсивных функций.
%%%
%%% Можно реализовать и простую мемоизацию для данного примера.
%%% Будем запоминать только последний вариант чисел фиббоначи,
%%% но в общем случае для чисел Фиббоначи она не будет такой быстрой.
%%%
%%% Иные, более простые варинты мемоизации моего авторства можно найти на 
%%%         https://gist.github.com/2875038
%%%
%%%     generator/0 --- Функция, которая реазована по заданию
%%%     generator/1 --- Основная рабочая функция generator/0
%%%         Примечание: test:generator(10000), выдает результат мгновенно.
%%%

-module(test).

-export([
    generator/0, % Искомая функция по заданию.
    generator/1, % Основная рабочая функция generator/0
    test/0       % Функция для тестирования.
]).

%%%
%%% @doc
%%%     Тестовая функция для проверки
%%%
test()->
    Start = fun generator/0,
    lists:foldl(
        fun(I,F) ->
            {N,F1} = F(),
            io:format("~p: ~p~n", [I, N]),
            F1
        end,
        Start,
        lists:seq(1, 100)
    ).

%%%
%%% @doc
%%%     Возвращает пару {очередное_число, генератор_следующего_числа}.
%%%     Генератор чисел Фибоначчи.
%%%     Искомая функция по заданию.
%%%
generator()->
    generator(1).


%%%
%%% @doc
%%%     Возвращает пару {очередное_число, генератор_следующего_числа}.
%%%     На вход подается порядковый номер числа.
%%%     Основная рабочая часть функции generator/0
%%%
generator(N) ->
    Rfun = rmemoize(fun fibimpl/1),
    {Rfun(N), fun()-> generator(N+1) end}.

%%%
%%% @doc
%%%     Возвращает функцию реализующую числа Фиббоначи по определению.
%%%
fibimpl(Self) ->
    fun
        (0) -> 1;
        (1) -> 1;
        (N) when N > 1 ->
            ((Self)(N - 1)) + ((Self)(N - 2))
    end. 


%%% ------------------------------------------------------------------------
%%% Ниже описана.
%%%
%%% Классическая рекурсивная мемоизация
%%% Реализована через оператор неподвижной точки.
%%% Крайне эффективна для рекурсивных функций.
%%% 
%%% Можно реализовать и простую мемоизацию для данного примера.
%%% Будем запоминать только последний вариант чисел фиббоначи,
%%% но в общем случае для чисел Фиббоначи она не будет такой быстрой.
%%% 
%%% ------------------------------------------------------------------------

%%%
%%% @doc
%%%     Оператор неподвижной точки
%%%     Следует из определения рекурсии в λ-исчислении.
%%%
ry(Function) when erlang:is_function(Function, 1) ->
    Function(
        fun(X) ->
            (ry(Function))(X)
        end
    ).

%%%
%%% @doc
%%%     Вычисляет рекурсивную функцию.
%%%     Запоминает промежуточные результаты.
%%%     И при необходимости достает их из памяти.
%%%
rmemoize(Tab, Function) when erlang:is_function(Function, 1) ->
    fun (B) ->
        Bfunction = Function(B),
        fun (Args) ->
            Hash = funhash(Bfunction, Args),
            case get_value(Tab, Hash) of
                undefined ->
                    Result = Bfunction(Args),
                    put_value(Tab, Hash, Result),
                    Result;
                Result ->
                    Result
            end
        end
    end.

%%%
%%% @doc
%%%     Вычисляет рекурсивную функцию.
%%%     Удаляет промежуточные результаты.
%%%     Запоминает последний результат.
%%%
%%%     ВАЖНО:
%%%         Function = fun( fun(Arg) ) -> fun(Arg)
%%%     Или в стиле Ocaml:
%%%         (fun (fun -> Arg ) -> (fun -> Arg)
%%%
rmemoize(Function) when erlang:is_function(Function, 1) ->
    fun (Args) ->
        Anstab = storage_new(memo_rmemoize_ans),
        Hash = funhash(Function, Args),
        case get_value(Anstab, Hash) of
            undefined ->
                Tmptab = storage_new(memo_rmemoize_tmp),
                Mfunction = rmemoize(Tmptab, Function),
                Yfunction = ry(Mfunction),
                Ans = Yfunction(Args),
                delete_storage(Tmptab),
                put_value(Anstab, Hash, Ans),
                Ans;
            Result ->
                Result
        end
    end.

%%%
%%% @doc
%%%     Создает новое хранилище (ets в данном случае)
%%%
storage_new(Name) ->
    case ets:info(Name) of
        undefined ->
            %ets:new(Name, [set, public, named_table]);
            ets:new(Name, [set]);
        _         ->
            Name
    end.

%%%
%%% @doc
%%%     Удаляет хранилище (ets в данном случае)
%%%
delete_storage(Tab) ->
    ets:delete(Tab).

%%%
%%% @doc
%%%     Берет значение по ключу Key в хранилище Tab
%%%
get_value(Tab, Key) ->
    case ets:lookup(Tab, Key) of
        [{Key, Value}] ->
            Value;
        [] ->
            undefined
    end.

%%%
%%% @doc
%%%     Кладет значение по ключу Key в хранилище Tab
%%%
put_value(Tab, Key, Value) ->
    case ets:insert(Tab, {Key, Value}) of
        true ->
            true;
        Else ->
            Else
    end.

%%%
%%% @doc
%%%     Вычисляет хеш для функции и аргументов.
%%%
funhash(Fun, Args) ->
    {module, Module}    = erlang:fun_info(Fun, module),
    {name, Name}        = erlang:fun_info(Fun, name),
    {arity, Arity}      = erlang:fun_info(Fun, arity),
    {Module, Name, Arity, Args}.