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

Question

I worked on the Prolog problem, which is counting the number of list items:

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

I can understand why it is written this way, but I don’t understand why we cannot replace N on X + 1 with X - 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 relatively low-level predicate and works only in very specific cases, which can only be understood procedurally and not declaratively. Therefore, (is)/2 extremely difficult to understand for beginners, and should be avoided since it destroys many of the relational properties that we want to use when using Prolog.

A declarative solution is to use constraints , where you can do exactly what you say. For relationships over whole words, just replace (is)/2 with (#=)/2 to take advantage of the relational properties you intuitively expect.

For example, using the GNU Prolog:

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

On other systems, such as SICStus Prolog and SWI, you still need to use library(clpfd) . In addition, I highly recommend a more declarative name for this relationship, making it clear which argument means that:

  : - use_module (library (clpfd)).

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

Request examples:

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

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

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