Computing the Histogram of a Signal as a Collection of Bins
Forward Tail Recursion in Prolog
<![CDATA[
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Computing the Histogram of a Signal as a Collection of Bins
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nicolaie Popescu-Bodorin
% http://fmi.spiruharet.ro/bodorin/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% PROLOG, TP 2.0
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% USAGE:
% rndlist(10,100,L), freq(L,HIST)
% ie: L contains 100 elements between 0 and 10 and the histogran of L is HIST
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
DOMAINS
i=integer
r=real
li=i*
lr=r*
fr=f(integer,integer)
% structured data for histogram encoding.
% f(Who,Occ) encodes the height (Occ) of the bin at a certain value (Who)
lfr=fr* % data type for the histogram (collection/list of bins)
PREDICATES
% freq(S,HIST) :: (i,o) :: Compute the histogram HIST of signal S (forward tail recursion)
freq(lr,lfr)
freq(lr,lfr,lfr)
% occno(E,L,N) :: (i,i,o) :: Count the occurences N of an element E within a list L (forward tail recursion)
occno(r,lr,r)
occno(r,lr,r,r)
% delel(E,L,R) :: (i,i,o) :: Delete the occurences of an element E within a list L (forward tail recursion)
delel(r,lr,lr)
delel(r,lr,lr,lr)
% lrev(I,O) :: (i,o) :: Reverse a list I (forward tail recursion)
lrev(lfr,lfr)
lrev(lr,lr)
lrev(lfr,lfr,lfr)
lrev(lr,lr,lr)
% rndlist(Max,N,L) :: (i,i,o) :: Generate a list L with N random integers taken between 0 and Max (backward tail recursion)
rndlist(r,i,lr)
CLAUSES
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Signal Histogram (forward tail recursion):
% freq([1,2,3,2,4,5,1,1,4],[f(1,3),f(2,2),f(3,1),f(4,2),f(5,1)])
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
freq([X],[f(X,1)]).
freq(L,R):-freq(L,[],R). % change arity in order to introduce the second parameter as Accumulator
freq([],Ri,R):-lrev(Ri,R). % the Accumulator is reversed and is fully grown when the first parameter becomes an empty list
freq([H|T],Ri,R):-
occno(H,[H|T],Occ), % count the occurences of H in [H|T];
delel(H,[H|T],La), % delete the occurences of H in [H|T];
freq(La,[f(H,Occ)|Ri],R). % forward tail recursive call;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Count the occurences of an element within a list (forward tail recursion):
% occ(Element,List,Result), (i,i,o)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
occno(E,L,R):-occno(E,L,0,R). % change arity in order to introduce the third parameter as Accumulator
occno(_,[],Ri,Ri). % the Accumulator is reversed and is fully grown when the second parameter becomes an empty list
occno(E,[E|T],Ri,R):-Ria=Ri+1,occno(E,T,Ria,R),!. % if E is found in the head of the list, count the occurence and make forward tail recursive call on the tail
occno(E,[_|T],Ri,R):-occno(E,T,Ri,R). % if E is not the head of the list (see the previous cut), make forward tail recursion call on the tail without updating the Accumulator
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Delete the occurences of an element within a list (forward tail recursion):
% delel(1,[1,2,4,3,5,1,3,1],[2,4,3,5,3]), (i,i,o)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
delel(E,L,R):-delel(E,L,[],R). % change arity in order to introduce the third parameter as Accumulator
delel(_,[],Ri,R):-lrev(Ri,R). % the Accumulator is reversed and is fully grown when the second parameter becomes an empty list
delel(E,[E|T],Ri,R):-delel(E,T,Ri,R),!. % if E equals the head of the second list, make forward tail recursion call on the tail without updating the Accumulator (E is not collected in the Accumulator)
delel(E,[H|T],Ri,R):-delel(E,T,[H|Ri],R). % if E is not H (the head of the second list), update the Accumulator by collecting H. Make forward tail recursive call on the tail and send the updated Accumulator forward.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Reverse a list (forward tail recursion):
% lrev([1,2,3],[3,2,1])
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
lrev(L,R):-lrev(L,[],R). % change arity in order to introduce the second parameter as Accumulator
lrev([],Ri,Ri). % in the most inner call, the Accumulator is "copied as" (unified with) final result
lrev([H|T],Ri,R):-lrev(T,[H|Ri],R). % forward tail recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Generate a list L with N random integers taken between 0 and Max (backward tail recursion):
% rndlist(Max,N,L)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
rndlist(_,0,[]):-!. % result in the most inner call
rndlist(Max,N,[H|T]):- % backward tail recursive call
random(Max,H),Ni=N-1,rndlist(Max,Ni,T).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% HOMEWORK ASSIGNMENT:
% The number of list traversals in the above implementation may decrease. How? What is redundant in the above approach?
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
]]>