Пролог: избавление от рекурсивного вспомогательного предиката

Итак, я пытаюсь избавиться от предложения-оболочки, используя предикат библиотеки сортировки непосредственно внутри разделения. Что делает split, так это просто генерирует список чисел из списка, который выглядит так: [1:2,3:2,4:6] ---split--> [1,2,3,2,4,6 ]. Но сгенерированный список содержит дубликаты, и я этого не хочу, поэтому я использую оболочку для объединения разделения и сортировки, которая затем генерирует желаемый результат: [1,2,3,4,6].

Мне бы очень хотелось избавиться от оболочки и просто использовать сортировку внутри разделения, однако я продолжаю получать сообщение «ОШИБКА: сортировка / 2: аргументы недостаточно созданы». Любые идеи? Спасибо :)

split([],[]).
split([H1:H2|T],[H1,H2|NT]) :-
    split(T,NT).

wrapper(L,Processed) :- 
    split(L,L2),
    sort(L2,Processed).

predicate prolog logic-programming
person oyvindhauge    schedule 15.11.2012    source источник
comment
Термин [1:2,3:2,4:6] мне кажется странным, для чего он нужен? а что это ins(T,NT)?   -  person false    schedule 15.11.2012
comment
входы должны быть разделены, вызываемые рекурсивно, мой плохой :). фиксированный. [1:2..] — список ребер в графе.   -  person oyvindhauge    schedule 15.11.2012
comment
Вы никогда не получите это сообщение об ошибке с вашим определением split/2. Это невозможно!   -  person false    schedule 15.11.2012
comment
Я получу его, если воспользуюсь им где-нибудь в теле сплита.   -  person oyvindhauge    schedule 15.11.2012
comment
Если вы вызовете wrapper/2, вы никогда не получите это сообщение об ошибке, потому что после успешного выполнения split(L,L2) переменная L2 будет правильно сформированным списком. Ваша программа, кажется, сейчас в порядке.   -  person false    schedule 15.11.2012
comment
да. Моя программа работает прекрасно. Однако, как я уже сказал, мне на самом деле плевать на оболочку, и я хочу изменить структуру своего кода, чтобы в ней не было необходимости.   -  person oyvindhauge    schedule 15.11.2012
comment
Непонятно, что вы подразумеваете под оберткой. Вы получаете данные типа [1:2,3:2] откуда-то еще, так что вам приходится с ними иметь дело? В противном случае я бы рекомендовал вместо этого [1-2,3-2], потому что есть библиотеки, предполагающие такое представление.   -  person false    schedule 15.11.2012
comment
Может быть, вы хотите написать что-то вроде: sort(split(L),Processed)? В Прологе это невозможно: нет функций — есть только отношения.   -  person false    schedule 15.11.2012
comment
@false да, sort(split(L),Processed) было бы здорово. Как вы понимаете, я новичок в Прологе. (надеюсь) мне больше не придется иметь с этим дело после этого семестра ;)   -  person oyvindhauge    schedule 15.11.2012
comment
Добро пожаловать! Может быть, вы научитесь любить его...   -  person false    schedule 15.11.2012

Ответы (1)


arrow_upward
1
arrow_downward

Я бы очень хотел избавиться от оболочки и просто использовать сортировку внутри разделения

Затем используйте findall со сложной целью, такой как

split(Edges, NodeSet) :-
    findall(Node,
            (member(Edge, Edges), (Edge = (Node:_); Edge = (_:Node))),
            NodeList),
    sort(NodeList, NodeSet).

Однако, как только вы начнете использовать агрегирующие предикаты, вы можете просто пропустить sort и использовать setof:

split(Edges, NodeSet) :-
    setof(Node, Edge^Pair^(member(Edge, Edges),
                           Edge =.. [:|Pair],
                           member(Node,Pair)),
          NodeSet).

Читается как: получить набор всех Node ст. существует Edge и существует Pair с.т. (и т. д.) и назовите это NodeSet.

Оператор =.. ("univ") деконструирует пару: Edge =.. [:, Left, Right]. Для лучшей читаемости вы можете написать отдельный предикат для получения узлов из ребер:

% endpoint(Edge, Node) is true iff Node is an endpoint of Edge
endpoint(Node:_, Node).
endpoint(_:Node, Node).

