Read some introductions to theory of categories (a very good introduction to the theory, or this one more programmer oriented). As I also stumble upon this thread, I discover a new concept: “hylomorphism is a composite of an anamorphism (unfold) and an catamorphism (fold/inject) [1], [2]“, along with a ruby code to implement it in some way (this the googlegroup thread above).

Just for fun (and be sure to understand it), I translated the code in Erlang. I’ve used the property list module to implement some kind of default value, but it’s not really elegant. Anyway, code is here.

-module(hylo).
-export([
    % hylomorphism API
    new/1,
    % examples/toys
    evens/1,
    fact/1,
    to_bin/1,
    expand/1
]).

% internal declarations

-record(hylo, {
    do,
    till,
    collecting,
    injecting
}).

% API

new(PL) when is_list(PL) ->
    H = #hylo{
        do = proplists:get_value(
            do,
            PL,
            fun(X) -> X + 1 end
        ),
        till = proplists:get_value(
            till,
            PL,
            fun(X) -> X =:= undefined end
        ),
        collecting = proplists:get_value(
            collecting,
            PL,
            fun(X) -> X end
        ),
        injecting = proplists:get_value(
            injecting,
            PL,
            {   [],
                fun(A,E) -> [E|A] end,
                fun lists:reverse/1
            }
        )
    },
    fun(S) -> eval(H, S, element(1,H#hylo.injecting)) end.

% internal implementation

eval(H, S1, R) ->
    {_, InjF, InjR} = H#hylo.injecting,
    case (H#hylo.till)(S1) of
        false ->
            V = (H#hylo.collecting)(S1),
            S2 = (H#hylo.do)(S1),
            eval(H, S2, InjF(R, V));
        _ ->
            InjR(R)
    end.

% examples

evens(N) ->
    H = new([
        {do, fun(X) -> X + 2 end},
        {till, fun(X) -> X >= N end}
    ]),
    H(0).

fact(N) when N > 0 ->
    H = new([
        {do, fun(X) -> X - 1 end},
        {till, fun(X) -> X =< 1 end},
        {injecting, {1, fun(A,E) -> A * E end, fun(A) -> A end}}
    ]),
    H(N).

to_bin(N) when N > 0 ->
    H = new([
        {do, fun(X) -> X div 2 end},
        {till, fun(X) -> X =< 0 end},
        {collecting, fun(X) -> (X rem 2) end},
        {injecting, {[], fun(A,E) -> [E|A] end, fun(A) -> A end}}
    ]),
    H(N).

expand(L) ->
    H = new([
        {do, fun ([_|T]) -> T; ([]) -> [] end},
        {till, fun ([]) -> true; (_) -> false end},
        {collecting, fun([{C,N}|_]) -> lists:duplicate(N, C) end}
    ]),
    H(L).

-ifdef(EUNIT).
-include_lib("eunit/include/eunit.hrl").

evens_test() ->
    ?assert(evens(10) =:= [0,2,4,6,8]).

fact_test() ->
    ?assert(fact(5) =:= 120).

to_bin_test() ->
    ?assert(to_bin(10) =:= [1,0,1,0]).

expand_test() ->
    ?assert(expand([{$a,2},{$b,3},{$c,4}]) =:= ["aa", "bbb", "cccc"]).

-endif.
Advertisements