ingo_schramm() -> tech.

Functors with Erlang

#erlang #patterns #abstraction #mathematics

epoch: 1265974860

Thinking about how useful Erlang parameterized modules might be I found a special use case I may call a Functor. Consider the following code. This presents a generic module representing a monoidal structure.

-module(monoid,[Impl]).
-export([op/2,cmp/2,get_id/0,get_member/0,is_member/1,proof/0]).

%% ------ INTERFACE -----

% apply monoid operation
op(A,B) ->
    case members([A,B]) of
        true  -> Impl:op(A,B);
        false -> undef
    end.

% compare two values if they are equal or not
cmp(A,B) ->
    case members([A,B]) of
        true  -> Impl:cmp(A,B);
        false -> undef
    end.

% get the identity or neutral element
get_id() ->
    Impl:get_id().

% get an arbitrary member element
get_member() ->
    Impl:get_member().

% test whether A is a member or not
is_member(A) ->
    case Impl:is_member(A) of
        true ->
            Impl:is_member(Impl:op(A,Impl:get_id()));
        false ->
            false
    end.

% give proof of monoid laws
proof() ->
    prove().

%% ------ PRIVATE ------

prove() ->
    I = Impl:get_id(),
    A = Impl:get_member(),
    B = A,
    Op = prove_closed(A,B),
    C = op(A,B),
    Assoc = prove_assoc(A,B,C),
    Id = prove_identity(I,A),
    neg(lists:member(false,[Op,Assoc,Id])).

prove_closed(A,B) ->
    Impl:is_member(Impl:op(A,B)).

prove_assoc(A,B,C) ->
    Impl:op(Impl:op(A,B), C) =:= Impl:op(A, Impl:op(B,C)).

prove_identity(I,A) ->
    0 =:= Impl:cmp(A,Impl:op(I,A)).

neg(true) -> false;
neg(false) -> true.

% empty set is always member
members([]) ->
    true;
members(L = [_|_]) ->
    neg(lists:member(false, [ is_member(X) || X <- L])).

Having this you can write a module implementing a concrete monoid, this time the monoid of the natural numbers under addition. In a similar fashion you could implement vector or matrix operations.

-module(nadd).
-export([op/2,cmp/2,get_id/0,get_member/0,is_member/1]).

op(A,B) ->
    A + B.

cmp(A,B) when A =/= B ->
    -1;
cmp(A,B) when A =:= B ->
    0.

get_id() ->
    0.

get_member() ->
    1.

is_member(A) when is_integer(A), A < 0 ->
    false;
is_member(A) when is_integer(A), A >= 0 ->
    true;
is_member(_A) ->
    false.

When you pass this implementation as a parameter to the generic module you can use it as in the following code.

1> M = monoid:new(nadd). 
{monoid,nadd}
2> M:proof().
true
3> M:op(1,2).
3

After reading this you may ask what these modules actually are. In terms of the Gang of Four, is the generic monoid an abstract factory? Is the implementation a strategy? Well, somehow both may be true. But exactly the “somehow” treats me to say, in fact all this is something different. It is a Functor. To put it more precisely it is the identity functor taking the monoid of the natural numbers to itself. You may check the functor laws in the shell again: 1) the functorial mapping of the identity arrow equals the identity arrow of the functorial mapping and 2) the functorial mapping of a composition of arrows equals the composition of the functorial mapping of these arrows. All this under the assumption that you treat the monoid as a category, and this is completely legal.

1> M = monoid:new(nadd).
{monoid,nadd}
2> N = monoid:new(nadd).
{monoid,nadd}
3> M:op(1,N:get_id()) == N:op(M:get_id(),1).
true
4> N:op( M:op(1,1), M:op(1,1) ) == M:op( N:op(1,1), M:op(1,1) ).
true

Sure, this is only a simple example of a Functor. In theory at least it is possible to add more structure to the generic module as well as to create more sophisticated functors. For example, you may add an inverse operation to turn the monoid into a group or you may create more complex functors with a little luck.

Monoids, Functors and similar structures appear to me the more functional variant of patterns and since Erlang is a (weak) functional language these should be patterns in Erlang as well.

permalink