Сумма префиксов Prolog списка
Я хочу реализовать предикат пролога prefixSum(L, R), который вычисляет сумму префиксов списка, т.е.:
?- prefixSum([1,2,3,4],R).
R=[1,3,6,10].
Вот мое решение:
prefixSum([],[]).
prefixSum([X], [X])
prefixSum([X|Xs], [R, Rs|T]):-
Rs is X + R, prefixSum(Xs, T).
Что я могу попробовать дальше?
@Enigmativity "это не работает" ;-)
Ответы 3
prefix_sum(L, Ps) :-
prefix_sum_(L, 0, Ps).
prefix_sum_([], _, []).
prefix_sum_([H|T], S, [P|Ps]) :-
P is H + S,
prefix_sum_(T, P, Ps).
Результат в swi-прологе:
?- prefix_sum([1,2,3,4], Ps).
Ps = [1, 3, 6, 10].
Конечно, это всего лишь сканирование. Смотрите мой ответ и предоставленную ссылку.
Хотя это лучше показывает ОП, как решить их проблему, это просто не объясняет, что ОП сделал неправильно или как и почему это решение работает.
«почему это решение работает» @Enigmativity оно работает, потому что оно правильное, а решение OP — нет.
@TA_intern - Как мы узнаем, что код OP не работает, а это решение работает? Оба только что опубликовали код без четкого объяснения. Это неудачная комбинация вопрос/ответ. Наша работа, как членов этого сообщества, состоит в том, чтобы повысить качество как вопросов, так и ответов на этом сайте. Stack Overflow существует для создания хранилища качественных вопросов и ответов для будущих читателей. Будущие читатели вряд ли запустят код OP и скажут: «А, я понимаю, почему он не работает», и даже если они запустят этот код, они все еще могут не знать, почему это работает.
@brebs oof выстрелы :-D
Это операция над списками, известная как «сканирование», которая, в отличие от «свертки», сохраняет список промежуточных результатов. В вашем конкретном случае вы можете использовать встроенный plus/3, но вам также может понадобиться определить вспомогательный предикат, например add/3:
add(X, Y, Z) :- Z is X + Y.
Теперь вы можете сделать:
?- foldl(add, [1,2,3,4], 0, Sum).
Sum = 10.
?- scanl(add, [1,2,3,4], 0, [0|Sums]).
Sums = [1, 3, 6, 10].
Если вам не нравится бесполезное добавление нуля, вы можете заранее отделить первый элемент, поэтому:
?- [1,2,3,4] = [V0|Vs], scanl(add, Vs, V0, Result).
V0 = 1,
Vs = [2, 3, 4],
Result = [1, 3, 6, 10].
«Сканировать влево» и «свернуть влево» доступны в библиотеке (применить) в SWI-Prolog, и ваш точный вопрос решен в примерах в документах для сканирования . Вы также можете посмотреть на реализацию scanl.
Да, этот ответ совершенно хорош. Когда я смотрю на решение и сравниваю его с библиотечным определением scanl/4, я просто вижу общий алгоритм, специализированный для решения одного конкретного случая путем привязки цели.
Совет для профессионалов: обратите внимание, что такие фразы, как «ответ выше» или «принятый ответ», могут не выдержать испытание временем, поскольку ответы могут измениться, а ОП может изменить отметку о принятии. Обычно лучше говорить «ответ от бребов», так как авторы ответов почти всегда пишут только один ответ. В качестве альтернативы вы можете сделать ссылку на ответ, используя ссылку «Поделиться».
Хотя это может обеспечить альтернативный подход для ОП, на мой взгляд, это не отвечает на вопрос. ОП спрашивает, как правильно получить свой предикат. Они учатся программировать на Прологе. Они не пытаются на самом деле получить результат.
@halfer исправил, спасибо за подсказку
@brebs - Похоже, они пытаются узнать, как получить результат. Сам результат не является целью. И это не странно. Есть много хороших постов о том, для чего используется понижающее голосование. meta.stackexchange.com/questions/39161/… meta.stackexchange.com/questions/39161/… meta.stackexchange.com/questions/2451/…
@Enigmativity «Кажется, они пытаются узнать, как получить результат». Да, точно. Поэтому я предоставил ответ, который помещает их вопрос в контекст, предлагает альтернативные способы взглянуть на него и тщательно подталкивает к систематическому способу решения таких проблем в будущем: правильно решите свою проблему с помощью библиотечного предиката, затем посмотрите на реализацию библиотеки. , а затем выясните, как перейти от этого общего алгоритма к вашему конкретному решению. Но почему-то этого недостаточно. :-)
Ваш исходный код,
prefixSum( [] , [] ) .
prefixSum( [X] , [X] )
prefixSum( [X|Xs] , [R,Rs|T] ) :- Rs is X+R, prefixSum(Xs,T) .
Имеет эти проблемы:
- Код синтаксически неверен, так как 2-й пункт не заканчивается
.. - В третьем предложении переменная
Rвсегда будет несвязанной, если вы не указали связанный список в качестве 2-го аргумента дляprefixSum/3, что означает, чтоRs is X+Rзавершится ошибкой.
Ключ к тому, чего вы пытаетесь достичь, заключается в том, что при перемещении по списку вам необходимо отслеживать сумму, ранее вычисленную по мере продвижения.
Это приводит к такой реализации:
prefix_sum( [] , [] ) . % the empty list is a special case
prefix_sum( [X|Xs] , [X|Ys] ) :- % for a non-empty list, we add the first item to the result , and
prefix_sum(Xs,X,Ys) . % invoke our helper, seeding the previous sum with the first element.
prefix_sum( [] , _ , [] ) . % once the source list is exhausted, we're done.
prefix_sum( [X|Xs] , P , [Y|Ys] ) :- % otherwise...
Y is P+X, % compute the sum of the current element and the previous sum
prefix_sum(Xs,Y,Ys) . % and recurse down on the tails.
@TA_intern — я полагаю, что отрицательный голос был за этот комментарий: «Хотя это лучше показывает ОП, как решить их проблему, это просто не объясняет, что ОП сделал неправильно или как и почему это решение работает». Часто вопросы новичков, в частности, касающиеся Пролога, в большей или большей степени касаются простого изучения рекурсии и понимания самого языка, которым является Пролог. . . . отличается от 95% языков программирования. И в этом случае решения, использующие библиотечный код, не очень полезны: они изучают основные принципы.
Нет, Пролог ничем не отличается. Это действительно не так. Он имеет четко определенное процедурное прочтение; Я бы даже осмелился сказать, что вникнуть в это процедурное чтение не так уж и сложно. Повторение этой мантры о Прологе уже нанесло достаточно вреда.
Что не так с тем, что у вас есть?