Различия между сопоставлением шаблонов и объединением?

Question

Мне показалось, что я понимаю, как совпадение шаблонов, найденное в Scala и Haskell, отличается от унификации, найденной в Prolog, но мои непонимания Prolog великолепны. Какие простые проблемы решаются теми, которые не могут быть решены другим? Спасибо

Answer 1

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

X = Y, 
X = 5, 
%% Y = 5 now as well 

В Erlang (который использует шаблон-сопоставление с синтаксисом рядом с Пролога), линия X = Y будет выдавать ошибку: variable 'Y' is unbound. Обратите внимание, что X является несвязанным в порядке: он должен быть сопоставлен с образцом.

Это может быть полезно, если вы хотите иметь дело с частично определенными значениями. Очень хороший пример: difference lists.

Это также позволяет использовать предикат Prolog в нескольких режимах. Например. в Scala/Haskell/Erlang, если вы хотите 1) найти A ++ B, 2) решить уравнение A ++ X == B или 3) решить уравнение X ++ A == B для данных списков A и B, вам необходимо написать 3 отдельные функции; в Prolog все эти задания (и многое другое!) выполняются одним предикатом.

Answer 2

В Scala не удалось скомпилировать, так как это первая ветвь case пытается объявить переменную x дважды.

(1, 1) match{ 
    case (x, x) => println("equals") 
    case _  => println("not equals") 
} 

Если Scala используется объединение вместо шаблону это будет иметь успех и печать «равно», а

(1, 2) match{ 
    case (x, x) => println("equals") 
    case _  => println("not equals") 
} 

напечатает «не равно». Это связано с тем, что унификация потерпит неудачу при попытке привязать переменную x как к 1, так и к 2.

Answer 3

В Прологе, вы можете добавить [3] [1,2], как это:

?- append([1,2], [3], Z). 
Z = [1, 2, 3]. 

Аккуратная вещь об объединении является то, что вы можете использовать один и тот же код (внутреннее определение понятия «Append»), но вместо того, чтобы найти второй аргумент, необходимый для получения результата от первого аргумента:

?- append([1,2], Y, [1,2,3]). 
Y = [3]. 

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

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

Answer 4

Я думаю, что это полезно для формализации понятия, вместо того, чтобы смотреть на определенном языке. Matching и унификация являются фундаментальные понятия, которые используются в более контекстах, чем сопоставление с образцом и пролога.

• Термин s ссылок т, тогда и только тогда происходит подмена фи таким образом, что фи (ы) = т
• термин сек объединяет с термином т, тогда и только тогда существует подстановка такая, что фи (ы) = фи (т)

Для примера рассмотрим члены s = f (Y, a) и t = f (a, X) где X, Y - переменные, a - постоянная. s не соответствует t, потому что мы не можем универсально количественно определить константу a. Однако существует унификатор для s и t: phi = {X \ a, Y \ a}