Stopping recursion when list length = 1

I am trying things in Prolog.
I wonder why the below program is not working?
The point is to remove last element of a list. I thought to make the recursion stop when the list has one element.
But apparently I think wrongly.
Can someone have a look at it?
I tried with a cut operator as well.

Thank you!

append( [], Li, Li). 
append( [H|T], Li2, [X|Res]) :- append(T, Li2, Res).

removeLast([H|T], R):- length([H|T],1). %stop recursion when the tail has only one element
removeLast([H|T], R):- append(R, H, H), removeLast(T, R).

With “append”:

removeLast(X,Y) :-
    append(Y,[_],X).

Without “append”:

removeLast([_],[]).
removeLast([H|T],[H|R]) :- 
    removeLast(T,R).

Marco

1 Like

Hi Marco!

This does not work:

append( [], Li, Li).
append( [H|T], Li2, [X|Res]) :- append(T, Li2, Res).

removeLast(X,Y) :-
    append(Y,[_],X).

Am I missing a line?

I used the predicate already defined in SWI-Prolog.

While in other programming languages thinking in terms of numbers would be good idea, in Prolog however thinking in terms of numbers or counts is not always the best way. What I personally find to be a better way is to think in term of parts of graphs or symbols.

Graph

From: GeeksForGeeks

image

Symbols

?- write_term([1,2,3],[dotlists(true)]).
.(1,.(2,.(3,[])))
true.

To help you better understand how to think about list here are few examples.

Print a list with recursion, which is to walk a list and print each item when visited.

print_list([]) :-
    format('~n',[]).
print_list([H|T]) :-
    format('~w ',H),
    print_list(T).

Example runs:

?- print_list([1,2,3]).
1 2 3 
true.

?- print_list([1]).
1 
true.

?- print_list([]).

true.

So now you know how to walk a list using recursion.

The next challenge is to change the value of a list. Remember that in Prolog values are immutable so to change a list you need two variables, one for the original list and one for the changed list.

First example will just walk a list and duplicate it.

duplicate_list([],[]).
duplicate_list([H0|T0],[H0|T]) :-
    duplicate_list(T0,T).
?- duplicate_list([1,2,3],L).
L = [1, 2, 3].

?- duplicate_list([1],L).
L = [1].

?- duplicate_list([],L).
L = [].

Next we will reverse a list. This needs a helper predicate, but instead of adding the word _helper to the name, because the helper uses 3 arguments and the query predicate uses 2 arguments, the same name can be used for both.

This is not needed to solve your question, but you should be aware of it as it looks like other recursive code, but is dramatically different. In other words, the construction of the list is not done in the head of the clause, but in the body of the clause.

reverse_list(List,Rev) :-
    reverse_list(List,Rev,[]).

reverse_list([],L,L).
reverse_list([H|T],L,Rest) :-
    reverse_list(T,L,[H|Rest]).
?- reverse_list([1,2,3],R).
R = [3, 2, 1].

?- reverse_list([1],R).
R = [1].

?- reverse_list([],R).
R = [].

Now to learn how to choose the last item in the list.

It is common for recursion routines to stop at the end of the structure, but in this case you don’t want to stop at the end, you want to stop at 1 less than the end.

The predicate used to stop the recursion at the end of the structure is like

duplicate_list([],[]).

but to stop one short of the end it would be like

duplicate_list([H|[]],[H|[]]).

and to remove the last item would be the same as starting the new list without the last item which was H

duplicate_list([H|[]],[]).

which is the same as

duplicate_list([_],[]).

So to remove the last item it is

remove_last_list([_],[]).
remove_last_list([H0|T0],[H0|T]) :-
    remove_last_list(T0,T).

Examples
Note that it leaves a choicepoint, but don’t want to teach about cuts in this topic.

?- remove_last_list([1,2,3],L).
L = [1, 2] ;
false.

?- remove_last_list([1],L).
L = [] ;
false.

?- remove_last_list([],L).
false.

I suspect that because you used append/3 in your question you are doing an exercise that ask you to use append/3. I know this did not use append/3, but it should help you.

Also of help to know when working with list in Prolog

?- write_term([1,2,3],[dotlists(true)]).
.(1,.(2,.(3,[])))
true.

?- write_term([1],[dotlists(true)]).
.(1,[])
true.

?- write_term([],[dotlists(true)]).
[]
true.

?- [_] = [_|[]].
true.

