Counting within a list. Help me understand this co

Question

I found a 3 year old question that helps me count the number of occurrences of variables within a list. The question had the answer below. The code works. But I can't understand how, can someone help me make sense of this?

Here is the answer with the code I found, writing in quotation marks is part of the answer:

count([],X,0). 
count([X|T],X,Y):- count(T,X,Z), Y is 1+Z.
count([X1|T],X,Z):- X1\=X,count(T,X,Z).

'However note that the second argument X is supposed to be instantiated. So e.g. count([2,23,3,45,23,44,-20],23,C) will unify C with 2. If you want the count for every element use'

:- use_module(library(lists)).

count([],X,0).
count([X|T],X,Y):- count(T,X,Z), Y is 1+Z.
count([X1|T],X,Z):- X1\=X,count(T,X,Z)

countall(List,X,C) :-
   sort(List,List1),
   member(X,List1),
   count(List,X,C).

'Then you get'

 ?- countall([2,23,3,45,23,44,-20],X,Y).
   X = -20,
   Y = 1  ;
   X = 2,
   Y = 1 ;
   X = 3,
   Y = 1  ;
   X = 23,
   Y = 2  ;
   X = 44,
   Y = 1  ;
   X = 45,
   Y = 1  ;
   no

I am very new to Prolog, I only understand one part of this code, and it is this

sort(List,List1),
member(X,List1),

I would appreciate an explanation of this the whole thing, especially how Y is being printed.

Answer 1

About counting, first try to think about the meaning of the code.

list_member_occ([], _, 0).       % list is empty, 0 occurrences
list_member_occ([X|Xs], X, N) :- % list has the element at the head
    list_member_occ(Xs, X, N0),  % count number of elements in the tail
    succ(N0, N).                 % the number of occurrences is the
                                 % next natural number
list_member_occ([Y|Xs], X, N) :-
    dif(X, Y),                   % head and the element are different
    list_member_occ(Xs, X, N).   % occurrences in the tail of the list
                                 % is the total number

In this code, succ(N0, N) is (arguably) a better way to say "N is the natural number after N0" than N is N0 + 1. One reason is that succ/2 was meant to be used in every direction:

?- succ(2, 3).
true.

?- succ(X, 4).
X = 3.

?- succ(1, X).
X = 2.

... while is/2 should be used with unbound left operand. Take this query

?- list_member_occ([1,1,2,1], X, 3).

... for an example of N being a number instead of a free variable.

Using the predicate:

?- list_member_occ([1,2,1], X, N).
X = 1,
N = 2 ;
X = 2,
N = 1 ;
N = 0,
dif(X, 1),
dif(X, 2),
dif(X, 1).

One interesting property of dif/2, as opposed to \=/2, is that it imposes a constraint on the variable X in the last solution: X cannot, from now on, take any of the values 1, or 2.

For the reason why you get all answers using dif/2, consider:

?- X = Y. % unify X and Y and succeed
X = Y.

?- X \= Y. % succeed if you cannot unify X and Y
false.

?- dif(X, Y). % succeed if X and Y are and will be different
dif(X, Y).

When you use X \= Y, Prolog tries to unify its arguments and fails if the unification succeeds. This means that you only get the solution in which all free variables have been unified to each other, but you miss solutions where free variables are different from each other.

About the Y = ..., when you make a query at the top level, it reports to you all new variable bindings that were made during successful proofs of this query. As the most simple example:

Which numbers are between 3 and 5, both including?

?- between(3, 5, X).
X = 3 ;
X = 4 ;
X = 5.

You don't need, of course, to print out the values of X by hand; just type a semicolon to get the next answer. After the last answer you get a full stop and return to the ?- prompt.

About the sorting: it sorts the whole list, but only shows you the first 9 elements of the sorted list. See this FAQ page from SWI-Prolog. In a nutshell, the easiest is to type ; true after your query, to make sure that there is at least one choice point, and use w and p to switch between showing the whole term and only some of it.

?- string_chars("the quick brown fox jumps over the lazy dog", Cs), sort(Cs, S) ; true.
Cs = [t, h, e, ' ', q, u, i, c, k|...],
S = [' ', a, b, c, d, e, f, g, h|...] [write]
Cs = [t, h, e, ' ', q, u, i, c, k, ' ', b, r, o, w, n, ' ', f, o, x, ' ', j, u, m, p, s, ' ', o, v, e, r, ' ', t, h, e, ' ', l, a, z, y, ' ', d, o, g],
S = [' ', a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z] .

?- string_chars("the quick brown fox jumps over the lazy dog", Cs), sort(Cs, S) ; true.
Cs = [t, h, e, ' ', q, u, i, c, k, ' ', b, r, o, w, n, ' ', f, o, x, ' ', j, u, m, p, s, ' ', o, v, e, r, ' ', t, h, e, ' ', l, a, z, y, ' ', d, o, g],
S = [' ', a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z] [print]
Cs = [t, h, e, ' ', q, u, i, c, k|...],
S = [' ', a, b, c, d, e, f, g, h|...] .

Hope this helps.