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!

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.