Подтвердить что ты не робот

Можно ли написать пустой список как список различий в Prolog?

Пустые списки... странные, новичкам Пролога, как я. Я бы сказал, что невозможно написать пустой список [] как список различий T1-T2 так же, как невозможно записать атом как список различий. Однако я бы предположил, что для использования рекурсии должен существовать способ использования [] в настройке списка различий. У меня есть Google для этого, но я не могу найти ответ, и Братко (Prolog Programming for AI) лишь кратко затрагивает тему.

Итак, можно ли написать пустой список как список различий в Prolog, если да, то как и когда это было бы полезно?

Ответ 1

Проблемы с пониманием этой темы обычно связаны с использованием вводящей в заблуждение терминологии.

Как рекомендовано в tutorial.pdf и особенно pap95.pdf используйте, например, список разницу или просто разницу.

Раздел 5 Преподаватели начинающих Prolog содержат соответствующие причины.

Пустой список однозначно обозначается атомом [].

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

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

Ответ 2

Добавление двух различий в списке означает просто объединение первого указателя конца diff со второй головкой. С регулярными списками требуется повторная проверка всей структуры списка первого списка. Таким образом, повторное конкатенация справа линейна по методу разности списков и квадратична с обычными списками.

Когда все запланированные конкатенации завершены, чтобы вернуть всю структуру в виде простого списка вызывающему, мы просто объединяем логвар "конечный указатель" с [].

В терминах C различие списков - это часть односвязного списка, где мы сохраняем две переменные: указатель на голову, а также его указатель на хвост:

// typedef struct { int payload; node* next } node;
typedef struct { node** head; node** tail } list_diff;

Теперь каждая конкатенация - это просто назначение конечного указателя:

void diff_concat( list_diff* a, list_diff* b)
{
    *(a -> tail) -> next = *(b -> head);
    a -> tail = b -> tail;
}

И финализация

void diff_finalize( list_diff* a)
{
    *(a -> tail) = NULL;  // or some sentinel value, whatever
}

В Prolog мы могли бы представить его как двоичный термин, например -/2, например. -(A,B) или A-B.

Но (как и в C) нет реальной необходимости создавать фактическую структуру в памяти только для удерживания двух указателей; мы можем просто поддерживать два логарифма в отдельности. Или пусть DCG сделают это для нас.

Выше было мотивированное введение в список разностной техники, "для чего они хороши?". Также ясно, что представление пустой разности

list_diff* d;
*(d -> head) = *(d -> tail);

Или в Prolog, пара логарифмов, унифицированных друг с другом: L-L, var(L). Чтобы узнать, почему, посмотрите, что происходит, когда пустой diff добавляется с некоторым другим различием справа (всегда справа мы добавляем вещи, тем самым увеличивая списки сверху вниз). Мой C может быть выключен, идея состоит в том, что, установив хвост, добавление к пустому diff также обновит его голову.