Prologue repeating list

I am working with Prolog and triying prolog list programs to do some operations on them. However, I got stuck at a point and couldn't find any solution or pattern.

I want to write a function that takes two lists of integers and returns a float value. The size of the two lists is equal. The float value is the result of the comparison divided by the size of the list.

The function should compare every element of the first list with every element of the second list. The pair (i, j) is that i is the location of the item in the first list and j is the location of the item in the second list. If i is greater than j, the comparison is incremented by 1. If i is less than j, the comparison is decremented by 1. If equal, nothing happens. At the end of the above operation, we return the float value described above.

Example:

retVal([4,5,3], [8,2,1], Result).

      

should return result = (-1 + 1 + 1-1 + 1 + 1-1 + 1 + 1) / 3 = 0.33

In an object oriented language, this is as easy as printing to the console. However in Prolog I have no idea. Thank you in advance.

0


source to share


3 answers


What you describe in words could be this snippet

retVal(L1,L2, Result) :-
 findall(S, (member(X1,L1), member(X2,L2), (X1 < X2 -> S = -1 ; S = 1)), L),
 sum_list(L, Sum),
 length(L1, Len),
 Result is Sum / Len.

      

Alas, the test result does not meet your expectations



?- retVal([4,5,3], [8,2,1], X).
X = 1.

      

As liori pointed out in his comment, your manual calculation is incorrect ...

0


source


I think this should work:

sgn(X, Y, -1) :- X<Y.
sgn(X, Y, 1) :- X>Y.
sgn(X, X, 0).

ssapd(L, R, O) :- ssapd(L, R, R, 0, 0, O).
ssapd([LI | LR], RL, [RPI | RPL], ACC, ACCL, O) :-
    sgn(LI, RPI, SGN), !,
    ACC1 is ACC + SGN,
    ssapd([LI | LR], RL, RPL, ACC1, ACCL, O).
ssapd([_  | LR], RL, [], ACC, ACCL, O) :-
    ACCL1 is ACCL + 1,
    ssapd(LR, RL, RL, ACC, ACCL1, O).
ssapd([],        _,  _, ACC, ACCL, Result) :-
    Result is ACC / ACCL.

      



This is a good tail-recursive implementation, done using two accumulators, O (n²) time complexity and persistent memory (apart from input size). To execute it try:

ssapd([4,5,3], [8,2,1], Result).

      

0


source


This is a tail-recursive approach:

compare_list( Xs , Ys , Z ) :- 
  compare_list( Xs, Ys, 0 , 0 , S , L ) ,
  Z is float(S)/float(L)
  .

compare_list( []     , []     , S , L , S , L ) .
compare_list( [X|Xs] , [Y|Ys] , A , B , S , L ) :-
  A1 is A + sign(X-V) ,
  B1 is B + 1 ,
  compare_list(Xs,Ys,A1,B1,S,L)
  .

      

Another approach, this time "head recursive":

compare_list( Xs , Ys , Z ) :-
  compare_list( Xs , Ys , S , L ) ,
  Z is float(S)/float(L)
  .

compare_list( []     , []     , 0 , 0 ) .
compare_list( [X|Xs] , [Y|Ys] , S , L ) :-
  compare_list(Xs,Ys,S1,L1) ,
  S is S1 + sign(X-Y) ,
  L is L1 + 1
  .

      

The first implementation will not flood the stack with long lists, since it optimizes for [efficient] iteration, but requires accumulators; the latter implementation does not require accumulators, but will remove the stack if the list is long enough.

0


source







All Articles