Counting the number of elements in a list: how affectation works

Question

I was working on a Prolog problem consisting in counting the number of elements of a list:

count([], 0).
count([H|T], N) :-
    count(T, X),
    N is X+1,
    N > 0.

I can understand why it's written like that but I don't understand why we can't replace N is X+1 by X is N-1 ?

Thanks a lot!

Preconcert

Minor nit: affectation means rather assignment. – Jalisajalisco

Answer 1

Your question is very legitimate, +1.

The reason for this seemingly arbitrary choice is that (is)/2 is a comparatively low-level predicate and only works in very specific cases that can only be understood procedurally, not declaratively. Therefore, (is)/2 is extremely hard to understand for beginners and should better be avoided because it destroys many relational properties we want to enjoy when using Prolog.

The declarative solution is to use constraints, where you can do exactly what you say. For relations over integers, simply replace (is)/2 by (#=)/2 to enjoy the relational properties you intuitively expect.

For example, using GNU Prolog:

count([], 0).
count([_|Ls], N) :-
        count(Ls, X),
        X #= N - 1,
        N #> 0.

In other systems like SICStus Prolog and SWI, you currently still need to use library(clpfd) for this. In addition, I highly recommend a more declarative name for this relation, making clear which argument denotes what:

:- use_module(library(clpfd)).

list_length([], 0).
list_length([_|Ls], N) :-
        list_length(Ls, X),
        X #= N - 1,
        N #> 0.

Sample queries:

?- list_length([_,_,_], N).
N = 3.

?- list_length(Ls, 2).
Ls = [_G602, _G605] .

I leave improving the termination properties of this predicate as an easy exercise.

Finley

Thanks for your detailed answer mat! At the beginning of your answer, you said that (is)/2 works in very specific cases. Do you know where I could find more informations about this ? In the SWI-Prolog website, it says that it should be used with unbound left operand, but it's not very clear to me (In my lessons, it says "The right-hand term should be fully instantiated at the time of the call."). – Preconcert

It's no wonder that this is not very clear for you: Especially as a beginner, you have almost no chance to understand how (is)/2 must be used. For later reference, I only let you know that its right-hand side must be fully instantiated, and its left-hand side should be a variable at the time the goal is called (ugh!). But why even bother with this logic hacking instead of logic programming? Use (#=)/2 and (#>)/2 throughout, and enjoy the relational nature of these predicates, which are usable in all directions. I have added more explanations about this to my answer. – Finley