Удаление элемента из списка

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

del(Ele, [H], [H]) :- Ele \= H.
del(Ele, [H|T], [H|New]) :-
    Ele \= H,
    del(Ele, T, [New]).

Идея состоит в том, что я добавлю элемент в новый список с именем New, если элемент, который я хочу удалить, не равен H. Насколько я понимаю, мой код не работает, потому что мой код останавливается, когда я достигаю элемента, где Ele \= H. Любые идеи, как это исправить?

Например, del(5, [3,4,5,6,7], X) вернет false.

Кроме того, есть ли лучшие решения? Кажется плохим решением продолжать добавлять каждый элемент списка в новый список, так как это будет медленным для большого списка. Я бы предпочел просто сохранить элементы, которые сейчас находятся в списке, найти элементы, соответствующие Ele, удалить этот элемент, а затем вернуть список.


prolog prolog-dif
person dtgee    schedule 19.03.2013    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Вы описали некоторые случаи, когда del/3 должен оставаться в силе. Но это только случаи, когда Ele не равно / не унифицируется с элементами в списке. Не хватает нескольких вещей:

Что насчет пустого списка?

Что, если Ele равно элементу?

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

Если вы используете SWI, B, SICStus или YAP, подумайте об использовании dif/2 вместо (\=)/2. prolog-diff

Вот почему dif/2 так помогает в этом случае. С dif/2 у вас будет чисто монотонная программа. И вы можете попробовать это напрямую:

?- del(5, [3,4,5,6,7], X).
false.

Та же проблема, что и у вас. Позвольте мне просто повторить, в чем проблема: вы ожидаете, что что-то должно удерживаться, но это не так. Итак, отношение слишком узко. Если я обобщу вопрос, я могу получить лучший ответ. Попробуйте del(E, [3,4,5,6,7], X)., но снова то же false. Поэтому я попробую еще более общий запрос:

?- del(E, Xs, Ys).
Xs = Ys, Ys = [_G1076],
dif(E, _G1076) ...

По мне, выглядит идеально! Может быть, другой ответ:

?- del(E, Xs, Ys).
Xs = Ys, Ys = [_G1076],
dif(E, _G1076) ;
Xs = [_G1133, _G1136],
Ys = [_G1133|_G1136],
dif(E, _G1136),
dif(E, _G1133) ...

Теперь мы получили неверный ответ. Я немного создам его экземпляр, чтобы было удобнее читать:

?- del(e, [a,b], Ys).
Ys = [a|b] ;
false.

Этот ответ явно неверен, потому что [a|b] не является списком. И, наверное, самый маленький неправильный ответ ...

Этим я хочу показать вам, что чаще всего вы можете найти проблемы, не выполняя их пошагово. Пошаговая отладка не работает даже в императивных языках, если вы получаете более сложный поток управления (например, параллелизм); и он вообще не масштабируется в Прологе.

person false    schedule 19.03.2013
comment
Вау! Не могу поверить, что это была проблема! Думаю, я настолько привык к ООП, что думаю, что если я просто рекурсивно пройду по списку, и он Ele не равен H, то он пропустит этот элемент и перейдет к следующему. - person dtgee; 20.03.2013
comment
@ user1831442: Вы слишком привязаны к фактическому выполнению Prolog. Это нормально, когда вы переходите с командно-ориентированного языка. - person false; 20.03.2013
comment
@false: но, к сожалению, я обнаружил, что написание правильных программ на Прологе требует размышлений о модели выполнения. По общему признанию, это не то же самое, что программирование на C, но, по крайней мере, я не могу написать даже простой предикат (например, пример OP), не задумываясь о процедурном значении программы. Я полагаю, что со временем это настолько хорошо усваивается, что больше не нужно думать об этом сознательно. - person ; 20.03.2013
comment
@Boris: Начать нужно с чисто монотонных программ. Одиночный (\=)/2 портит однообразие. Другой момент - больше полагаться на запросы верхнего уровня, а не не на трассировки. Вы можете посмотреть в теге отказ-срез, чтобы увидеть, как в этом манера. - person false; 20.03.2013

arrow_upward
2
arrow_downward

Проследим:

