Why do I get duplicate results in my `length/2` implementation in prolog?

2
votes

I'm working through exercises in Prolog. I've implemented a predicate similar to length/2 (called ue_length here) like this:

%%
% ue_length/2
%%

% not a list predicate

\+(T) :- call(T), !, fail.
\+(_).

% target case

ue_length(List, Length) :- \+(is_list(List)), !, fail.
ue_length(List, Length) :- ue_length(List, 0, Length).

% standard cases

ue_length([], Length, Length).
ue_length([X], Part, Length) :- ue_length([], [Part], Length).
ue_length([X| Rest], Part, Length) :- ue_length(Rest, [Part], Length).

The result is supposed to be a term rather than a number: 0 for [], [0] for a list of length one and [...[0]...] (n brackets) for a list of length n.

When I query Prolog (SWI-Prolog 6) with e.g. [1,2,3,4,5] I get the correct result twice.

?- ue_length([1,2,3,4,5], X).
X = [[[[[0]]]]] 
X = [[[[[0]]]]].

I'm new to Prolog. Can someone explain why I get a redundant result?

1
prolog
Your second 'standard case' is redundant. It is the same as third case with Rest = []. - zch
@zch Ok. You're right. I just tried it without the second standard case and it works. Post an answer and I'll accept it. - FK82
Your definition for (\+)/1 should produce an error in SWI? Have you overlooked it? - false
What is the meaning of the second argument? That's quite unusual. Rather use successor-arithmetics. - false
@false Yes, I checked the whole thing in SWI 6.6 and it runs just fine. The definition of \+/1 is not mine. It's a hint in the exercise. The intended semantic is a ``not a list'' predicate. It's not entirely clear to me either. - FK82

1 Answers

3
votes

Minimize the problematic query

As a first step, reduce the size of your query. The same problem (redundant solutions) can be observed already with ue_length([1], X). alone.

But there is something else which is much more problematic:

Is your definition a relation?

?- ue_length(L,N).
false.

So your definition succeeds with a list [1] but fails with a variable in its place? This does not make any sense at all! Even looping would be a better behavior.

Another problematic case is

?- ue_length(L,0).
false.

Here, your definition should give L = [] as answer.

The culprit for this is the test using is_list/1. Simply drop the rule

ue_length(List, Length) :- \+(is_list(List)), !, fail. % incorrect!

Now your definition can also be used to ask the most general query which contains distinct variables in the arguments.

?- ue_length(L,N).
  L = [], N = 0
; L = [_A], N = [0]
; L = [_A], N = [0]
; L = [_A, _B], N = [[0]]
...

This is one of the very nice properties of Prolog: You do not need to type in concrete data for your test cases. Just enter the most general query like a pro, and Prolog will do the rest for you.

Localize with false

To localize this redundancy, first think of how that could have happened. One simple possibility is that some clause in your program is redundant and can thus be deleted. Let's say it's the last one. So I will insert a goal false into the last clause. And I try again the most general query. Alas ...

ue_length(List, Length) :- ue_length(List, 0, Length).

% standard cases

ue_length([], Length, Length).
ue_length([_X], Part, Length) :-
   ue_length([], [Part], Length).
ue_length([_X| Rest], Part, Length) :-
   false,
   ue_length(Rest, [Part], Length).

?- ue_length(L,N).
  L = [], N = 0
; L = [_A], N = [0]
; false.

That rule must be quite important, for now we get only answers for lists of length zero and one. So my guess was wrong. But my point is that you can see this very easily by simply using the most general query. The actual redundant clause is the other one. And don't forget to ask the most general query such that you can be sure you get all your answers!