Соответствие шаблону - Пролог против Хаскелла

Это не вопрос, связанный с домашним заданием, а вопрос об экзамене. В чем разница между совпадением шаблонов в Prolog Vs Haskell?

Я провел некоторое исследование и прочитал теории, стоящие за ними, на самом деле не дает мне надежного понимания между ними. Я читал, что в Prolog сопоставление шаблонов отличается тем, что имеет возможность унифицировать переменные и, следовательно, иметь возможность выводить через разрешение и выплевывать возможный ответ

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

Теперь я не уверен, как отобразить совпадение шаблонов в Haskell. Я знаю, что тот же самый запрос, показанный в Prolog, не будет работать в Haskell, потому что Haskell не может объединиться, как Prolog. Я где-то помню, чтобы получить тот же ответ в Haskell, вы должны явно рассказать об этом через охранников.

Я знаю, что я очень близка к пониманию этого, но мне нужен кто-то, чтобы сломать стиль Барни для меня, чтобы я мог ПОЛНОСТЬЮ понять это и объяснить его 12-летнему. Это довольно долго меня подтачивало, и я не могу найти убедительного объяснения.

Кстати, приведенный выше пример был просто для того, чтобы показать вам, ребята, что я узнал до сих пор, и что я на самом деле пытаюсь найти ответ. Мой главный вопрос не относится к приведенным выше примерам, а скорее к полному пониманию различий между ними.

Ответ 1

Согласование шаблонов Prolog основано на унификации, в частности, Мартелли-Монтанари-алгоритм (за вычетом проверки происходит по умолчанию). Этот алгоритм сопоставляет значения одной и той же позиции, связывающие переменные с одной стороны со значением в соответствующей позиции с другой стороны. Такое сопоставление шаблонов может работать в обоих направлениях, поэтому в Prolog вы можете использовать аргументы как входные, так и выходные. Простой пример, предикат length/2. Мы могли бы использовать это для (комментарий объясняет запрос):

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

Совпадение шаблонов Haskell - это одностороннее совпадение, привязка переменных к различным частям заданного значения. После привязки он выполняет соответствующее действие (правая сторона). Например, при вызове функции сопоставление шаблонов может решить, какую функцию вызывать. например:.

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

первая сумма связывает пустой список, а вторая связывает список по меньшей мере из 1 элемента. Исходя из этого, с учетом sum <a list> результат может быть либо 0, либо x + sum xs в зависимости от того, соответствует ли sum <a list> sum [] или sum (x:xs).

Ответ 2

Различие между сопоставлением шаблонов, как и в объединении Haskell и Prolog, проистекает из принципиально иной роли переменных на обоих языках.

В Haskell переменные сохраняют значения. Конкретные значения. Такое значение, возможно, еще не было вычислено, и это может быть даже ⊥, но в остальном это одно конкретное значение. В Haskell вы не можете взять переменную и сначала указать некоторые свойства ее значения.

Таким образом, соответствие шаблонов всегда означает, что конкретное значение сопоставляется с шаблоном, который содержит некоторые переменные. Результатом такого сопоставления является либо отказ, либо привязка переменных к конкретным значениям. В Haskell это дополнительно ограничивается, чтобы избежать необходимости общего сравнения, что подразумевало бы, что класс Eq определяется для согласованных терминов.

Однако в Prolog переменные могут ссылаться на набор возможных решений. Переменные могут встречаться где угодно - также где-то между другими значениями. Унификация теперь гарантирует, что указанные равенства все еще сохраняются, и результат представляется оптимально, т.е. Вычисляется наиболее общий унификатор.


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

Таким образом, Prolog не отвечает здесь конкретными значениями, такими как L = [1,1,1,1,1] или L = [[],[],[],[],[]], но дает самый общий унификатор в качестве ответа, который содержит все эти конкретные значения.

Ответ 3

Никто не упомянул следующее очень важное различие. Сравнение шаблонов в Prolog проверяется для каждого предложения предиката, даже если одно из предыдущих совпадений выполнено успешно (если не остановлено сокращение). Но в шаблоне Haskell для сопоставления по предложениям используется только до первого успеха. Никакие другие альтернативы не рассматриваются (если матч не был отклонен охранником).

Сопровождение шаблона Prolog устанавливает ограничение равенства в самом общем смысле (подробнее см. ответ @false). Совместное использование явно: A=B, A=5 устанавливает B=5. Это возможно, потому что логвар журнала Prolog может находиться в еще не установленном состоянии (т.е. Неинстантированном). Это упрощает привязку (простой метод программирования, а именно списки различий).

В Haskell любая переменная разрешается определять только один раз на уровне синтаксиса. В Prolog логарифм устанавливается только один раз тоже (без возврата), но ему разрешено указывать неполную структуру (данные), где дыры представлены другими не-показуемыми логарифмами, которые могут быть установленный в любой более поздний момент времени.

В Haskell данная структура, определенная с охраняемой рекурсией, постепенно сглаживается по требованию доступа. В Prolog после первоначальной инстанцирования переменной любая последующая унификация превращается в проверку совместимости терминов и возможного далее (возможно, частично снова) ( "заполнение" дырки явно).

Ответ 4

Добавляя к ответу LeleDumbo, можно сказать, что объединение Prolog строит термины, а также деконструирует их, в то время как в Haskell фазе сборки обычно требуется вернуть значение.

Конечно, такая функция позволяет в чистом Prolog так называемые "двунаправленные" предикаты, используемые, например, в DCG, которые с некоторым ограничением могут использоваться как для синтаксического анализа, так и для генерации.

Ответ 5

Вот пример, который я нахожу интересным в Prolog для поддержки упоминания @chac (+1 кстати) о том, как объединение Prolog "строит" термины, с которыми мы столкнулись вчера в теге пролога:

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

В этом предикате почти нет "тела". Он использует только объединение своих аргументов в своей голове и рекурсию.

Как указано как @chac, так и @LeleDumbo, это потому, что объединение Prolog является "двусторонним".

Вот что говорит об этом нежное введение в Haskell:

Сравнение шаблонов в Haskell отличается от того, что найдено в логике языки программирования, такие как Prolog; в частности, его можно просмотреть как "одностороннее" совпадение, тогда как Prolog позволяет "двустороннее" соответствие (через унификация), а также неявное отступление в его оценке механизм.