listing - prolog examples

Asignación Prolog

Question

Esta es la pregunta para una de mis tareas:

Escriba repCount(L, X, N) que es verdadero cuando N es el número de ocurrencias de X en la lista L

Aquí está mi código donde intento abordar el problema recursivamente:

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

Y funciona cuando proporciono una lista llena de números idénticos como este:

?- repCount([2,2,2], 2, N).
N = 3.

Pero si proporciono una lista con al menos un valor diferente:

?- repCount([2,2,22], 2, N).
false.

Devuelve false . No puedo entender por qué sucede esto ni cómo cambiarlo para ''omitir'' el valor que no coincide, en lugar de declararlo como falso. Cualquier entrada es apreciada.

Answer 1

Casi allí ... necesitas usar un acumulador , así:

repCount(Xs,Y,N) :-
count(Xs,Y,0,N) % the 3rd argument is the accumulator for the count, which we seed as 0
.
count([],_,N,N). % if the list is empty, unify the accumulator with the result
count([X|Xs],Y,T,N) :- % if the list is non-empty,
X == Y , % and the head of the list (X) is the the desired value (Y),
T1 is T+1 , % then increment the count, and
count(Xs,Y,T1,N) % recurse down, passing the incremented accumulator
. %
count([X|Xs],Y,T,N) :- % if the list is non-empty,
X /== Y , % and the head of the list(X) is not the desired value (Y),
count(Xs,Y,T,N) % simply recurse down
. %

Answer 2

La pregunta original no decía si había restricciones sobre qué predicados podrías usar.

Si se le permite ''hacer trampa'', es decir. utilice predicados de orden superior como ''findall'' que recurse para usted. Si realiza la recursión usted mismo, esto puede hacerse en un solo predicado:

repCount(L, X, N) :-
findall(X, member(X, L), ListOfX),
length(ListOfX, N).

Answer 3

Pero suponiendo que no se le permite ''hacer trampas'', si desea usar recursión, no necesita hacer la comparación ''==''. Puede usar la unificación de variables de Prolog para alcanzar el mismo fin:

% Job done all instances
repCount2([], _, 0).
% Head unifies with X/2nd parameter - ie X found
repCount2([H|T], H, N) :-
repCount2(T, H, NewN),
N is NewN + 1.
% We got here, so X not found, recurse around
repCount2([_|T], X, N) :-
repCount2(T, X, N).

En el segundo predicado, H se menciona dos veces, lo que significa que si el encabezado de la lista es igual a X, entonces recurse hacia abajo, luego agregue 1 al resultado del resto de la recursión (que termina en agregar 0 - el caso base , que es cómo se construye el acumulador).

Answer 4

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

aquí declaras que N debería ser N1 + 1 si X es H; Sin embargo, no define lo que debería suceder si X no es H (básicamente falta una cláusula else), esto debería funcionar:

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

otra forma sería:

count([H|T], X, N):- count(T, X, N1), X=:=H, N is N1 + 1.
count([H|T], X, N):- X=/=H, count(T, X, N1), N is N1.

pero esto es ineficiente ya que el conteo (T, X, N1) se llamará dos veces si X no es H. podemos solucionarlo haciendo el control en el encabezado de la cláusula:

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

o simplemente: count ([H | T], H, N): - count (T, X, N1), N es N1 + 1.

count([H|T], X, N1):- X=/=H, count(T, X, N1).

Answer 5

Una adición quizás interesante a lo que @magus escribió: Si solo te importa la cantidad de elementos en lugar de los elementos en sí, puedes usar findall / 3 así:

list_elem_num(Ls, E, N) :-
findall(., member(E, Ls), Ds),
length(Ds, N).

Answer 6

Preserve la pureza lógica con una pequeña ayuda de meta-predicate tcount/3 y (=)/3 !

El objetivo tcount(=(X),Es,N) dice "hay N elementos en la lista Es que son iguales a X".

Consulta de muestra:

?- tcount(=(X), [a,b,c,a,b,c,a,b,a], N). ( N = 4, X=a ; N = 3, X=b ; N = 2, X=c ; N = 0, dif(X,a), dif(X,b), dif(X,c) ). % terminates universally