?- trace, del(5, [3,4,5,6,7], X).
   Call: (7) del(5, [3, 4, 5, 6, 7], _G218) ? creep
   Call: (8) 5\=3 ? creep
   Exit: (8) 5\=3 ? creep
   Call: (8) del(5, [4, 5, 6, 7], [_G344]) ? creep
   Call: (9) 5\=4 ? creep
   Exit: (9) 5\=4 ? creep
   Call: (9) del(5, [5, 6, 7], [[]]) ? creep
   Fail: (9) del(5, [5, 6, 7], [[]]) ? creep
   Fail: (8) del(5, [4, 5, 6, 7], [_G344]) ? creep
   Fail: (7) del(5, [3, 4, 5, 6, 7], _G218) ? creep
false.

Таким образом, вы можете видеть, что ваш код действительно не работает, когда он достигает 5, потому что 5 \= 5 ложно. Ваше первое правило никогда не выполняется, потому что список содержит более одного элемента. Второе правило повторяется «правильно» после нахождения 5 \= 3 и 5 \= 4, но поскольку у вас нет 5 = 5 регистра ни в одном из ваших правил, сбой происходит там.

Кстати, давайте посмотрим, что будет, если 5 не окажется в списке:

?- trace, del(5, [3,4,6,7], X).
   Call: (7) del(5, [3, 4, 6, 7], _G350) ? creep
   Call: (8) 5\=3 ? creep
   Exit: (8) 5\=3 ? creep
   Call: (8) del(5, [4, 6, 7], [_G473]) ? creep
   Call: (9) 5\=4 ? creep
   Exit: (9) 5\=4 ? creep
   Call: (9) del(5, [6, 7], [[]]) ? creep
   Fail: (9) del(5, [6, 7], [[]]) ? creep
   Fail: (8) del(5, [4, 6, 7], [_G473]) ? creep
   Fail: (7) del(5, [3, 4, 6, 7], _G350) ? creep
false.

Вот почему я сказал «правильно» раньше: ваш индуктивный случай тоже неверен. Во-первых, у вас есть del(Ele, T, [New]), но наверху у вас del(Ele, [H|T], [H|New]), поэтому вы разворачиваете список еще раз справа (вот почему в нашей трассировке есть [[]]). Но @false затрагивает более серьезную проблему, заключающуюся в том, что вы просто никогда не учитываете случай, когда вы действительно находите то, что хотите удалить. :) Вы также не обрабатываете случай, когда список пуст.

Это досадный факт из жизни, что обход структур данных и просмотр каждого элемента будет O (N). Еще один досадный факт заключается в том, что в функциональных и декларативных языках (языках, в которых отсутствуют «присваиваемые») изменение списка означает копирование хотя бы части списка. В Prolog есть более эффективные способы сделать это (например, вы можете использовать списки различий), но они будут иметь одну и ту же основную проблему. Эффективность Пролога - довольно большая тема. Я бы посоветовал вам не беспокоиться об этом слишком сильно заранее, но это может довольно быстро стать вашей проблемой. Но в этом случае нет, на самом деле нет более эффективного подхода с использованием деструктивных обновлений.

person Daniel Lyons    schedule 19.03.2013
comment
Спасибо! Я только что исправил свою проблему. Однако у меня есть одноэлементная переменная, поскольку мой базовый случай del(Ele, [], []).. Я чувствую, что одноэлементные переменные - это плохо. Как мне удалить это предупреждение? - person dtgee; 20.03.2013
comment
Они плохие. Вы всегда можете избавиться от предупреждения, заменив одноэлементную переменную на _. Это также полезно, потому что если это выглядит так, как будто это меняет значение кода (в данном случае это не так), это хороший признак того, что ваша интуиция относительно кода неверна. - person Daniel Lyons; 20.03.2013
comment
Спасибо! Даниэль, ты спаситель Пролога! И последний вопрос ... Мне скоро предстоит экзамен, и это будет в значительной степени тест на то, как писать некоторые функции для Prolog, Haskell и Perl. Я также должен знать различия этих языков (их системы типов, динамический / статический, механизм вывода и т. Д.). Есть ли у вас какие-либо рекомендации о том, какие еще функции мне следует попробовать написать, или как я могу понять, как эти языки работают по-другому? Например, мне нужно знать, чем сопоставление с образцом в Прологе отличается от сопоставления с образцом в Haskell и что Пролог использует унификацию и отслеживание с возвратом. - person dtgee; 20.03.2013
comment
Это неподходящий форум для обсуждения этого вопроса (возможно, slant.co), но если вы пришлете мне электронное письмо, мы сможем поговорить об этом в другом месте. - person Daniel Lyons; 20.03.2013