recursion - Búsqueda recursiva y acumuladores y contadores en Prolog

counter accumulator

Question

Después de una larga búsqueda en google, no pude encontrar una respuesta clara a esto: en Prolog, la recursividad por sí misma es fácil. Mi principal problema es entender dónde colocar los acumuladores y los contadores. Aquí hay un ejemplo:

nXlist(N,X,[X|T]):-
    N /=0,
    N1 is N-1,
    nXList(N1,X,T).
nXList(0,_,[]).

media([X|L], N, Soma):-
   media(L, N1, Soma1),
   N is N1 + 1,
   Soma is Soma1 + X.
media([], 0, 0).

En el primer ejemplo, utilicé un contador ANTES de la recursión, pero en el segundo ejemplo lo uso DESPUÉS. La razón por la que he hecho eso es porque lo intento y veo porque realmente no puedo entender por qué a veces es antes y a veces lo es después ...

Answer 1

Respuesta corta: puede colocar tales relaciones aritméticas antes y después. Al menos, si está utilizando restricciones en lugar de (is)/2 . La única diferencia puede ser en la terminación y errores.

Entonces veamos cómo sus predicados se pueden definir con restricciones:

:- use_module(library(clpfd)).

nXList(0,_,[]).
nXList(N,X,[X|T]):-
    N #> 0,
    N1 #= N-1,
    nXList(N1,X,T).

media([], 0, 0).
media([X|L], N, Soma):-
   N #> 0,
   N #= N1 + 1,
   Soma #= Soma1 + X,
   media(L, N1, Soma1).

Ahora puede usar estas definiciones de una manera mucho más general, por ejemplo:

?- nXList(3, X, T).
T = [X, X, X] ;
false.

?- media(Xs, 3, S).
Xs = [_A, _B, _C],
_D+_A#=S,
_C+_B#=_D ;
false.

... nXList/3 se puede expresar de forma más compacta mediante:

..., length(T, N), maplist(=(X), T), ...

Answer 2

Tal vez el punto central de tu pregunta esté en el preámbulo:

En Prolog, la recursividad es fácil

No es fácil , es obligatorio . No tenemos bucles, porque no tenemos una forma de controlarlos. Las variables se asignan una vez .

Por lo tanto, creo que la respuesta práctica es bastante simple: si el ''predicado'' (como es / 2) necesita un valor variable, conecte a tierra la variable antes de llamarlo.

Para mí, ayuda considerar un programa Prolog (un conjunto de cláusulas) como producciones gramaticales y argumentos de cláusulas como atributos, ya sea heredados (valores calculados antes del ''puntero de instrucción'') o sintetizados (valores calculados ''aquí'', para ser devueltos )

Answer 3

actualización: lo más importante, si la llamada recursiva no es la última, el predicado no es recursivo de cola. Por lo tanto, tener algo después de la llamada recursiva se debe evitar si es posible. Observe que ambas definiciones en la respuesta del usuario falso son recursivas de cola, y eso se debe precisamente al hecho de que las condiciones aritméticas allí se colocan antes de la llamada recursiva, en ambas. Eso es tan básico, que tenemos que hacer un esfuerzo para notarlo de manera explícita.

A veces contamos hacia abajo, a veces contamos. Discuto esto en otra respuesta detalladamente. Habla de acumuladores, befores y afters. :)

También hay algo llamado "asociatividad" de una operación (digamos, + ), donde

a+(b+(c+....)) == (a+b)+(c+...)

eso nos permite reagrupar y (parcialmente) calcular más pronto que tarde. Lo antes posible, pero no antes.