Recursion on a list involving arithmetic operations and counting elements?

Question

I'm struggling to really grasp the understanding of Prolog lists and recursive calls. I've been working on a program to keep track of how many items are greater than the head of the list and then recursively call this relation to check greater than the next element and so on. I've gotten my program working to the point where it can count the number of elements greater than the head but once it reaches the end and tries to recursively call the relation on the next element it fails. From the research I've done here's what I have and how I think it's supposed to work:

Input - List = [7,2,4,3,6,9,8,10,12,5].

testHead(List).

testHead([H|T]) :-
    greaterThan(H,T,0),
    teastHead(T).

^My understanding is this relation takes the head element from the list and calls greaterThan using the head and the rest of the list. After the greaterThan finishes, it should recursively call testHead(T) to test the next element and so on.

greaterThan(H,[X|T],C) :-
    H > X ->
    C2 is C+1,
    greaterThan(H,T,C2);
    greaterThan(H,T,C).

^My understand here is the greaterThan reads in the head element, the rest of the list, and a variable for counting. If the head is greater than the next element, increase the count and recursively call greaterThan with the Tail and new count; else recursively call greaterThan without incrementing count.

My expected output would be C2 = 12. (7 is greater than 5 elements, 2 is greater than 0 elements, 4 is greater than 1 element, and so on)

The actual output currently is 5; then false.
My program seems to be correctly evaluating and incrementing for the head element but when it finishes greaterThan for that element the program returns false. I've tried researching and understanding lists and recursive calls in prolog but I've been hitting a wall. I'm not sure if it fails because you can't recursively run the increment relation or if there's some other issue with my list relation. Any clarification on how to tackle this issue and how prolog functions here would be helpful.

DuDa DuDa · Accepted Answer · 2020-11-17T14:59:32

Lets start with your first code snippet:

testHead(List).  
testHead([H|T]) :-
    greaterThan(H,T,0),
    teastHead(T).

You got the idea of recursion but I see four problems.

First: there is only one attribute for testHead, which means (besides true and false) you get nothing back. So it should look more like this: testHead([H|T], L) ....

Second: you need to know when to stop. This is normally the first line of a predicate. Yours states: anything matches. But it should say something like: if there is no element left, I can "return" an empty list. testHead([],[]).

Third: You call greaterThan(H,T,0) with the fixed value 0, which means you want to test if the "output" value is zero. Which is not the case, you want to count stuff. So put a variable here: N

Fourth: If you have calculated a value N you have to forward it to the outputlist. Since you will get the list Nlist from your recursive call, you can create a new list with N as the head element and Nlist as the tail and "return" this new list.

Conclusion:

testHead([],[]).
testHead([H|T],[N|Nlist]) :-
    greaterThan(H,T,N),
    testHead(T,Nlist).

Sadly we can not test it yet, we have to have a look at greaterThan/3. Your snippet is the following:

greaterThan(H,[X|T],C) :-
    H > X ->
    C2 is C+1,
    greaterThan(H,T,C2);
    greaterThan(H,T,C).

And also here are some parts odd.

First: You need to tell when to stop. Usually you stop with the empty list [] or if the list has only one element left [A]. If you are not interested in the content of A you use a "throw away variable" which starts with an underscore _. This results in: greaterThan(_,[],0). Which means: if my list is empty, there are 0 numbers greater in my list, no matter what the refence value was. Also since the order of rules matters you put this on top of your recursion rule.

Second: You got the cases right, so if H is larger than the head X of the list do something, otherwise "ignore" X by just calling the same predicate without X. The problem appears in the something part: since the value of C2 is unificated before C you need to calculate C depending on C2 and not vice versa. C is C2+1 means: I know the value C2 from the recursion call and since H>X I want to add one to its value and "return" it.

Third: You know the value of C2 just after asking greaterThan(H,T,C2), so put the C is C2+1 after it.

Ok, now we got:

greaterThan(_,[],0).
greaterThan(H,[X|T],C) :-
    H > X ->
    greaterThan(H,T,C2),
    C is C2+1;
    greaterThan(H,T,C).

testHead([],[]).
testHead([H|T],[N|Nlist]) :-
    greaterThan(H,T,N),
    testHead(T,Nlist).

Lets test it!

?- testHead( [7,2,4,3,6,9,8,10,12,5],L).
L = [5, 0, 1, 0, 1, 2, 1, 1, 1, 0] ;
false.

Looks good besides that you don't want a list but a total number. Ok, here you go:

testHead([],0).
testHead([H|T],New) :-
    greaterThan(H,T,N),
    testHead(T,NN),
    New is NN+N.

?- testHead( [7,2,4,3,6,9,8,10,12,5],N).
N = 12 ;
false.

Explanation: if your input list is empty, there is nothing to be done, "return" the neutral element for addition: 0.
If your inputlist has a head element H, calculate the "greater as N remaining elements" through greaterThan(H,T,N). Assume your code works so you can call testHead(T,NN) for your tail list T and get the sum value NN. If both values N and NN are known, add them and state it as the "return".

Recursion on a list involving arithmetic operations and counting elements?

1 Answers