0

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.

nudaStck
  • 311
  • 2
  • 6
  • 18

3 Answers3

0

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).
liori
  • 40,917
  • 13
  • 78
  • 105
0

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.

Nicholas Carey
  • 71,308
  • 16
  • 93
  • 135
0

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...

CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • retVal([1],[1],R) should definitely be zero, that is 0.0 and not something > 0. – false Jun 05 '14 at 21:32
  • Thank you for the answer that was so helpfull. Now I have another problem. How can I reach a pair of elements in two lists? L1 = [1,2,3], L2 = [3,2,5]. Pair (a, b) is determined as a is place of element in L1 and b is place of element in L2. All possible pairs of L1 and L2 is: (0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2). How can I get a list of pairs that are constructed from the two lists L1 and L2? Thank you. – nudaStck Jun 06 '14 at 11:46
  • try to use [nth0](http://www.swi-prolog.org/pldoc/doc_for?object=nth0/3) instead of member. Of course some other change is needed. I hope you have got the idea behind use of findall/3 – CapelliC Jun 06 '14 at 13:34