2

I want to count the number of elements in a list which have a relation with the element following. The predicate I have works by using an accumulator variable which it increments if the predicate related returns true. The following example code is to check the number of times an element is greater than it's previous element.

So for example

count_list([1,2,3,2,1,3,2],Count).

should return 3.

The code almost works. It increments the accumulator variable correctly. However, the function returns false, when it tries to compare the final 2 at the end with the non-existent next term.

listofitems([],N,N).
%count number of items which are related to the previous
listofitems([A,B|T],Acc,N) :-
   write(A),write(' '), write(B),
   ( related(A,B) -> Acc1 is Acc+1 ; Acc1 = Acc ),
   write(Acc1),write('\n'),
  listofitems([B|T],Acc1,N).

count_list(L,N):-
   listofitems(L,0,N).

%define the relationship to be counted
related(A,B):-
   B>A.

Does anyone have any suggestions as to how to create an elegant terminating condition so I can return the accumulated value?

false
  • 10,264
  • 13
  • 101
  • 209
John
  • 303
  • 2
  • 12

3 Answers3

4

Does anyone have any suggestions as to how to create an elegant terminating condition so I can return the accumulated value?

The problem you have is that your query fails. Try first to minimize the query as much as possible. Certainly, you expect it to work for:

?- listofitems([], Count).
   Count = 0.

Yet, it already fails for:

?- listofitems([1], Count).
   false.

So let's try to dig into the reason for that. And since your program is pure (apart from those writes), it is possible to diagnose this a little better by considering a generalization of your program. I prefer to look at such generalizations as I do not want to read too much (eye strain and such):

:- op(950, fy, *).
*_.

listofitems([], N,N).
listofitems([A,B|T], Acc,N) :-
   * ( related(A,B) -> Acc1 is Acc+1 ; Acc1 = Acc ),
   * listofitems([B|T], Acc1,N).

count_list(L,N):-
   listofitems(L,0,N).


?- count_list([1], Count).
   false.

Even this generalization fails! So now in desperation I try to ask the most general query. It's like when I ask one thing after the other and get a noe after a no. Good this is Prolog, for we can ask: "Say me just everything you know".

?- count_list(Es,Count).
   Es = [], Count = 0
;  Es = [_,_|_].

So it is only the case for the empty list and lists with at least two elements. But there is no answer for one-elemented lists! You will thus have to generalize the program somehow.

A natural way would be to add a fact

listofitems([_], N, N).

As a minor remark, this isn't called a "terminating condition" but rather a "base case".

And if you really want to trace your code, I recommend these techniques instead of adding manual writes. They are much too prone to error.

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
4

If the all list items are integers and your Prolog system supports , you can proceed like this:

:- use_module(library(clpfd)).
:- use_module(library(lists), [last/3]).
:- use_module(library(maplist), [maplist/4]).

To relate adjacent items, look at two sublists of [E|Es], Es and Fs. If, say, [E|Es] = [1,2,3,2,1,3,2] holds ...

  • ... then Fs lacks the last item (Fs = [1,2,3,2,1,3,2]) ...
  • ... and Es lacks the first item (Es = [1,2,3,2,1,3,2]).

maplist/4 and i0_i1_gt01/3 map corresponding list items in Fs and Es to 0 / 1:

i_j_gt01(I, J, B) :-                  % if I #<  J then B #= 1
   I #< J #<=> B.                     % if I #>= J then B #= 0

?- maplist(i_j_gt01, [1,2,3,2,1,3], [2,3,2,1,3,2], Bs).
Bs = [1,1,0,0,1,0].

Last, sum up [1,1,0,0,1,0] using sum/3:

?- sum([1,1,0,0,1,0], #=, N).
N = 3.

Let's put it all together!

count_adj_gt([E|Es], N) :-
   last(Fs, _, [E|Es]),               % or: `append(Fs, [_], [E|Es])`
                                      % or: `list_butlast([E|Es], Fs)`
   maplist(i_j_gt01, Es, Fs, Bs),
   sum(Bs, #=, N).

Sample query using SICStus Prolog 4.3.2:

?- count_adj_gt([1,2,3,2,1,3,2], N).
N = 3.                                % succeeds deterministically
Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
1

not sure about

an elegant terminating condition

my whole code would be

?- Vs=[1,2,3,2,1,3,2], aggregate_all(count, (append(_,[X,Y|_], Vs), X<Y), Count).

That's all...

If you need something more complex, remember that library(clpfd) has more to offer.

CapelliC
  • 59,646
  • 5
  • 47
  • 90