?- write_term([_],[dotlists(true)]).
.(_2178,[])
true.

?- write_term([_|[]],[dotlists(true)]).
.(_2404,[])
true.
1 Like

There is an issue with your definition of append. If you try it out.
e.g.

?- append([a,b],[c,d],E).
E = [_7262, _7268, c, d].

In fact SWI should be warning you about why this isn’t working when it first reads your source code.

Disclaimer: a bunch of personal opinions that I cannot back up with real arguments.

If you are trying to learn a new language in general and Prolog in particular, the best way to spend your time is to read the textbook definitions and compare them to the definitions in the standard library.

Do not waste time implementing something that is in the standard library. Instead, spend time looking for things that are in the standard library.

This isn’t a warning about not reinventing the wheel! This is about orienting yourself in a vast unknown area!

For SWI-Prolog, for many predicates you can click on the :- inside the circle on the top-right of the documentation of a predicate. For append/3, this should get you from here:

https://www.swi-prolog.org/pldoc/doc_for?object=append/3

to here:

https://www.swi-prolog.org/pldoc/doc/_SWI_/library/lists.pl?show=src#append/3

The full source code is available on GitHub: https://github.com/SWI-Prolog/swipl-devel

Then, never ignore warnings. Like, never ever. Warning in SWI-Prolog have always meant that I thought my code means something but actually it meant something else. Sometimes the warning text itself might be misleading, but I cannot remember hitting a false positive.

2 Likes

One caveat of this is when the author uses predicate names that are not the same as the standard.

In “Prolog Programming for Artificial Intelligence” by Ivan Bratko, (WorldCat) the predicate conc/3 is used instead of append/3. Also the book makes no mention of append/3 and IIRC the book definition has a flaw that causes people self-studying to ask questions in forums. As such if you are using his books and see conc/3, use append/3 from the Prolog built-in library of your favorite version of Prolog.

This is not posted or to be interpreted as blaming anyone, see post, it is merely to suggest that if your code is using conc/3 and you can’t find the problem, then try using append/3 and if the problem is resolved then you know it was not your code.

I have a biased and somewhat negative opinion of the Bratko book. I tried to read it after reading “The Art of Prolog” by Sterling and Shapiro and I didn’t see the point of fighting my way through. I cannot recommend it to anyone.

PS: especially now that “The Art of Prolog” is available as a free PDF download.

Hmm, I definitely did not put this link there!

The real download can be found on the website of the book:

https://mitpress.mit.edu/books/art-prolog-second-edition

How can I preven Discourse from editing my links or even inserting links on my behalf? This isn’t the first time.

I think it is unfair to blame Bratko. In the past several Prolog systems provided member/2 and append/3 as built-in and thus if you wanted to learn novices how append/3 works, you might not be able to (re)define append/3. In current SWI-Prolog it is a normal library predicate. I vaguely recall that some ISO revision defines it as a built-in again. I never bothered following that as append/3 is autoloaded and thus available. It does still allow you to define it as something else though, which is nice for educational reasons as well as running old small programs that included their own implementation. Surely, normal programs should use as much as possible from the library.

I’m not sure we should learn novices very early how append/3 can be implemented. If you to though, it is not always a good advice to look in the library. Some predicates have quite awkward implementations for performance, safety against cyclic terms, determinism and other (sometimes historical) reasons. If you are just starting to learn Prolog this can be a bit too much :slight_smile:

1 Like

Thank you everyone.
@Boris: thank you, I did not know that (about :- )
@Ian: weird, it is the textbook definition (the one I have!).
@EricGT: thank you again for the long answer! Still processing it. What is : write_term([1,2,3],[dotlists(true)]). I don’t see where you defined it in your facts?

Yes I do feel like fainting right now. :scream::dizzy_face:

1 Like

It is an SWI-Prolog built-in predicate. See: write_term/2

1 Like

Which textbook are you using?

There are not many good textbooks on Prolog and odds are many of us here have the book on hand.

If you are doing an exercise from a book, please note the book and exercise so that we can reference it if we have the book to help us further understand what the author of the book is trying to teach with the exercise.

Sorry, It’s not a text book but an ad hoc paper.

Is there a public link to the paper?

No unfortunately, one need a login. But this is the append I used.

To prevent the unwanted choicepoint, can use Tail for first-element indexing as in indexing - Why does this predicate leave behind a choicepoint? - Stack Overflow