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

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

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

Источник

2 ответа

Решение

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

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

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

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

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

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

Источник

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

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

В терминах 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
}

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

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

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

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

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

Источник
Другие вопросы по тегам