Prolog - How to get a tail so that it is not zero
I have the following problem:
Define a predicate
sorted(LL)
that runs when the listLL
contains other lists sorted in ascending order of length. For example:?- sorted([[],[1],[1,1],[1,1,1]]) -> yes. ?- sorted([[],[1],[1,1]]) -> yes. ?- sorted([[1],[],[1,1],[1,1,1]]) -> no.
And I have this code:
% shorter/2
shorter([],_).
shorter([_|T1], [_|T2]) :- shorter(T1,T2).
% sorted/1
sorted([]).
sorted([_]).
sorted([L1,L2 | T]) :- shorter2(L1, L2), sorted([L2,T]).
The problem is contained in the above line: sorted([L2,T])
. When there is only one item left in the list of lists, this call will add an empty list []
, causing the shorter / 2 to fail. He is depicted on the next SWIPL track.
[trace] ?- sorted([[1],[2,3]]).
Call: (6) sorted([[1], [2, 3]]) ? creep
Call: (7) shorter2([1], [2, 3]) ? creep
Call: (8) shorter2([], [3]) ? creep
Exit: (8) shorter2([], [3]) ? creep
Exit: (7) shorter2([1], [2, 3]) ? creep
Call: (7) sorted([[2, 3], []]) ? creep <-- empty list appended
Call: (8) shorter2([2, 3], []) ? creep
Fail: (8) shorter2([2, 3], []) ? creep
Fail: (7) sorted([[2, 3], []]) ? creep
Fail: (6) sorted([[1], [2, 3]]) ? creep
source to share
@PauloMoura already gave you the correct answer. Is there anything to know about this? How did you face this problem? And how can you systematically identify such problems? I'm assuming you haven't jumped into the debugger to look at all these traces for sheer curiosity and low stock of animated gifs.
You are more likely to run into a problem. That is, you had a goal sorted([[1],[2,3]]).
that you expected to achieve, but it is not. So you had an unexpected crash here . Sometimes also called deficiency or incompleteness . This means that the definition for is sorted/1
too specialized, it describes a set of solutions that are too small - at least it skips sorted([[1],[2,3]])
.
This often helps to minimize the problem. It also sorted([[],[3]])
fails, although we expect it to be successful. And sorted([[],[]])
even hinges.
Understanding no interruption
Loops? This is often even easier to localize in a pure Prolog program. I will add goals and objectives to the team such as . The resulting piece of the program (called the rejection slice ) will certainly become completely dysfunctional. But it will keep a very pleasant property. For: if this is a new cycle of fragments, then the original program will also loop. Here is this program that is still looping: false
T = []
? - sorted ([[], []]), false .sorted ([]): - false.sorted ([_]): - false. sorted ([L1, L2 | T]): - T = [], L1 = [], L2 = [] , shorter (L1, L2), sorted ([L2, T]). shorter ([], _).shorter ([_ | T1], [_ | T2]): - false,shorter (T1, T2).
In other words:
sorted([[],[]]) :-
shorter([],[]),
sorted([[],[]]).
So, procedurally speaking, this rule does not (always) decrease the length of the list.
Final reading
Another way to understand the problem is to read the recursive rule from right to left in the direction of the arrow . In fact, :-
intended to symbolize & larr; well, 1970s style (listen to this French 1972 summer to until you get it). So try this. I will read:
sorted([L1,L2 | T]) :- shorter2(L1, L2), sorted([L2,T]).
^^^^^^^^^^^^^^ starting here
I start on the right side and interpret this as:
Provided is
sorted([L2,T])
true.
Maybe some additional note: now it can be very difficult for you. You could say: who knows? Maybe this is not true at all! But the point is that this is just conditional. OK?
and provided that it is
shorter(L1, L2)
true
then we can conclude that it issorted([L1, L2|T])
true.
So we take a list of length 2 as provided and conclude that there is also a list of length 2 or more.
But where do we actually state that a list of length 2 is taking place? There is no other place but this rule. Thus: It is not specified anywhere. And thus, lists of length 2 or more will never be sorted .
source to share