recursion prolog tail-recursion accumulator

recursion - Acumuladores Prolog. ¿Son realmente un concepto "diferente"?



tail-recursion accumulator (3)

Estoy aprendiendo Prolog en mi Laboratorio de Inteligencia Artificial, de la fuente ¡ Aprenda Prólogo Ahora! .

En el Capítulo V, llegamos a aprender sobre los Acumuladores . Y a modo de ejemplo, se proporcionan estos dos fragmentos de código. Para encontrar la longitud de una lista

sin acumuladores :

len([],0). len([_|T],N) :- len(T,X), N is X+1.

con acumuladores :

accLen([_|T],A,L) :- Anew is A+1, accLen(T,Anew,L). accLen([],A,A).

No puedo entender, ¿cómo los dos fragmentos son conceptualmente diferentes? ¿Qué hace exactamente un acumulador diferente? Y cuales son los beneficios?

Los acumuladores suenan como variables intermedias . (Corrígeme si estoy equivocado.) Y ya los había usado en mis programas hasta ahora, ¿así que es realmente ese gran concepto?

Los acumuladores son variables intermedias, y son un tema importante (leer básico ) en Prolog porque permiten invertir el flujo de información de algún algoritmo fundamental, con importantes consecuencias para la eficiencia del programa.

Tome la inversión de una lista como ejemplo

nrev([],[]). nrev([H|T], R) :- nrev(T, S), append(S, [H], R). rev(L, R) :- rev(L, [], R). rev([], R, R). rev([H|T], C, R) :- rev(T, [H|C], R).

nrev / 2 (reverso ingenuo) es O (N ^ 2), donde N es la longitud de la lista, mientras que rev / 2 es O (N).

Cuando le das un nombre a algo, de repente se vuelve más real de lo que solía ser. Discutir algo ahora se puede hacer simplemente usando el nombre del concepto. Sin llegar a ser más filosófico, no, no hay nada especial acerca de los acumuladores, pero son útiles.

En la práctica, pasando por una lista sin un acumulador:

foo([]). foo([H|T]) :- foo(T).

El encabezado de la lista queda atrás y no se puede acceder mediante la llamada recursiva. En cada nivel de recursión solo ve lo que queda de la lista.

Usando un acumulador:

bar([], _Acc). bar([H|T], Acc) :- bar(T, [H|Acc]).

En cada paso recursivo, tiene la lista restante y todos los elementos por los que ha pasado. En su ejemplo len/3 , solo conserva el recuento, no los elementos reales, ya que esto es todo lo que necesita.

Algunos predicados (como len/3 ) pueden ser recursivos de cola con acumuladores: no es necesario esperar al final de su entrada (agotar todos los elementos de la lista) para hacer el trabajo real, en lugar de hacerlo incrementalmente como usted obtener la entrada. Prolog no tiene que dejar valores en la pila y puede hacer la optimización de la cola de llamadas por usted.

Los algoritmos de búsqueda que necesitan conocer la "ruta hasta el momento" (o cualquier algoritmo que necesite tener un estado) usan una forma más general de la misma técnica, proporcionando un "resultado intermedio" a la llamada recursiva. Un codificador de longitud de ejecución, por ejemplo, podría definirse como:

rle([], []). rle([First|Rest],Encoded):- rle_1(Rest, First, 1, Encoded). rle_1([], Last, N, [Last-N]). rle_1([H|T], Prev, N, Encoded) :- ( dif(H, Prev) -> Encoded = [Prev-N|Rest], rle_1(T, H, 1, Rest) ; succ(N, N1), rle_1(T, H, N1, Encoded) ).

Espero que ayude.

TL; DR : sí, lo son.

Imagine que debe ir de una ciudad A a la izquierda a una ciudad B a la derecha, y desea saber la distancia entre las dos con anticipación. ¿Cómo vas a lograr esto?

Un matemático en tal posición emplea la magia conocida como recursión estructural . Se pregunta a sí mismo qué pasaría si le doy un paso más a la ciudad B y le pregunto si está lejos de la ciudad. Luego agregaré 1 a su resultado, después de recibirlo de mi copia, ya que lo he enviado un paso más hacia la ciudad, ¡y sabré mi respuesta sin haberme movido una pulgada! Por supuesto, si ya estoy en las puertas de la ciudad, no enviaré ninguna copia de mí a ninguna parte, ya que sabré que la distancia es 0, ¡sin haber movido ni una pulgada!

¿Y cómo sé que mi copia de mí tendrá éxito? Simplemente porque seguirá las mismas reglas exactas, mientras comienza desde un punto más cercano a nuestro destino. Cualquiera que sea el valor de mi respuesta, la suya será una menos, y solo un número finito de copias de nosotros será llamado a la acción, porque la distancia entre las ciudades es finita. Entonces la operación total seguramente se completará en un tiempo finito y obtendré mi respuesta. Debido a que obtener su respuesta después de un tiempo infinito ha pasado, no la está consiguiendo en absoluto, nunca.

Y ahora, después de haber encontrado su respuesta por adelantado, nuestro cauteloso matemático mago está listo para embarcarse en su viaje seguro (¡ahora!).

Pero eso, por supuesto, no era magia en absoluto, ¡todo era un sucio truco! No descubrió la respuesta de antemano de la nada: envió toda la pila de otros para encontrarla. El trabajo agotador tenía que hacerse después de todo, solo fingía no darse cuenta. La distancia fue recorrida. Además, también era necesario viajar la distancia atrás , para que cada copia diga su resultado a su maestro, y el resultado se crea realmente en el camino de regreso desde el destino. Todo esto antes de que nuestro mago falso alguna vez hubiera empezado a caminar solo. ¿Cómo es eso para un esfuerzo de equipo? Para él , podría parecer una buena oferta. Pero en general...

Así es como piensa el mago matemático . Pero su doble, el valiente viajero, simplemente hace un viaje y cuenta sus pasos a lo largo del camino, agregando 1 al contador de pasos actual en cada paso, antes del resto de su viaje real. Ya no hay pretensiones. El viaje puede ser finito, o puede ser infinito; no tiene forma de saber por adelantado. Pero en cada punto de su ruta, y por lo tanto cuando / si llega a las puertas de la ciudad B también, sabrá su distancia recorrida hasta el momento. Y ciertamente no tendrá que retroceder hasta el comienzo del camino para decirse el resultado.

Y esa es la diferencia entre la recursión estructural de la primera, y la recursividad de la cola con el acumulador / recursivo de la cola módulo cons / corecursion empleado por la segunda. El conocimiento del primero se construye en el camino de regreso desde la meta; del segundo - en el camino desde el punto de partida, hacia la meta.

ver también:

¿Cuáles son las implicaciones prácticas de todo esto, preguntas? Por qué, imagina a nuestro amigo el mago matemático que necesita hervir algunos huevos. Él tiene una olla; un grifo; un plato caliente; y algunos huevos ¿Qué es él para hacer?

Bueno, es fácil: pondrá huevos en la olla, agregará agua del grifo y la colocará en el plato caliente.

¿Y si ya le dieron una olla con huevos y agua? ¡Por qué es aún más fácil para él, simplemente sacará los huevos, verterá el agua y terminará con el problema que ya sabe cómo resolver! Magia pura, ¿no es así?

Antes de reírnos del pobre muchacho, no debemos olvidar la historia del ciempiés . A veces la ignorancia es felicidad. Pero cuando el conocimiento requerido es simple y "unidimensional", como la distancia aquí, sería un delito pretender que no tiene memoria en absoluto.