restricciones - Coincidencia de patrones: Prólogo vs. Haskell

restricciones multiples haskell

Question

Esta no es una pregunta de tarea, sino una pregunta de guía de estudio de examen. ¿Cuál es la diferencia entre la coincidencia de patrones en Prolog Vs Haskell?

Investigué un poco y leer las teorías que hay detrás de ellos realmente no me da una comprensión sólida entre los dos. Leí que en Prolog, la coincidencia de patrones es diferente porque tiene la capacidad de unificar variables y así poder deducir a través de la resolución y escupir la posible respuesta

eg ?- [a,b] = [a,X]
   X = b

Ahora no estoy seguro de cómo mostrar la coincidencia de patrones en Haskell. Sé que la misma consulta anterior que se muestra en Prolog no funcionará en Haskell porque Haskell no puede unificarse como Prolog. Recuerdo que para obtener la misma respuesta en Haskell, tienes que contarla explícitamente a través de los guardias.

Sé que estoy muy cerca de entenderlo, pero necesito que alguien me lo describa con estilo de Barney para poder entenderlo COMPLETAMENTE y explicárselo a un niño de 12 años. Esto me ha estado molestando por bastante tiempo y parece que no puedo encontrar una explicación sólida.

Por cierto, el ejemplo que se muestra arriba fue solo para mostrarles lo que he aprendido hasta ahora y que estoy tratando de encontrar una respuesta. Mi pregunta principal no se relaciona con los ejemplos anteriores, sino más bien con una comprensión completa de la diferencia entre los dos.

Answer 1

Agregando a la respuesta de LeleDumbo, podríamos decir que la unificación de Prolog construye términos y los deconstruye , mientras que en Haskell la fase de construcción es convenientemente exigida al valor devuelto.

Por supuesto, tal característica es lo que permite en Prolog puro los llamados predicados "bidireccionales", explotados por ejemplo en DCG, que con alguna restricción, se pueden usar tanto para analizar como para generar.

Answer 2

Aquí hay un ejemplo que encuentro interesante en Prolog para apoyar a @chac (+1 por cierto) mencione cómo la unificación de Prolog "construye" términos que encontramos en la etiqueta de prólogo ayer:

swapPairs([],       []).
swapPairs([X],      [X]).
swapPairs([X, Y|T], [Y, X|R]) :- swapPairs(T, R).

Este predicado casi no tiene "cuerpo". Solo utiliza la unificación de sus argumentos en su cabeza y la recursión.

Como lo señalan @chac y @LeleDumbo, eso se debe a que la unificación de Prolog es "bidireccional".

Esto es lo que dice Una suave introducción a Haskell al respecto:

La coincidencia de patrones en Haskell es diferente de la que se encuentra en los lenguajes de programación lógica como Prolog; en particular, se puede ver como una coincidencia "unidireccional", mientras que Prolog permite la coincidencia "bidireccional" (mediante la unificación), junto con el retroceso implícito en su mecanismo de evaluación.

Answer 3

La coincidencia de patrones Prolog se basa en la unificación, específicamente el algoritmo Martelli-Montanari (menos la comprobación de ocurrencias, por defecto). Este algoritmo coincide con valores de la misma posición, vinculando variables de un lado a un valor en la posición correspondiente del otro lado. Este tipo de coincidencia de patrones podría funcionar en ambos sentidos, por lo tanto, en Prolog podría usar argumentos como entrada y salida. Un ejemplo simple, el predicado de length/2 . Podríamos usar esto para (el comentario explica la consulta):

?- length([],0).      % is the length of empty list zero?
?- length([a,b,c],X). % what''s the length of list consisting of a,b and c?
?- length(L,5).       % give me all lists that have length of 5

La coincidencia de patrones Haskell es una coincidencia unidireccional, para vincular variables a diferentes partes de un valor dado. Una vez encuadernado, lleva a cabo la acción correspondiente (el lado derecho). Por ejemplo, en una llamada a función, la coincidencia de patrones puede decidir a qué función llamar. p.ej:

sum []     = 0
sum (x:xs) = x + sum xs

la primera suma vincula la lista vacía, mientras que la segunda liga una lista de al menos 1 elemento. En base a esto, dada la sum <a list> , el resultado podría ser 0 o x + sum xs dependiendo de si sum <a list> coincide con sum [] o sum (x:xs) .

Answer 4

La diferencia entre la coincidencia de patrones como en Haskell y la unificación de Prolog surge del papel fundamentalmente diferente de las variables en ambos idiomas.

En Haskell, las variables tienen valores. Valores concretos Tal valor podría no haber sido calculado aún , e incluso podría ser ⊥, pero de lo contrario es un valor concreto. En Haskell no puedes tomar una variable y solo declarar primero algunas propiedades de su valor.

Entonces la coincidencia de patrones siempre significa que un valor concreto se compara con un patrón que contiene algunas variables. El resultado de tal coincidencia es la falla o un enlace de las variables a valores concretos. En Haskell esto se restringe aún más para evitar la necesidad de una comparación general, lo que implicaría que la clase Eq se define para los términos que coinciden.

En Prolog, sin embargo, las variables pueden referirse a un conjunto de posibles soluciones. Las variables pueden ocurrir en cualquier lugar, también en algún lugar entre otros valores. La unificación ahora asegura que las igualdades establecidas todavía se mantienen y el resultado se representa de manera óptima, es decir, se calcula el unificador más general.

| ?- length(L,5).                      
L = [_,_,_,_,_]
| ?- length(L,5), maplist(=(E),L).
L = [E,E,E,E,E]

Así que Prolog no responde aquí con valores concretos como L = [1,1,1,1,1] o L = [[],[],[],[],[]] pero ofrece el unificador más general como respuesta que contiene todos esos valores concretos.

Answer 5

Nadie mencionó la siguiente diferencia muy importante. La coincidencia de patrones en Prolog se prueba para cada cláusula de un predicado, incluso si una de las coincidencias anteriores tuvo éxito (a menos que se detenga en un corte ). Pero en Haskell, la coincidencia de patrones en cláusulas solo se intenta hasta el primer éxito . No se intentan otras alternativas (a menos que el partido haya sido rechazado por un guardia ).

La coincidencia de patrones de Prolog establece una restricción de igualdad en el sentido más general (ver respuesta por @false para más detalles). Compartir es explícito : A=B, A=5 establece B=5 también. Esto es posible porque el logvar de Prolog puede estar en un estado aún no configurado (es decir, no se ha iniciado ). Esto hace que atar sea un nudo fácil (una técnica de programación básica en realidad, a saber, listas de diferencias ).

En Haskell, cualquier variable puede definirse solo una vez en el nivel de sintaxis . En Prolog, un logvar también se establece una sola vez (sin backtracking ), pero se puede apuntar a una estructura incompleta (datos), donde los agujeros están representados por otros logvars aún no instanciados que se pueden establecer en cualquier momento posterior. .

En Haskell, una estructura dada definida con recursión protegida se desarrolla progresivamente según lo exija el acceso. En Prolog, después de la instanciación inicial de una variable, cualquier posterior unificación se convierte en verificación de la compatibilidad de los términos y posible instanciación posterior (quizás parcial una vez más) ("llenando" los agujeros explícitamente ).