Содержание
Я очень плохо знаком с прологом и пытаюсь написать небольшую программу, которая, учитывая список, возвращает сумму элементов списка. Следование всем примерам, которые я видел, привело меня к решению, которое выглядит следующим образом:
Но когда я тестирую это решение со следующими значениями:
Я просто получаю значения мусора из него, как _34521.
Затем я попробовал второе решение, которое выглядит так:
Этот способен правильно складывать числа, но не может передать окончательное значение X, которое является истинным ответом, в N. Итак, для теста:
Я получаю ответ 6, окончательное значение N, а также предпоследнее значение X вместо 10, окончательное значение X. Любая помощь и / или объяснения того, почему ни одно из этих решений не сработает оценили. Благодарю.
1 ответ
Во-первых, сумма пустого списка равна 0 — это базовый случай, который у вас уже был.
Во-вторых, сумма N элемента H и списка T является суммой списка T добавленного к H Пролог работает на объединение, так что это говорит о том, что N объединяется с суммой H и T , где сумма T объединяется с X с использованием sum(T,X) .
В вашем первоначальном вопросе ?- sum([1,2,3,4], 0). фактически говорит: «Это правда, если сумма списка [1,2,3,4] равна 0 » — вам нужно передать переменную в качестве второго аргумента для sum чтобы объединить его с ответом.
Дальнейшая информация:
_34521 является представлением несвязанной переменной — это говорит о том, что переменная существует, но она еще не объединена со значением.
Вторичное рассмотрение:
Для достаточно длинного списка приведенная выше реализация исчерпает пространство стека, так как каждый кадр рекурсии должен храниться так, чтобы сложение могло происходить снизу вверх. Чтобы предотвратить ошибку стека, мы можем использовать хвостовой рекурсивный аккумулятор, например, так:
. который сохраняет подпись оригинального метода, заключая в себе сумму / 3. Поскольку в теле правила отсутствует точка выбора (учитывая, что A + H всегда одинакова для заданных A и H, а список либо пуст, либо нет), Prolog будет отбрасывать каждый кадр, поскольку он покидает область видимости ( так как с этим больше ничего не поделаешь) и, по завершении, вернется к исходному звонящему.
Упрощенный стек для sum([1,2,3],N) в каждом случае:
без хвостовой рекурсии:
Обратите внимание, что хвост-рекурсивный стек имеет ограниченную глубину для любой длины списка (в зависимости от того, что его вызывает), где не хвостовой рекурсивный стек идет на глубину, прямо пропорциональную длине списка.
Таким образом, вызов, такой как N is 10^7,length(L,N),maplist(=(1),L),sum(L,N). (как поднято @false), вероятно, потерпит неудачу без хвостовой рекурсии и, вероятно, преуспеет с этим.
В функциональных и логических языках списки используются чрезвычайно часто, они позволяют сохранить набор данных произвольной длины. В статье на множестве примеров показана обработка списков в языке Prolog. Основная часть примеров написана на диалектах с динамической типизацией (SWI/GNU/Arity Prolog), но с небольшими изменениями будет отлично работать на строго-типизированных реализациях (Turbo/Visual Prolog).
Содержание:
Списки в Prolog. Теория
В общем случае список представляет собой абстрактный тип данных, задающий набор значений. В этой статье под списком понимается «связный список», являющийся одной из возможных реализаций абстрактных списков.
Связный список — структура данных, состоящая из узлов. Узел содержит данные и ссылку (указатель, связку) на один или два соседних узла. Списки языка Prolog являются односвязными, т.е. каждый узел содержит лишь одну ссылку.
В языке Prolog программист не сталкивается с явной работой с указателями в узлах, однако ему нужно иметь общее представление о списках, т.к. являясь основной структурой данных в функциональных и логических языках, они обладают рядом существенных отличий от массивов, используемых в императивных языках (таких как С++, Java, Pascal). В частности, элемент данных может быть очень быстро добавлен или удален из начала односвязного списка. Однако операция произвольного доступа (обращения к n-ному элементу) в списках выполняется гораздо дольше чем в массивах, т.к. требует n операций перехода по ссылкам.
При работе с односвязными списками необходимо выделять первый узел (называемый головой списка), остальные узлы (составляющие хвост списка) можно получить передвигаясь по указателям вплоть до последнего узла. Хвост списка является таким же списком, как и исходный, поэтому обрабатывается аналогичным образом (рекурсивно).
Процесс обработки списка в Prolog
Списки в Prolog. Синтаксис
При использовании статически-типизированного диалекта необходимо объявить тип списка (например в Turbo Prolog это делается в разделе domains):
В дальнейшем, при объявлении функций обработки списков (раздел predicates) необходимо использовать объявленный тип данных. Функция обработки списков вещественных чисел не будет обрабатывать список целых — это не очень удобно, однако позволяет выявлять несоответствие типов на этапе трансляции и генерировать более оптимальный код компилятору.
При использовании таких диалектов как SWI Prolog, предварительное объявление типов не требуется, кроме того, список может содержать данные разных типов.
Приведенный выше пример показывает рекурсивную природу списков — после отделения головы (первого элемента) остается хвост, также являющийся списком. Операция разделения на голову и хвост может использоваться для формирования нового списка. В языке имеется обозначение для пустого списка и оно постоянно используется в рекурсивных функциях для фиксации окончания обработки.
Рекурсивная обработка списков. Примеры
sum_list(List, Sum) — вычисление суммы элементов списка
Сумма элементов пустого списка равна нулю. Если список не пуст — разделим его на первый элемент и хвост. Обработаем рекурсивно хвост, в результате получим сумму элементов части списка без учета первого элемента. Добавим первый элемент чтобы получить окончательный результат.
nth0(Index, List, Elem) — функция получения элемента списка с заданным индексом. Индексация начинается с нуля. Если нужного элемента нет — функция завершается неудачей.
Функция завершает свою и успешно возвращает первый элемент списка если Index равен нулю и от списка удалось отделить первый элемент. Функция завершается неудачей если Idex оказался меньше нуля или остался больше нуля при пустом списке. Если же список не пуст (от него успешно отделяется первый элемент) и индекс больше ноля — рекурсивно обрабатывается хвост списка и уменьшенный на единицу Index (ведь список уменьшился на один элемент).
member(Elem, List) — выполняет поиск значения в списке. Завершается удачей если элемент найден.
Если значение первого элемента списка совпадает со значением искомого элемента — правило сразу завершается удачей. В противном случае первый элемент отбрасывается и поиск продолжается в хвосте. Как только разделение списка на голову и хвост станет невозможно — правило завершится неудачей.
Важно то, что предикат может вернуть несколько решений (предикат является недетерминированным — nondeterm), поэтому первое правило не содержит отсечения. Такое поведение особенно важно если функция member используется для перебора всех элементов списка (достаточно передать вместо Elem анонимную переменную).
min_list(List,MinElem) — вычисление наименьшего элемента списка
Решение очевидно, если список состоит из одного элемента. Если элементов больше, то список разделяется на голову и хвост. Рекурсивно вычисляется наименьший элемент хвоста и сравнивается с первым элементом для определения результата для всего списка.
Если на вход будет подан пустой список, то разделение на голову и хвост провалится и правило завершится неудачей.
reverse(List, ReverseList) — функция переворота списка
Чтобы перевернуть список используется метод накапливающего параметра, при этом создается вспомогательная функция, которая помимо двух списков принимает буфер. Изначально буфер пуст, но по мере обработки, в его начало добавляются элементы из исходного списка — поэтому первый добавленный элемент окажется последним, а последний — первым. Как только все элементы окажутся обработаны — накопленные в буфере значения будут переписаны в список-результат.
Метод накапливающего параметра используется достаточно часто, т.к. при его использовании рекурсивный вызов оказывается последней операцией, выполняемой функцией. Компиляторы заменяют такой вызов циклом, что позволяет обрабатывать огромные списки и не бояться переполнения стека.
sublist(Sub, List) — завершается удачей если все элементы списка Sub встречаются в списке List в точно таком же порядке.
Напишем вспомогательную функцию sub_start для проверки случая, когда список List начинается со списка Sub. Очевидно, проверка вспомогательного правила даст условие выхода из рекурсии в случае успешного завершения работы. Если же проверка не увенчалась успехом — отделим от List первый элемент, а остальные попробуем обработать рекурсивно.
Функция sub_start завершается успехом если список Sub оказался пуст, т.к. пустой список по определению является часть любого списка.
delete(InputList, Elem, ResultList) — функция удаления всех элементов с заданным значением из списка
Если на вход подан пустой список, то результатом должен также являться пустой список. Если первый элемент списка совпал с удаляемым значением — функция должна вернуть результат рекурсивной обработки хвоста, а в противном случае — добавить к полученному результату первый элемент.
append(List1, List2, List1AndList2)— функция объединения двух списков
Постепенно выбирая элементы первого списка сводим ситуацию к тому, что список станет пуст — в этом случае результатом работы функции должен являться второй список. На рекурсивном подъеме добавим к полученному результату элементы первого списка.
Функция может выполнять как объединение списков, так и их вычитание. Если задан третий аргумент, но не задан второй или первый — то она попробует подобрать недостающие значения так, чтобы получился требуемый результат. Кроме того, если не заданы оба первых аргумента — функция будете перебирать все варианты генерации третьего списка из двух.
Примеры использования функции append
unique(List) — проверка того, что ни один элемент списка не повторяется дважды
В списке нет повторяющихся элементов, если первый элемент списка не встречается в хвосте, а также, в хвосте нет повторяющихся элементов. Условием выхода из рекурсии может быть пустота исходного списка — в нем гарантированно нет повторяющихся элементов.
rangConcat(List1, List2, List1AndList2) — объединение двух отсортированных списков так, чтобы в результате получился отсортированный список.
Очевидно, что если один из списков пуст — результатом является другой список. На каждом шаге алгоритма оба входных списка разделяются на голову и хвост. Головы сравниваются и рекурсивно обрабатываются списки без наименьшей головы, на рекурсивном подъеме она добавляется к результату.
length(List, Length) — вычисляет длину списка
Используем метод накапливающего параметра чтобы рекурсия функции была хвостовой, т.к. длина списков на языке Prolog вычисляется очень часто поэтому эффективность функции является критичной.
Функция length вызывает вспомогательную, при этом задает начальное значение длины равным нулю.
Вспомогательная функция возвращает накопленное в буфере значение в качестве длины если на вход подан пустой список. В противном случае от исходного списка отделяется один элемент, вычисляется новое значение буфера. Хвост списка и буфер передаются для рекурсивной обработки.
этот код возвращает true . Если я заменю Total = Head + Sum1 С Total is Head + Sum1 , затем он вернет значение. Но что я должен заменить, чтобы получить такой результат:
5 ответов
обратите внимание,что во втором предложении вашей процедуры TotalSum никогда не создается. Вы должны были получить предупреждение от переводчика при консультации с вашим кодом.
вот мое предложение:
первое предложение имеет дело с базовым случаем, когда в списке остается только один элемент — ваш результат.
второе предложение касается шага рекурсии. Он захватывает первые два элемента списка и выполняет рекурсивный вызов replacing эти два элемента с новым термином Item1+Item2.
этот код работает только в одном направлении — это значит — она не позволяет создавать списки с этой конкретной суммы. Но поскольку набор таких списков бесконечен, это все равно было бы непрактично.
В Пролог (+)/2 — это двоичный infix оператора. Это позволяет нам писать A+B вместо +(A,B) .
(+)/2 партнеры слева, так что 1+2+3 это сокращение от (1+2)+3 .
(.)/2 присоединяется к право, так что [1,2,3] сокращенно .(1,.(2,.(3,[]))) .
чтобы получить parenthesization право, мы используем вспомогательный предикат с собой дополнительный "аккумулятор" аргумент:
Если вы хотите преобразовать список чисел в аддитивное выражение, из
вы можете сделать что-то вроде этого, используя что-то вроде список разница:
кроме того, вы можете использовать аккумулятор:
Я считаю, что вы найдете первый стиль не правильно хвост рекурсивной и поэтому не будет оптимизирован в цикл via оптимизация хвостовой рекурсии (TRO) — и поэтому, если список достаточно длинный, получит переполнение стека. Второй подход должен быть применен TRO и должен работать для списков любой длины.
что такое ТРО, спросите вы? Вот!—24—>Википедия с ответом для вас:
в информатике вызов хвоста-это вызов подпрограммы, который происходит внутри другого процедура и которая производит возвращаемое значение, которое после этого немедленно возвращенный вызывающая процедура. Затем говорят, что сайт вызова находится в хвостовом положении, т. е. в конце вызывающая процедура. Если подпрограмма выполняет хвостовой вызов для себя, она вызывается хвост-рекурсивный. Это частный случай рекурсии.
хвостовые вызовы значительны, потому что они могут быть реализованы без добавления нового стека кадр в стек вызовов. Большая часть рамок текущей процедуры не требуется больше, и его можно заменить рамкой хвоста вызов, измененный соответствующим образом (аналогично overlay для процессов, но для вызовов функций). Затем программа может перейти к называемая подпрограмма. Создание такого кода вместо стандартной последовательности вызовов называется устранение хвостового вызова или оптимизация хвостового вызова.
Загрузка...
