Contare il numero di elementi di una lista: come funziona affettazione

Question

stavo lavorando su un problema Prolog che consiste nel contare il numero di elementi di una lista:

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

posso capire il motivo per cui è scritto così, ma io non capisco perché non possiamo sostituire N è X + 1 di X è N-1?

Grazie mille!

Answer 1

La tua domanda è molto legittima, +1.

La ragione di questa scelta apparentemente arbitraria è che (is)/2 è un basso livello predicato comparativamente e funziona solo in casi molto specifici che possono essere comprese solo procedurale, non dichiarativo. Pertanto, (is)/2 è estremamente difficile da comprendere per i principianti e dovrebbe essere evitato perché distrugge molte proprietà relazionali di cui vogliamo godere quando utilizziamo Prolog.

La soluzione dichiarativa utilizza i limiti , dove è possibile fare esattamente ciò che si dice. Per le relazioni su interi, è sufficiente sostituire (is)/2 per (#=)/2 per godere delle proprietà relazionali che si prevede intuitivamente.

Ad esempio, utilizzando GNU   Prolog:

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

In altri sistemi come SICStus Prolog e SWI, è attualmente ancora bisogno di utilizzare library(clpfd) per questo. Inoltre, mi raccomando un nome più dichiarativo per questa relazione, rendendo chiaro che l'argomento denota ciò:

 
:- use_module(library(clpfd)). 

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

query di esempio:

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

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

lascio migliorare le proprietà di terminazione di questo predicato come un facile esercizio.