Сопоставление с образцом - Пролог против Хаскелла

Question

Это не домашнее задание, а вопрос к руководству по экзамену.В чем разница между сопоставлением с образцом в Прологе против Хаскелла?

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

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

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

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

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

Answer 1

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

?- 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

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

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

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

.

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

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