List Processing in Prolog
Backward Tail Recursion in Prolog / Forward Tail Recursion in Prolog
<![CDATA[
%%%%%%% lstdp.pro :: TP2.0 %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% INCLUDE THIS FILE IF YOU WANT TO USE (ANY OF) THE FOLLOWING PREDICATES:
% 1.% lconcat (list,list,list), (i,i,o) % concatenate two lists
% 2.% lcount (list,real), (i,o), % count the list
% 3.% lsum (list,real), (i,o), % make sum
% 4.% singleton (list), (i), % is singleton?
% 5.% singleton (list,element), (i,i), % is singleton of ... ?
% 6.% lrev(list,list), (i,o), % reverse list
% 7.% plndrm(list), (i), % is palindrom?
% 8.% ismof(element,list), (i,i),(o,i), % is member of ?
% 9.% mknl(int,list), (i,o), % mknl(3,[1,2,3])
% 10. % mklel(int,list_of_empty_lists), (i,o), % mklel(3,[ [],[],[] ])
% 11. % mklxl(realx,int,llr), (i,i,o), % mklxl(0, 3, [ [0],[0],[0] ])
% 12. % maxlr(list,element), (i,o), % max element from a list
% 13. % minlr(list,element), (i,o), % min element from a list
% 14. % scalarp(lr,lr,real), (i,i,,o), % scalar product of two vectors
% 15. % sortins(inputlist,sortedlist), % Insertion sort
% 16. % addrealtolr(real,list,list), (i,i,o) % addrealtolr(3,[1,7,3],[4,10,6])
% 17. % lprod(list,result), (i,o) % lprod([6,3],18=6*3)
% 18. % pow(base,expo,result), (i,i,o) % pow(2,3,8)
% 19. % bitreversal(startindex, k, 1:N, Butterfly permutation)
% 20. % delfromlist(what, fromthislist) %
% 21. % ldeflate(list, set) % transform a list into a set
% 22. % rle(list, who, occ) % Run-Length Encoding
% 23. % rle(list, who, occ) % Run-Length Decoding
% WHERE: "list" could be a list of integers/reals/strings/chars/symbols,
% or a list of lists of integers/reals/strings/chars/symbols,
% according to the defined operation.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nicolaie Popescu-Bodorin, 2009,
% http://fmi.spiruharet.ro/bodorin/
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
DOMAINS
i=integer
r=real
s=string;
sym=symbol
c=char
li=i*
lli=li*
lr=r*
llr=lr*
lc=c*
llc=lc*
ls=s*
lls=ls*
lsym=sym*
llsym=lsym*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Concatenate two lists (backward tail recursion):
PREDICATES
lconcat(lr,lr,lr)
lconcat(llr,llr,llr)
lconcat(lc,lc,lc)
lconcat(llc,llc,llc)
lconcat(ls,ls,ls)
lconcat(lls,lls,lls)
lconcat(lsym,lsym,lsym)
lconcat(llsym,llsym,llsym)
CLAUSES
% Concatenate two lists (backward tail recursion):
% lconcat(i,i,o)
lconcat([],L,L). % the most inner call;
lconcat([H|T],List,[H|TR]):-lconcat(T,List,TR).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Count the list (forward tail recursion):
PREDICATES
lcount(lr,r)
lcount(ls,r)
lcount(lc,r)
lcount(lsym,r)
lcount(llr,r)
lcount(lls,r)
lcount(llc,r)
lcount(lr,r,r)
lcount(ls,r,r)
lcount(lc,r,r)
lcount(lsym,r,r)
lcount(llr,r,r)
lcount(lls,r,r)
lcount(llc,r,r)
CLAUSES
% Count the list (forward tail recursion):
lcount(L,R):-lcount(L,0,R). % change arity in order to introduce the second parameter as Accumulator
lcount([],Ri,Ri):-!. % in the most inner call, the Accumulator is "copied as" (unified with) final result
lcount([_|T],Ri,R):-Ria=Ri+1,lcount(T,Ria,R). % while the input list is non empty, the Accumulator is updated and it is sent forward in the next call (forward tail recursive call)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Sum the elements of an array (forward tail recursion):
PREDICATES
lsum(lr,r)
lsum(lr, r,r)
CLAUSES
% Sum the elements of a list (forward tail recursion):
lsum([X],X):-!. %
lsum(L,R):-lsum(L,0,R). % change arity in order to introduce the second parameter as Accumulator
lsum([],Ri,Ri). % in the most inner call, the Accumulator is "copied as" (unified with) final result
lsum([H|T],Ri,R):-Ria=Ri+H,lsum(T,Ria,R). % while the input list is non empty, the Accumulator is updated and it is sent forward in the next call (forward tail recursive call)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Test if the input list is a singletone of the input element (bacward tail recursion)
PREDICATES
singleton(lr)
singleton(ls)
singleton(lc)
singleton(lsym)
singleton(li)
singleton(llr)
singleton(lls)
singleton(llc)
singleton(llsym)
singleton(lli)
singleton(lr,r)
singleton(ls,s)
singleton(lc,c)
singleton(lsym,sym)
singleton(li,i)
singleton(llr,lr)
singleton(lls,ls)
singleton(llc,lc)
singleton(llsym,lsym)
singleton(lli,li)
% USAGE:
% singleton(InputList,InputElement) :: Test if the input list is a singletone of the input element
% singleton(InputList,OutputElement) :: Test if the input list is a singletone of its head element. If YES, the output is the head of the list.
% singleton([_,_,_],X) :: will return Yes if X is Bounded.
% lcount(L,3), singleton(L,5) :: will return L=[5,5,5].
% singleton([_,X,_],Y) :: Unify X with Y if X id Bounded.
% finall(X,singleton([1,2,3],X),Y) :: will return Y=[];
CLAUSES
% Test if the input list is a singletone of the input element (bacward tail recursion):
singleton([H|T]):-singleton([H|T],H). % change arity in order to see if the head of the list equals all of its components
singleton([X],X):-!. % the most inner call;
singleton([R|T],R):-singleton(T,R). % if initial head equals current head, make the backward tail recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Reverse a list (forward tail recursion):
PREDICATES
lrev(lr,lr)
lrev(lc,lc)
lrev(ls,ls)
lrev(li,li)
lrev(lsym,lsym)
lrev(llr,llr)
lrev(llc,llc)
lrev(lls,lls)
lrev(lli,lli)
lrev(llsym,llsym)
lrev(lr,lr,lr)
lrev(lc,lc,lc)
lrev(ls,ls,ls)
lrev(li,li,li)
lrev(lsym,lsym,lsym)
lrev(llr,llr,llr)
lrev(llc,llc,llc)
lrev(lls,lls,lls)
lrev(lli,lli,lli)
lrev(llsym,llsym,llsym)
CLAUSES
% Reverse a list (forward tail recursion):
% lrev(i,o)
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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Test if the input list is a palindrome:
PREDICATES
plndr(lr)
plndr(lc)
plndr(ls)
plndr(li)
plndr(lsym)
plndr(llr)
plndr(llc)
plndr(lls)
plndr(lli)
plndr(llsym)
CLAUSES
% Test if the input list is a palindrome:
plndr(L):-lrev(L,L).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Test if the input element is memeber of the input list (forward tail recursion):
PREDICATES
ismof(r,lr)
ismof(c,lc)
ismof(s,ls)
ismof(i,li)
ismof(sym,lsym)
ismof(lr,llr)
ismof(lc,llc)
ismof(ls,lls)
ismof(li,lli)
ismof(lsym,llsym)
ismof(r,lr,r,r)
ismof(c,lc,r,r)
ismof(s,ls,r,r)
ismof(i,li,r,r)
ismof(sym,lsym,r,r)
ismof(lr,llr,r,r)
ismof(lc,llc,r,r)
ismof(ls,lls,r,r)
ismof(li,lli,r,r)
ismof(lsym,llsym,r,r)
% USAGE:
% ismof(InputElement,InputList) :: test if the input element is memeber of the input list
% lcount(L,4),ismof(10,L) :: will return L=[10,10,10,10];
CLAUSES
% Test if the input element is memeber of the input list (forward tail recursion):
% (i,i),(o,i)!
ismof(E,L):-ismof(E,L,0,C),C>0. % change arity in order to introduce the third parameter as Accumulator for the forth parameter which is the number of occurences of the given element in the given list
ismof(_,[],Ri,Ri). % in the most inner call, the Accumulator (third parameter) is "copied as" (unified with) final result for the number of occurences
ismof(E,[E|T],Ci,C):-Cia=Ci+1,ismof(E,T,Cia,C),!. % if the given element equals the head of the current list, count the occurence and make the forward recursive call on the tail
ismof(E,[_|T],Ci,C):-ismof(E,T,Ci,C). % or else, make the recursive call without updating the Accumulator
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% mknl(N,R) :: Expand a list (R) of consecutive integers starting from 1, ending with the given number N (forward tail recursion):
PREDICATES
mknl(r,lr) % (i,o)
mknl(r,lr,lr) % (i,a,o)
% USAGE:
% mknl(input, output)
% mknl(5,L) :: will return L=[1,2,3,4,5];
CLAUSES
% mknl(N,R) :: Expand a list (R) of consecutive integers starting from 1, ending with the given number N (forward tail recursion):
mknl(N,R):-N>0,mknl(N,[],R). % change arity in order to introduce the second parameter as Accumulator
mknl(0,Ri,Ri). % in the most inner call, the Accumulator (second parameter) is "copied as" (unified with) final result
mknl(Ni,Ri,R):-Ni>0,Nia=Ni-1,mknl(Nia,[Ni|Ri],R). % forward tail recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% mklel(N,L) :: Expand a list (L) containing N empty lists (forward tail recursion):
PREDICATES
mklel(i,llr)
mklel(i,lli)
mklel(i,lls)
mklel(i,llc)
mklel(i,llsym)
mklel(i,llr,llr)
mklel(i,lli,lli)
mklel(i,lls,lls)
mklel(i,llc,llc)
mklel(i,llsym,llsym)
% USAGE:
% mklel(4,R) :: will return R=[ [],[],[],[] ]
CLAUSES
% mklel(N,L) :: Expand a list (L) containing N empty lists (forward tail recursion):
mklel(N,LR):-mklel(N,[],LR). % change arity in order to introduce the second parameter as Accumulator
mklel(0,Ri,Ri). % in the most inner call, the Accumulator (second parameter) is "copied as" (unified with) final result
mklel(N,Ri,R):-N>0, Na=N-1, mklel(Na, [ []|Ri ], R). % forward tail recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% mklxl(R,N,L) :: Expand a list (L) containing N lists [R] (forward tail recursion):
PREDICATES
mklxl(r,i,llr)
mklxl(r,i,llr,llr)
% USAGE:
% mklxl(0.5, 4, L) :: will return L=[ [0.5],[0.5],[0.5],[0.5] ]
CLAUSES
% mklxl(R,N,L) :: Expand a list (L) containing N lists [R] (forward tail recursion):
mklxl(X,N,LR):-mklxl(X,N,[],LR). % change arity in order to introduce the third parameter as Accumulator
mklxl(_,0,Ri,Ri). % in the most inner call, the Accumulator (third parameter) is "copied as" (unified with) final result
mklxl(X,N,Ri,R):-N>0, Na=N-1, mklxl(X, Na, [ [X]|Ri ], R). % forward tail recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
PREDICATES
maxlr(lr,r)
maxlr(lr,r,r)
minlr(lr,r)
minlr(lr,r,r)
% USAGE:
% maxim/minim of a numeric list
CLAUSES
maxlr([X],X):-!.
maxlr([H|T],R):-maxlr(T,H,R).
maxlr([],Ri,Ri). % (i,i -> o)
maxlr([H|T],Ri,R):-
Ri>=H, maxlr(T,Ri,R);
Ri<H, maxlr(T,H,R).
minlr([X],X):-!.
minlr([H|T],R):-minlr(T,H,R).
minlr([],Ri,Ri). % (i,i -> o)
minlr([H|T],Ri,R):-
Ri<=H, minlr(T,Ri,R);
Ri>H, minlr(T,H,R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Compute scalar product of two vectors:
PREDICATES
scalarp(lr,lr,r)
scalarp(lr,lr,r,r)
CLAUSES
% Compute scalar product of two vectors (forward tail recursion):
scalarp(L,V,R):-lcount(L,N),lcount(V,N),scalarp(L,V,0,R). % test if the lists are equal in length and change arity in order to introduce an Accumulator (third parameter)
scalarp([],[],Ri,Ri). % in the most inner call, the Accumulator (third parameter) is "copied as" (unified with) final result
scalarp([H1|T1],[H2|T2],Ri,R):-Ria=Ri+H1*H2, scalarp(T1,T2,Ria,R). % forward tail recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% INSERTION SORT:
PREDICATES
sortins(lr,lr)
insinord(lr,lr,lr)
insertr(r,lr,lr)
%test(lr,lr,lr,r)
% INSERTION SORT:
CLAUSES
% 1
sortins([],[]):-!.
sortins([H|T],R):-insinord(T,[H],R),!.
insinord([],Ri,Ri).
insinord([H|T],Ri,R):-insertreal(H,Ri,Ria),insinord(T,Ria,R).
insertreal(X,[H],[H,X]):-H<=X,!.
insertreal(X,[H|T],[X,H|T]):-X<=H,!.
insertreal(W,[X,Y|T],[X,W,Y|T]):-X<=W,W<=Y,!.
insertreal(W,[X,Y|T],[X|R]):-insertreal(W,[Y|T],R),!.
% 2
%sortins([],[]):-!.
%sortins([H|T],R):-insinord(T,[H],R),!.
%insinord([],Ri,Ri).
%insinord([H|T],Ri,R):-insertreal(H,Ri,Ria),insinord(T,Ria,R).
%insertreal(X,[H],[H,X]):-H<=X,!.
%insertreal(X,[H|T],[X,H|T]):-X<=H,!.
%insertreal(X,L,R):- test(A,B,L,X),lconcat(A,[X|B],R).
%test(A,B,L,X):-lconcat(A,B,L),maxlr(A,AM),minlr(B,Bm),AM<=X,X<=Bm.
% 3
%sortins([],[]):-!.
%sortins([H|T],R):-insinord(T,[H],R),!.
%insinord([],Ri,Ri).
%insinord([X],[H],[H,X]):-H<=X,!.
%insinord([X],[H|T],[X,H|T]):-X<=H,!.
%insinord([W],[X,Y|T],[X,W,Y|T]):-X<=W,W<=Y,!.
%insinord([W],[X,Y|T],[X|R]):-insinord([W],[Y|T],R),!.
%insinord([H|T],Ri,R):-insinord([H],Ri,Ria),insinord(T,Ria,R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Additive shifting of all components within a given list (forward tail recursion):
PREDICATES
addrealtolr(r,lr,lr) % (i,i,o)
addrealtolr(r,lr,lr,lr) % (i,i,a,o)
% USAGE:
% additive shifting of all components within a given list
% addrealtolr(0.5,[1,4,2],L) :: will return L=[ 1.5, 4.5, 2.5]
CLAUSES
% Additive shifting of all components within a given list (forward tail recursion):
addrealtolr(N,L,R):-addrealtolr(N,L,[],R). % change arity in order to introduce an Accumulator (third parameter)
addrealtolr(_,[],Ri,R):-lrev(Ri,R). % in the most inner call, the Accumulator (third parameter) is reversed and unified with final result
addrealtolr(N,[H|T],Ri,R):-Ha=H+N, addrealtolr(N,T,[Ha|Ri],R). % forward tail recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Compute the product of all components of a numeric list (forward tail recursion)
PREDICATES
lprod(lr,r)
lprod(lr, r,r)
% USAGE
% lprod([1,2,3],R) :: will return R=1*2*3=3!=6
CLAUSES
Compute the product of all components of a numeric list (forward tail recursion)
lprod([X],X):-!.
lprod(L,R):-lprod(L,1,R). % change arity in order to introduce an Accumulator (second parameter)
lprod([],Ri,Ri). % in the most inner call, the Accumulator is unified with final result
lprod([H|T],Ri,R):-Ria=Ri*H,lprod(T,Ria,R). % while the current list is not empty, update the Accumulator and make forward tail recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Compute positive integer power of a real number (forward tail recursion):
PREDICATES
pow(r,r,r)
% USAGE
% pow(1.6,2,R) :: will return R=2.56
CLAUSES
% Compute positive integer power of a real number (forward tail recursion using a list)
pow(B,E,R):-lcount(L,E),singleton(L,B),lprod(L,R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Compute Butterfly Permutation (forward tail recursion)
% http://fmi.spiruharet.ro/bodorin/articles/brdfpvdro.pdf (Butterfly Permutation, Fourier Permutation, Bit Reversal)
PREDICATES
% bitreversal(0,3,[0,1,2,3,4,5,6,7],[0,4,2,6,1,5,3,6])
% bitreversal(S,K,I,BR)
bitreversal(r,r,lr,lr) % (i,i,o,o)
% bitrev(0,3,[0,4,2,6,1,5,3,6])
% bitrev(S,K,BR)
bitrev(r,r,lr,lr) % (i,i,ia -> o)
CLAUSES
% Compute Butterfly Permutation
bitreversal(S,K,I,BR):-pow(2,K,N), mknl(N,I1), addrealtolr(-1,I1,I0), addrealtolr(S,I0,I), bitrev(S,K,[S],BR).
bitrev(_,1,Ri,R):-addrealtolr(1,Ri,Ri2),lconcat(Ri,Ri2,R).
bitrev(S,K,Ri,R):- Ka=K-1, pow(2,Ka,P), addrealtolr(P,Ri,Ri2), lconcat(Ri,Ri2,Ria), bitrev(S,Ka,Ria,R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Delete an element from a list (forward tail recursion)
PREDICATES
delfromlist(r,lr,lr)
delfromlist(i,li,li)
delfromlist(c,lc,lc)
delfromlist(s,ls,ls)
delfromlist(sym,lsym,lsym)
delfromlist(lr,llr,llr)
delfromlist(li,lli,lli)
delfromlist(lc,llc,llc)
delfromlist(ls,lls,lls)
delfromlist(lsym,llsym,llsym)
delfromlist(r,lr,lr,lr)
delfromlist(i,li,li,li)
delfromlist(c,lc,lc,lc)
delfromlist(s,ls,ls,ls)
delfromlist(sym,lsym,lsym,lsym)
delfromlist(lr,llr,llr,llr)
delfromlist(li,lli,lli,lli)
delfromlist(lc,llc,llc,llc)
delfromlist(ls,lls,lls,lls)
delfromlist(lsym,llsym,llsym,llsym)
% USAGE:
% delfromlist(1,[1,2,1,3,1,4,1,5],R) :: will return R=[2,3,4,5]
CLAUSES
% Delete an element from a list (forward tail recursion)
delfromlist(E,L,R):-delfromlist(E,L,[],R). % change arity in order to introduce an Accumulator (third parameter)
delfromlist(_,[],Ri,R):-lrev(Ri,R). % in the most inner call, the Accumulator (third parameter) is reversed and unified with final result
delfromlist(E,[E|T],Ri,R):-delfromlist(E,T,Ri,R),!. % if E is the head of the list, make recursive call on the tail without updating the Accumulator
delfromlist(E,[H|T],Ri,R):-delfromlist(E,T,[H|Ri],R). % or else (see the previous cut), update the Accumulator and make the recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Eliminate all duplicates from a given list (forward tail recursion)
PREDICATES
ldeflate(lr,lr)
ldeflate(li,li)
ldeflate(lc,lc)
ldeflate(ls,ls)
ldeflate(lsym,lsym)
ldeflate(llr,llr)
ldeflate(lli,lli)
ldeflate(llc,llc)
ldeflate(lls,lls)
ldeflate(llsym,llsym)
ldeflate(lr,lr,lr)
ldeflate(li,li,li)
ldeflate(lc,lc,lc)
ldeflate(ls,ls,ls)
ldeflate(lsym,lsym,lsym)
ldeflate(llr,llr,llr)
ldeflate(lli,lli,lli)
ldeflate(llc,llc,llc)
ldeflate(lls,lls,lls)
ldeflate(llsym,llsym,llsym)
% USAGE:
ldeflate([4,1,2,1,4,5], L) :: will return L=[4,1,2,5]
% Eliminate all duplicates from a given list (forward tail recursion)
CLAUSES
ldeflate(L,R):-ldeflate(L,[],R). % change arity in order to introduce an Accumulator (second parameter)
ldeflate([],Ri,R):-lrev(Ri,R). % in the most inner call, the Accumulator is reversed and unified with final result
ldeflate([H|T],Ri,R):-delfromlist(H,T,Ta), ldeflate(Ta,[H|Ri],R). % forward tail recursive call
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Compute the Run-Length Encoding of a list
PREDICATES
rle(lr, lr,lr) % (i,o,o)
rle(lr,lr,lr,lr,lr) % (i,ri,ri,r,r)
rld(lr,lr ,lr) % (i,i,o)
rld(lr,lr,lr,lr) % (i,i,ri,r)
mkctl(r,r,lr)
mkctl(r,r,lr,lr)
CLAUSES
% Run-Length Encoding
rle([H|T],W,O):-
rle(T,[H],[1],Wrv,Orv), % change arity in order to introduce two Accumulators (second and third parameters)
lrev(Wrv,W),lrev(Orv,O).
%nl,write("Who:"),write(W),
%nl,write("Occ:"),write(O),
%nl.
rle([],RWi,ROi,RWi,ROi). % ( i,(i,i)->(o,o) ) % in the most inner call, the Accumulators are unified with final result results
rle([H|T],[H|T2],[Oi|T3],W,O):-
Oia=Oi+1,
rle(T,[H|T2],[Oia|T3],W,O),!. % encode reduntance and make the recursive call
rle([H|T],[X|T2],Oi,W,O):-
lconcat([H],[X|T2],Wia),
lconcat([1],Oi,Oia),
rle(T,Wia,Oia,W,O). % forward tail recursive call
% Compute the Run-Length Encoding of a list:
rld(W,O,R):-rld(W,O,[],R). % change arity in order to introduce an Accumulators (third parameter)
rld([],[],Ri,Ri). % (i,i,i->o) % in the most inner call, the Accumulators are unified with final result results
rld([W|WT],[O|OT],Ri,R):-
mkctl(W,O,URi),lconcat(Ri,URi,Ria),
rld(WT,OT,Ria,R). % forward tail recursive call
% mkctl(Who,Occ,[3,3,3,3,3]) Expand a singletone containing Occ occurences of Who (forward tail recursion)
% USAGE: mkctl(3,5,[3,3,3,3,3])
mkctl(W,O,R):-mkctl(W,O,[],R).
mkctl(_,0,Ri,Ri):-!. % (i,i,i->o)
mkctl(W,O,Ri,R):-
Oa=O-1,
mkctl(W,Oa,[W|Ri],R).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
]]>