Prolog iterating over list

Question

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

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

The function should compare every elemen of first list to every elemen of the second list. A pair (i, j) is that i is the location of element in first list and j is the location of the element in second list. If element i greater than element j, result of comparison is incremented by 1. If element i less than element j, result of comparison decremented by 1. If equal, nothing happen. 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 object oriented language, it is as simple as printing something on the console. However, I don't have any idea in Prolog. Thank you in advance.

Answer 1

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 former implementation won't overflow the stack on long lists as it gets optimized away into [effectively] iteration, but requires accumulators; the latter implementation doesn't require accumulators, but will blow the stack if the list(s) are of sufficient length.

Answer 2

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.

It's a nice implementation with tail recursion done by using two accumulators, O(n²) time complexity and constant memory (except for the size of input). To execute it, try:

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

Answer 3

What you describe by 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 outcome doesn't match your expectation

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

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