Prova Developers Blog

Continuing on this drive to map the functional programming concepts to Prova. To open a little bracket here first, it is quite obvious that Erlang and Prova messaging look pretty close. I'll explore this subject later in more detail but it will suffice for now to note that Erlang obviously lacks logic programming elements. Let's see for now how some pretty cool elements of functional programming can be expressed in new Prova. I hope to demonstrate eventually how logic and functional programming as well as agents/workflows/events could be nicely integrated.

This is a new test func_003.prova that solves the challenge of cleanly implementing the bind operation on list monads. No general monads support is there yet but you'll see, it's getting there. All but the last example in this test are borrowed from the Haskell cookbook but look slightly different (and even better, in some cases): http://www.haskell.org/haskellwiki/Monads_as_containers.

% Demonstrate
%    concat function on lists,
%    concrete monadic bind defined as concat(map f m) on lists,
%    using partial application for map.

% The three goals below return X=[[1,1,2,2,3,3]]
:- solve(concat([[1,1],[2,2],[3,3]],X)).

:- solve(
	derive(
		[[concat,map],[duplicate,[1,2,3]],X]
	)
).

% in Haskell, [1,2,3] =>> duplicate
:- solve(
	derive(
		[[concat,map(duplicate)],[[1,2,3]],X]
	)
).

% let's show how bind allows us to do it more than once: % [1,2,3] =>> duplicate =>> duplicate
%    this returns X=[[1,1,1,1,2,2,2,2,3,3,3,3]]
:- solve(
	derive(
		[[concat,map(duplicate),concat,map(duplicate)],[[1,2,3]],X]
	)
).

% good fun with fractals: ['#'] =>> f =>> f =>> f =>> f 
:- solve(
	derive(
		[[concat,map(f),concat,map(f),concat,map(f),concat,map(f)],[['#']],X]
	)
).

% Let's see how to execute binary operations on list monads.
% The first map operates on a lifting function a->Mb (that creates a list),
%    the second map operates on raw function a->b.
% This is equivalent to: [1,2,3] =>> (\x -> map add(x) [1,2])
% mapflip (not map) is needed as we have to flip the arguments to this map 
% The goal returns: X=[[2,3,3,4,4,5]]
:- solve(
	derive(
		[[concat,map([mapflip(add,[1,2])])],[[1,2,3]],X]
	)
).

% example of an a->Mb function 
duplicate(X,[X,X]).

% a fractal a->Mb
f('#',['#',' ','#']) :- !.
f(_,[' ',' ',' ']).

% map is an example of an fmap: a->b->Ma->Mb
map([_,[]],[]).
map([Fun,[A|As]],[B|Bs]) :-
	derive(Fun(A,B)),
	map([Fun,As],Bs).

% concat is an example of join: M(Ma)->Ma 
concat([],[[]]).
concat([[]|As],R) :-
	concat(As,R).
concat([[X|Xs]|As],[[X|Rs]]) :-
	concat([Xs|As],[Rs]).

mapflip([Fun,M,X],R) :-
	map([[Fun(X)],M],R).

add([A,B],Z) :-
	Z=A+B.

The code is quite well documented so let's just discuss the general idea. Monadic bind is essentially a way to take a wrapped data (for example, a list of numbers) and ship the raw data (numbers) from it to a computation that takes a raw number and creates a wrapped data again (a list). The bind operation can be nicely represented as concat . map(f), where '.' is function composition. f is that 'lifting' function that works on individual list elements and produces a list. However, since we map this function on a list, we end up with a list of lists, in monadic terms it is a function Ma->M(Ma). What we want to get, however, is just a list, wrapping the elements only once, so we take a 'join' function (in this case, concat) that takes M(Ma) and produces an Ma, that is a list, for example, concat([[1,2],[3,4]])->[1,2,3,4].

The trickiest example is the last one, in which a binary operation on list monads is defined. Basically, we have a list L as input, and we ship it to a function that maps an add function plus each of L elements X, add(X) curryied to apply to another list. We end up getting a list of lists once again so concat flattens the result again.