Prova Developers Blog

The new Subversion and binary distribution updates have a few simple additions that make writing functional programs far easier with Prova, including functions, function composition, currying, and typical high-order constructs like map, filter, or foldr.

By convention, functions are represented as arity 2 predicates with the first argument representing the input parameters and the second argument, a result. If there is more than one argument, they are passed as a list. If the result is complex, it is returned as a list. For example, these are some basic functions from the test func_001.prova:

double(X,XM) :-
   XM=2*X.
% Wrap in a list (e.g., as required by the second map argument)
list(X,[X]).
duplicate(X,[X,X]).
add([A,B],Z) :-
   Z=A+B.
add3([A,B,C],Z) :-
   Z1=A+B,
   Z=Z1+C.
divide([A,B],Z) :-
   Z=A/B.
max([X,Y],X) :-
   X>=Y,
   !.
max([X,Y],Y).

Now let's define the function map that is probably the best known combinator function.

map([_,[]],[]).
map([Fun,[A|As]],[B|Bs]) :-
   derive(Fun(A,B)),
   map([Fun,As],Bs).

Note that map is also a function as all other functions above so it can be used anywere we want provided the signatures match. Time to run some goals:

%%% map double to a list of numbers: X*2
:- solve(map([double,[1,2,3,4,5]],L)).
%%% map a function composition: +[X,X]
:- solve(map([[add,duplicate],[1,2,3,4,5]],L)).
%%% map a function composition of reduced functions: add 1 twice to each number
:- solve(map([[add(1),add(1)],[1,2,3,4,5]],L)).
%%% shows that composition is ordered right-to-left: (X*2*2+2)*2
:- solve(map([[double,add(2),double,double],[1,2,3,4,5]],L)).
%%% shows how compound result provides remaining two argument to add3: X*2+X*2+10
:- solve(map([[add3(10),duplicate,double],[1,2,3,4,5]],L)).
%%% shows how compound result must be adapted to the required type (second argument to map is a list: [X*2,X*2]*2
:- solve(map([[map(double),list,duplicate,double],[1,2,3,4,5]],L)).

The key to all of this working is a revised derive/1 builtin predicate. It now accepts a list of composed functions (they work right-to-left!) that are possibly partially applied by currying. For example, when "add(2)" is passed in the list of functions, 2 is substituted as the first argument to add and the second operand is taken from the result of the function immediately to the right or from the original argument, if there is none. Another example above uses add3(10) based on add3/3 to add the two numbers coming from the result of the function on the right (duplicate) to return the sum of these three numbers. Last but not least, note how partially applied map(double) is used inside map. Be careful, there is a subtlety there. When duplicate creates two numbers they are by default flattened together with double passed as the first argument to that inner map. This is not what we want, we need these numbers to be wrapped in a list and then passed as one second argument to map. The function "list" does that wrapping.

Finally, before we go, here are useful foldr and foldl implementations

foldr([_,X,[]],X).
foldr([Fun,X,[A|As]],Z) :-
   foldr([Fun,X,As],Z1),
   derive(Fun([A,Z1],Z)).
foldl([_,X,[]],X).
foldl([Fun,X,[A|As]],Z) :-
   derive(Fun([X,A],Z1)),
   foldl([Fun,Z1,As],Z).

with some goals:

%%% use foldr to add all numbers to the seed 5: 1+2+3+4+5 + 5
:- solve(foldr([add,5,[1,2,3,4,5]],X)).
%%% use foldr to find the maximum of seed 4 and all elements: max(1,2,3,4,5,4)=5
:- solve(foldr([max,4,[1,2,3,4,5]],X)).
%%% use foldl to divide the seed 64 by all list elements: 64/4/2/4=2.0
:- solve(foldl([divide,64,[4,2,4]],X)).

Obviously, function compositions can be used in place of simple functions under foldr/foldl.