From:
"andrew cooke" <andrew@...>
Date:
Wed, 18 Apr 2007 22:12:50 -0400 (CLT)
The following allows me to write code like this:
add(Name, Sources, Graph) ->
UniqueSources = usort(Sources),
seq_cons([curry_2(fun assert_present/2, delete(Name, UniqueSources)),
curry_2(fun add_if_necessary/2, Name),
curry_3(fun add_connections/3, Name, UniqueSources)],
Graph).
If you're a regular Erlang user you're probably crying or laughing after
reading that, but hey, it's a free world :o)
The idea is that the list of arguments to seq_cons are actions which are
invoked within a monad. Part of the monad is the Graph value, which
maintains the current description of a graph, and which is threaded
through each of the actions. The rest of the monad is a list, which
accumulates the output generated by those actions. The return type is
{List, Graph}.
Anyway, the library follows.
Andrew
% Before everything else - please forgive me if the use of monads is
% incorrect, or strained, here.
% Erlang being a pure functional language (my) code is often busy
% carrying a little ball of state around from function to function.
% It soon becomes natural to use this as the last argument(s) to
% functions and to write "sequencers" that take curried functions that
% are applied, in sequence, to the state.
% (Currying is defined in a utility library. For example,
% curry_2(Fun) -> fun(A) -> fun(B) -> Fun(A, B) end end.)
% This convention requires that each function return the state, of
% course.
% In addition it is often conventient for a function to be able to
% either abort a sequence or skip an action. Such functions could
% return fail (the state is discarded) or skip (the previous state is
% re-used).
% Here's an example from some code where the ball of state is a graph:
% seq([], Acc, Graph) -> {Acc, Graph};
% seq([Fun|Funs], Acc, Graph) ->
% case Fun(Graph) of
% fail -> fail;
% skip -> seq(Funs, Acc, Graph);
% {Results, Graph2} -> seq(Funs, Results ++ Acc, Graph2)
% end.
% seq(Funs, Graph) -> seq(Funs, [], Graph).
% In this code actions (functions) return {List, Graph} and the lists
% are appended.
% Now it seems to me that this is rather like a monad (may even, in
% some cases, *be* a monad) and that we can generalise the sequencing
% functions that are used.
% There's a subtlety here - as far as I can see, the "monad" is the
% tuple {Acc, Graph}, not the Graph alone.
% What is Acc and how does it fit into our idea of a Monad? Within
% the sequencing there are two parallel processes at work. Some of
% the state is accumulated using append, the rest is simply chained.
% This "composite Monad" pattern is fairly common - it seems to occur
% when we are constructing some "result" in the presence of a more
% persistent "kernel" of state.
% But either of the two "halves" of this "composite monad" can be
% unused, depending on the particular case. So a practical library
% will have a variety of sequencing functions (I guess there will be
% other, more complex cases, but these seem sufficiently general to
% cover a wide range of problems).
% If the graph example above seems contrived, consider this code from
% a parser combinator library. Again we have state in two pieces - a
% Stream which we consume and which is chained through various
% Parsers, and a result which is typically the recognised string or a
% list of tokens and which is accumulated separately.
% foldl(_, Acc, [], Stream) -> {match, Acc, Stream};
% foldl(Fun, Acc, [Parser|Parsers], Stream) ->
% case Parser(Stream) of
% {match, Result, Stream2} ->
% foldl(Fun, Fun(Result, Acc), Parsers, Stream2);
% {empty, Stream2} ->
% foldl(Fun, Acc, Parsers, Stream2);
% _ -> fail
% end.
% (for some obscure reason the Acc is not in the penultimate parameter
% position and the function is not really faithful to its name - it's
% a real example, from dirty code, before I had unified everything
% with this library).
% In this parser example the tagged tuple "empty" extends "skip"
% described above by returning a new Stream. This approach is
% slightly more general and we adopt it below. In other words,
% "empty" applies only to the accumulation component in the monad (the
% skip behaviour can be achieved by returning empty with the chained
% component unaltered).
% The parser example above will not be able to use this library
% directly because it does not follow the conventions used here - the
% "match" token is separate from the result. To convert to use this
% library it should either be grouped with result in a tuple, or
% simply dropped.
% The fail and empty results are an ad-hoc extension to whatever type
% is returned by the actions we are executing within the monad. This
% is trivial to do in an untyped language, but I imagine a little goes
% a long way. It's probably worth commenting that they seem similar
% to exception and the ordering (>>) operators (the bind operator
% (>>=) is implemented by the sequencing functions here).
% I hope that makes sense. Here goes...
-module(monad).
% Functions named with trailing underscores take curried functions
-export([seq/2, seq/3, seq_/3, seq/4]).
-export([seq_cons/2, rseq_cons/2, seq_app/2, rseq_app/2]).
-export([repeat/3, repeat_/3, repeat/4]).
-export([map/3, map_acc/4, map_/3, map_acc_/4, map/2, map_acc/3]).
-export([foldl/4, foldl_/4, foldl/3, foldr/4, foldr_/4, foldr/3]).
-export([lift/3, lift/1, drop/3, drop/1]).
% Simple sequencing of functions that take and return a monad.
seq([], Monad) -> Monad;
seq([Fun|Funs], Monad) ->
case Fun(Monad) of
fail -> fail;
{empty, Monad2} -> seq(Funs, Monad2);
Monad2 -> seq(Funs, Monad2)
end.
% Sequencing with two arguments - a simple composite monad where both
% components are chained (if the functions take the two in a tuple
% then you can just use seq)
seq([], Result, Kernel) -> {Result, Kernel};
seq([Fun|Funs], Result, Kernel) ->
case Fun(Result, Kernel) of
fail -> fail;
{empty, Kernel2} -> seq(Funs, Result, Kernel2);
{Result2, Kernel2} -> seq(Funs, Result2, Kernel2)
end.
% and for curried functions
seq_([], Result, Kernel) -> {Result, Kernel};
seq_([Fun|Funs], Result, Kernel) ->
case (Fun(Result))(Kernel) of
fail -> fail;
{empty, Kernel2} -> seq_(Funs, Result, Kernel2);
{Result2, Kernel2} -> seq_(Funs, Result2, Kernel2)
end.
% Alternatively, we may specify a separate function for processing the
% result component
seq(_Join, [], Result, Kernel) -> {Result, Kernel};
seq(Join, [Fun|Funs], Result, Kernel) ->
case Fun(Kernel) of
fail -> fail;
{empty, Kernel2} -> seq(Join, Funs, Result, Kernel2);
{Result2, Kernel2} ->
case Join(Result2, Result) of
fail -> fail;
skip -> seq(Join, Funs, Result, Kernel);
Result3 -> seq(Join, Funs, Result3, Kernel2)
end
end.
% Common uses of the seq functions cons or append lists
seq_cons(Funs, Kernel) -> seq(fun util:cons/2, Funs, [], Kernel).
rseq_cons(Funs, Kernel) ->
(lift(fun lists:reverse/1))(seq_cons(Funs, Kernel)).
seq_app(Funs, Kernel) -> seq(fun lists:append/2, Funs, [], Kernel).
rseq_app(Funs, Kernel) ->
(lift(fun lists:reverse/1))(seq_app(Funs, Kernel)).
% Similar to sequencing, we can repeatedly evaluate the same action
% until fail/empty.
repeat(Fun, Result, Kernel) ->
case Fun(Result, Kernel) of
fail -> {Result, Kernel};
{empty, Kernel2} -> repeat(Fun, Result, Kernel2);
{Result2, Kernel2} -> repeat(Fun, Result2, Kernel2)
end.
repeat_(Fun, Result, Kernel) ->
case ((Fun(Result))(Kernel)) of
fail -> {Result, Kernel};
{empty, Kernel2} -> repeat(Fun, Result, Kernel2);
{Result2, Kernel2} -> repeat(Fun, Result2, Kernel2)
end.
% And with a separate function for processing the result component.
% We need to be careful to fully promote join (on both arguments)
% since Result could be empty when called, I guess.
repeat(Join, Fun, Result, Kernel) ->
case {Result, Fun(Kernel)} of
{_, fail} -> {Result, Kernel};
{_, {empty, Kernel2}} -> repeat(Join, Fun, Result, Kernel2);
{empty, {Result2, Kernel2}} -> repeat(Join, Fun, Result2, Kernel2);
{_, {Result2, Kernel2}} ->
case Join(Result2, Result) of
fail -> {Result, Kernel};
skip -> repeat(Join, Fun, Result, Kernel);
Result3 -> repeat(Join, Fun, Result3, Kernel2)
end
end.
% Mapping in the presence of the monad.
% Here you can think of the accumulator as either "just an
% accumulating list" or as a separate part of a larger monad that also
% includes a "kernel", as above (a list is a monad, so what we have
% here is a composite monad - it's all consistent in a hand-waving
% way).
map_acc(_Fun, [], Result, Kernel) -> {Result, Kernel};
map_acc(Fun, [Head|Tail], Result, Kernel) ->
case Fun(Head, Kernel) of
fail -> fail;
{empty, Kernel2} -> map_acc(Fun, Tail, Result, Kernel2);
{Result2, Kernel2} -> map_acc(Fun, Tail, [Result2|Result], Kernel2)
end.
map(Fun, List, Kernel) ->
case map_acc(Fun, List, [], Kernel) of
fail -> fail;
{empty, Kernel2} -> {empty, Kernel2};
{List2, Kernel2} -> {lists:reverse(List2), Kernel2}
end.
% and for curried functions
map_acc_(_Fun, [], Result, Kernel) -> {Result, Kernel};
map_acc_(Fun, [Head|Tail], Result, Kernel) ->
case (Fun(Head))(Kernel) of
fail -> fail;
{empty, Kernel2} -> map_acc_(Fun, Tail, Result, Kernel2);
{Result2, Kernel2} -> map_acc_(Fun, Tail, [Result2|Result], Kernel2)
end.
map_(Fun, List, Kernel) ->
case map_acc_(Fun, List, [], Kernel) of
fail -> fail;
{empty, Kernel2} -> {empty, Kernel2};
{List2, Kernel2} -> {lists:reverse(List2), Kernel2}
end.
% Folding can be defined too.
foldl(_Fun, [], Result, Kernel) -> {Result, Kernel};
foldl(Fun, [Head|Tail], Result, Kernel) ->
case Fun(Head, Result, Kernel) of
fail -> fail;
{empty, Kernel2} -> foldl(Fun, Tail, Result, Kernel2);
{Result2, Kernel2} -> foldl(Fun, Tail, Result2, Kernel2)
end.
foldl_(_Fun, [], Result, Kernel) -> {Result, Kernel};
foldl_(Fun, [Head|Tail], Result, Kernel) ->
case ((Fun(Head))(Result))(Kernel) of
fail -> fail;
{empty, Kernel2} -> foldl_(Fun, Tail, Result, Kernel2);
{Result2, Kernel2} -> foldl_(Fun, Tail, Result2, Kernel2)
end.
% I can't find a sensible meaning for empty/skip here
foldr(_Fun, [], Result, Kernel) -> {Result, Kernel};
foldr(Fun, [Head|Tail], Result, Kernel) ->
case foldr(Fun, Tail, Result, Kernel) of
fail -> fail;
{Result2, Kernel2} -> Fun(Head, Result2, Kernel2)
end.
foldr_(_Fun, [], Result, Kernel) -> {Result, Kernel};
foldr_(Fun, [Head|Tail], Result, Kernel) ->
case foldr(Fun, Tail, Result, Kernel) of
fail -> fail;
{Result2, Kernel2} -> ((Fun(Head))(Result2))(Kernel2)
end.
% As mentioned in the introduction, we can also drop the chained part
% of the state completely. In that case we have the list monad, with
% the fail and empty extensions.
% Without a chained component we revert back to skip rather than empty.
map_acc(_Fun, [], Result) -> Result;
map_acc(Fun, [Head|Tail], Result) ->
case Fun(Head) of
fail -> fail;
skip -> map_acc(Fun, Tail, Result);
Other -> map_acc(Fun, Tail, [Other|Result])
end.
map(Fun, List) ->
case map_acc(Fun, List, []) of
fail -> fail;
skip -> skip;
List2 -> lists:reverse(List2)
end.
foldl(_Fun, [], Result) -> Result;
foldl(Fun, [Head|Tail], Result) ->
case Fun(Head, Result) of
fail -> fail;
skip -> foldl(Fun, Tail, Result);
Other -> foldl(Fun, Tail, [Other|Result])
end.
% Again, I can't find a sensible meaning for empty/skip here
foldr(_Fun, [], Result) -> Result;
foldr(Fun, [Head|Tail], Result) ->
case foldr(Fun, Tail, Result) of
fail -> fail;
Other -> Fun(Head, Other)
end.
% Sometimes you may want to lift functions to work inside the monad even
% though they don't use the kernel.
lift(Fun, Empty, Fail) ->
fun(Tuple) ->
case Tuple of
fail -> Fail;
{empty, Kernel} -> {Empty, Kernel};
{Result, Kernel} -> {Fun(Result), Kernel}
end
end.
lift(Fun) -> lift(Fun, empty, fail).
drop(_Empty, Fail, fail) -> Fail;
drop(Empty, _Fail, {empty, _Kernel}) -> Empty;
drop(_Empty, _Fail, {Result, _Kernel}) -> Result.
drop(Value) -> drop(empty, fail, Value).