Geek Answers Handbook

Prolog list items above n

I am new to Prolog, so I have a few problems with a specific task. The task is to write a tail recursive predicate count_elems(List,N,Count) condition List_Element > N, Count1 is Count+1 .

My approach:

 count_elems( L, N, Count ) :- count_elems(L,N,0). count_elems( [H|T], N, Count ) :- H > N , Count1 is Count+1 , count_elems(T,N,Count1). count_elems( [H|T], N, Count ) :- count_elems(T,N,Count).

Error-Msg:

 ERROR: toplevel: Undefined procedure: count_elems/3 (DWIM could not correct goal)

I'm not quite sure where the problem is. thanks for any help :)

+2
source share
3 answers

If you want to make a tail recursive version of your code, you need (as CapelliC points out) an additional parameter to work as a battery. You can see the problem in your first sentence:

 count_elems(L, N, Count) :- count_elems(L,N,0).

Here Count is a singleton variable not created anywhere. Your recursive call to count_elems starts at 0 , but there is no longer a variable to be created along with the result. So you need to:

 count_elems(L, N, Count) :- count_elems(L, N, 0, Count).

Then declare the count_elem/4 sentences:

 count_elems([H|T], N, Acc, Count) :- H > N, % count this element if it > N Acc1 is Acc + 1, % increment the accumulator count_elems(T, N, Acc1, Count). % check the rest of the list count_elems([H|T], N, Acc, Count) :- H =< N, % don't count this element if it <= N count_elems(T, N, Acc, Count). % check rest of list (w/out incrementing acc) count_elems([], _, Count, Count). % At the end, instantiate total with accumulator

You can also use the if-else structure for count_elems/4 :

 count_elems([H|T], N, Acc, Count) :- (H > N -> Acc1 is Acc + 1 ; Acc1 = Acc ), count_elems(T, N, Acc1, Count). count_elems([], _, Count, Count).

Also, as CapelliC noted, your reported error message is probably due to the fact that you are not reading the prolog in the source file.

+6
source

Save logical-purity with clpfd !

Here's how:

 :- use_module(library(clpfd)). count_elems([],_,0). count_elems([X|Xs],Z,Count) :- X #=< Z, count_elems(Xs,Z,Count). count_elems([X|Xs],Z,Count) :- X #> Z, Count #= Count0 + 1, count_elems(Xs,Z,Count0).

Let's see how versatile count_elems/3 :

  ? - count_elems ([1,2,3,4,5,4,3,2], 2, Count).
 Count = 5;  % leaves useless choicepoint behind
 false

 ? - count_elems ([1,2,3,4,5,4,3,2], X, 3).
 X is 3;
 false

 ? - count_elems ([1,2,3,4,5,4,3,2], X, Count).
 Count = 0, X in 5..sup;
 Count = 1, X = 4;
 Count = 3, X = Count;
 Count = 5, X = 2;
 Count = 7, X = 1;
 Count = 8, X in inf..0.

Edit 2015-05-05

We could also use the tcount/3 meta predicate in conjunction with the updated version (#<)/2 :

 #<(X,Y,Truth) :- integer(X), integer(Y), !, ( X<Y -> Truth=true ; Truth=false ). #<(X,Y,true) :- X #< Y. #<(X,Y,false) :- X #>= Y.

Repeat the above requests again!

 ?- tcount(#<(2),[1,2,3,4,5,4,3,2],Count). Count = 5. % succeeds deterministically ?- tcount(#<(X),[1,2,3,4,5,4,3,2],3). X = 3 ; false. ?- tcount(#<(X),[1,2,3,4,5,4,3,2],Count). Count = 8, X in inf..0 ; Count = 7, X = 1 ; Count = 5, X = 2 ; Count = 3, X = Count ; Count = 1, X = 4 ; Count = 0, X in 5..sup .

Performance Note:

  • count_elems([1,2,3,4,5,4,3,2],2,Count) left a useless choice.
  • tcount(#<(2),[1,2,3,4,5,4,3,2],Count) was deterministic.
+3
source

It seems you did not consult the source file.

When you fix this (can you save these rules in the file count_elems.pl and then issue ?- consult(count_elems). ), You will encounter the actual problem that Count is a singleton in the first rule, which indicates that you should transmit the counter to the actual tail recursive sentences and combine it with the battery (a counter that is updated to Count1) when the list is being scanned.

You will end up with 3 articles count_elems / 4. Do not forget the base case:

 count_elems([],_,C,C).
+2
source

More articles:


All Articles