split(Edges, NodeSet) :-
    setof(Node, Edge^(member(Edge, Edges), endpoint(Edge, Node)), NodeSet).

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

person Fred Foo    schedule 15.11.2012
comment
Что вы получаете здесь по сравнению с исходным split/2? За исключением того, что ваше решение не работает, если присутствуют переменные. - person false; 15.11.2012
comment
@false: вы все равно не можете найти набор элементов из списка, содержащего переменные. Что вы получаете, так это то, что теперь у вас есть цель или пара целей, которые вы можете вставить в середину более крупного предложения, не называя их, потому что рекурсия теперь неявна. Вот почему эти предикаты существуют. - person Fred Foo; 15.11.2012
comment
(=..)/2 ?!?! Это 1970-е? :-) - person false; 15.11.2012
comment
@false: что вы предлагаете вместо этого? - person Fred Foo; 15.11.2012
comment
Использование переменных напрямую не имеет смысла, но они могут использоваться в качестве дополнительного аргумента. Вы уверены, что этого никогда не произойдет? Я бы не был так уверен. - person false; 15.11.2012
comment
что вы предлагаете вместо него? Я думаю, что split/2 в порядке. Это очень надежно. Даже к странным вещам. Для setof/3, получившего такой большой термин, как Edges, может случиться так много всего, например, неожиданные объединения и тому подобное. Может быть, не здесь. Но я видел это так часто. - person false; 15.11.2012
comment
@false: это правда, что эта версия предиката принимает списки с мусором в них, я дам вам это. Но он соответствует стилю более высокого порядка, который мне нравится с тех пор, как я перешел от логического программирования к функциональному программированию, и который лично мне легче читать. - person Fred Foo; 15.11.2012
comment
Я понимаю аргумент элегантности, но он чрезвычайно хрупок, поскольку количественная оценка настолько неявна. Если между ними произойдет какая-то неудача, цель все равно будет успешной! Сравните это с чистыми монотонными предикатами более высокого порядка, такими как maplist/2... Если что-то не получается, вся цель терпит неудачу. Кроме того, maplist/2.. и ему подобные прекрасно взаимодействуют с ограничениями. Но setof/3 к этому не подготовлен; и никогда не будет (скорее всего). - person false; 15.11.2012
comment
@larsman: Извините, я пропустил ваш универсальный вопрос. (я так и не понял лайф-апдейт, видится, что иногда что-то пропускаю, а иногда идеально). Так что же плохого? Он допускает гораздо больший набор, чем предполагалось (здесь, в данном случае). Подумайте об этом: в качестве узлов у вас есть список других узлов. И теперь вы путаете один уровень списков - и быстро ваш (=..)/2 теперь даст вам 1 и [2,3]... Другими словами: Недостаточно типизации (не то, чтобы я тоскую по системе типов...) - person false; 15.11.2012
comment
@false: хорошая система типов HO - одно из дополнений к Prolog, которое мне бы понравилось (Mercury в этом отношении довольно интересен). Я уже усилил код, сделав его Edge =.. [:|Pair]; проверка length(Pair,2) может усилить его еще больше. - person Fred Foo; 15.11.2012
comment
Самая большая проблема заключается в том, как такая система взаимодействует с остальной частью Пролога. У Тома Шриверса была система типов, допускающая некоторые динамические преобразования. Я много комментировал это в 2008 году. Но это еще не развивалось. Также нет типа list. Только тип list_of/1. Видишь, что я имею в виду? - person false; 15.11.2012
comment
@false: я собираюсь закончить это обсуждение в одностороннем порядке, если вы не возражаете - я не так хорошо разбираюсь в теории Пролога, как вы. Мой пост отвечает на вопрос ОП, но я добавил к нему примечание, указывающее на это обсуждение, чтобы ваши опасения можно было прочитать. Если вы опубликуете их как отдельный ответ и оставите здесь комментарий, я, безусловно, подумаю о том, чтобы проголосовать за него. - person Fred Foo; 16.11.2012
comment
setof (а также bagof), кажется, сохраняет переменные в списке, поэтому здесь это кажется правильным решением. +1 = 400! :) - person Will Ness; 30.04.2013