Verificamos de forma cada escrito en nuestro espacio con el objetivo de enseñarte en todo momento la información con la mayor veracidad y actual.
Solución:
Cuando das algo a nombre, de repente se vuelve más real de lo que solía ser. Ahora se puede discutir algo simplemente usando el nombre del concepto. Sin ponerme más filosófico, no, no hay nada especial sobre acumuladores, pero son útiles.
En la práctica, revisando una lista sin acumulador:
foo([]).
foo([H|T]) :-
foo(T).
El encabezado de la lista se deja atrás y la llamada recursiva no puede acceder a él. En cada nivel de recursividad, solo verá lo que queda de la lista.
Usando un acumulador:
bar([], _Acc).
bar([H|T], Acc) :-
bar(T, [H|Acc]).
En cada paso recursivo, tienes la lista restante y todos los elementos por los que has pasado. En tus len/3 Por ejemplo, solo mantiene el recuento, no los elementos reales, ya que esto es todo lo que necesita.
Algunos predicados (como len/3) se puede hacer de cola recursiva con acumuladores: no necesita esperar al final de su entrada (agotar todos los elementos de la lista) para hacer el trabajo real, sino hacerlo de forma incremental a medida que obtiene la entrada. Prolog no tiene que dejar valores en la pila y puede realizar la optimización de la llamada final por usted.
Los algoritmos de búsqueda que necesitan conocer la “ruta hasta ahora” (o cualquier algoritmo que necesite tener un estado) utilizan 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.
Imagina que te vas de una ciudad A a la izquierda a una ciudad B a la derecha, y desea saber la distancia entre los dos de antemano. ¿Cómo vas a lograr esto?
A matemático en tal posición emplea magia conocida como recursividad estructural. Se dice a sí mismo, ¿y si le envío mi propia copia un paso más cerca? hacia la ciudad B, y pregunta eso de su distancia a la ciudad? Luego agregaré 1 a su resultado, después recibirlo de mi copia, ya que lo he enviado uno paso más cerca hacia la ciudad, y sabré mi respuesta sin haberme movido ni un centímetro! Por supuesto, si ya estoy en las puertas de la ciudad, no enviaré copias mías a ninguna parte, ya que sabré que la distancia es 0, ¡sin haberme movido ni una pulgada!
Y como se que mi copia-de-mi ¿podría suceder? Simplemente porque seguirá las mismas reglas exactas, mientras comienza desde un punto más cerca a nuestro destino. Cualquiera que sea el valor de mi respuesta, su será uno menos, y solo un número finito de copias de nosotros entrarán en acción, porque la distancia entre las ciudades es finita. De modo que la operación total seguramente se completará en una cantidad finita de tiempo y yo voluntad obtén mi respuesta. Porque obtener tu respuesta después de que haya pasado un tiempo infinito, no es obtenerla en absoluto, nunca.
Y ahora, habiendo averiguado su respuesta de antemano, nuestro cauteloso mago matemático está listo para embarcarse en su viaje seguro (¡ahora!).
Pero eso, por supuesto, no fue magia en absoluto, ¡es todo un truco sucio! No descubrió la respuesta por adelantado de la nada: ha enviado todo el apilar de otros para encontrarlo por él. El trabajo agotador tenía que hacerse después de todo, simplemente fingió no ser consciente de ello. La distancia era viajado. Además, la distancia espalda tenía que viajar también, para que cada copia le dijera su resultado a su maestro, el resultado se creó realmente en el camino espalda desde el destino. Todo esto antes de que nuestro falso mago comenzara a caminar él mismo. Como esta ese por un esfuerzo en equipo. Para él podría parecer un buen trato. Pero en general…
Así es como piensa el matemático mago. Pero su doble el valiente viajero simplemente emprende un viaje y cuenta sus pasos a lo largo del camino, sumando 1 a el contador de pasos actual en cada paso, antes de el resto de su viaje real. Ya no hay pretensión. El viaje puede ser finito o puede ser infinito; no tiene forma de saberlo por adelantado. Pero en cada punto de su ruta y, por tanto, cuando ⁄ si llega a la ciudad B puertas también, sabrá la distancia recorrida hasta ahora. Y ciertamente no tendrá que retroceder hasta el comienzo del camino para decirse a sí mismo el resultado.
Y esa es la diferencia entre la recursividad estructural del primero y recursividad de la cola con acumulador ⁄ recursión de la cola módulo contras ⁄ corecursion empleado por el segundo. El conocimiento del primero se construye en el camino de regreso. de la meta; del segundo – en camino adelante desde el punto de partida, hacia la meta. los viaje es el destino.
ver también:
- Informe técnico TR19: Desenrollar recursiones estructuradas en iteraciones.
Daniel P. Friedman y David S. Wise (diciembre de 1974).
¿Cuáles son las implicaciones prácticas de todo esto, te preguntarás? Imagina a nuestro amigo el mago matemático necesita hervir algunos huevos. Tiene una olla; un grifo; un plato caliente; y unos huevos. ¿Qué va a hacer él?
Bueno, es fácil: simplemente pondrá huevos en la olla, agregará un poco de agua del grifo y lo pondrá en el plato caliente.
¿Y si ya le han dado una olla con huevos y agua? Vaya, 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. Puro magia, ¿no es así?
Antes de reírnos del pobre muchacho, no debemos olvidar la historia del ciempiés. A veces ignorancia es felicidad. Pero cuando el conocimiento requerido es simple y “unidimensional” como la distancia aquí, sería un crimen fingir no tener memoria en absoluto.
acumuladores están variables intermedias, y están un importante (leer básico) tema en Prolog porque permiten revertir el flujo de información de algún algoritmo fundamental, con importantes consecuencias para el eficiencia Del programa.
Tome como ejemplo invertir una lista
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 (inversa ingenua) es O (N ^ 2), donde N es la longitud de la lista, mientras que rev / 2 es O (N).
Si para ti ha sido de provecho este post, agradeceríamos que lo compartas con otros seniors de esta manera nos ayudas a difundir nuestro contenido.