La Coincidencia de patrón - Prólogo vs Haskell

La diferencia entre la coincidencia de patrones como en Haskell y la unificación de Prolog se deriva 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 todavía, e incluso podría ser ⊥, pero de lo contrario es un valor concreto. En Haskell no se puede tomar una variable y solo indicar primero algunas propiedades de su valor.

Así que la coincidencia de patrones siempre significa que un concreto el valor se compara con un patrón que contiene algunas variables. El resultado de tal coincidencia es un fallo o una unión 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 se comparan.

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 declaradas 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 = [[],[],[],[],[]] sino que da el unificador más general como una respuesta que contiene todos esos valores concretos.

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

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

En Haskell, cualquier variable se puede definir solo una vez en el nivel de sintaxis . En Prolog un logvar es establecer solo una vez también (sans backtracking), pero se permite 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 exige el acceso. En Prolog, después de la instanciación inicial de una variable, cualquier unificación posterior se convierte en verificación de la compatibilidad y posible además (quizás parcial una vez más) instanciación ("llenar" los agujeros explícitamente).

Añadiendo a la respuesta de LeleDumbo, podríamos decir que Prolog unification construye términos así como los deconstruye, mientras que en Haskell la fase de compilación se exige convenientemente al valor devuelto.

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

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

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

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

Como señalan @chac y @LeleDumbo, eso es porque la unificación de Prolog es "en ambos sentidos".

Esto es lo que Una introducción suave a Haskell dice sobre it:

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