создание списка из вложенной структуры в прологе

Я хочу создать список с коэффициентами из вложенной структуры в прологе.

Например: (structure --> возвращаемое значение)

item(koeffizient(2), exponent(2), item(koeffizient(3), exponent(3))) --> [0,0,2,3]

item(koeffizient(5), exponent(0), item(koeffizient(1), exponent(1), item(koeffizient(3), exponent(3)))) --> [5,1,0,3]

item(koeffizient(5), exponent(0)) --> [5]

item(koeffizient(5), exponent(0), item(koeffizient(2), exponent(2))) --> [5,0,2]

Как я могу сделать это рекурсивным способом? На самом деле я понятия не имею, как я могу это сделать.

Спасибо за любую помощь, которую вы можете мне дать =)


person user1843596    schedule 07.12.2012    source источник
comment
эти "возвращаемые значения" кажутся почти случайными...   -  person CapelliC    schedule 07.12.2012


Ответы (1)


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

Вы можете сделать это жадно, предполагая, что ваша структура упорядочена по показателям (как показывают ваши примеры):

structure(Struct, Exps):-
  structure(Struct, 0, Exps).

structure(item(koeffizient(Coeff), exponent(Exp)), Exp, [Coeff]).
structure(item(koeffizient(Coeff), exponent(MExp)), Exp, [0|Tail]):-
  MExp > Exp,
  succ(Exp, NExp),
  structure(item(koeffizient(Coeff), exponent(MExp)), NExp, Tail).
structure(item(koeffizient(Coeff), exponent(Exp), StructTail), Exp, [Coeff|Tail]):-
  succ(Exp, NExp),
  structure(StructTail, NExp, Tail).
structure(item(koeffizient(Coeff), exponent(MExp), StructTail), Exp, [0|Tail]):-
  MExp > Exp,
  succ(Exp, NExp),
  structure(item(koeffizient(Coeff), exponent(MExp), StructTail), NExp, Tail).

Процедура structure/2 просто вызывает structure/3 с показателем степени 0.

Первый пункт structure/3 является базовым. Возвращает коэффициент для последней степени.

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

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

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

Если, как говорится в ваших комментариях, входные данные не упорядочены, возможно, было бы лучше преобразовать ваши входные данные в список упорядоченных кортежей формы Exp-Coeff.

С таким списком ваша structure/2 процедура остается прежней, и вы можете упростить procedure/3 до этой:

structure([], _, []).
structure([Exp-Coeff|Tail], Exp, [Coeff|TailCoeffs]):-
  succ(Exp, NExp),
  structure(Tail, NExp, TailCoeffs).
structure([MExp-Coeff|Tail], Exp, [0|TailCoeffs]):-
  MExp > Exp,
  succ(Exp, NExp),
  structure([MExp-Coeff|Tail], NExp, TailCoeffs).
person gusbro    schedule 07.12.2012
comment
Спасибо! Структура — это возвращаемое значение из прогресса DCG, сделанного однокурсником. Теперь он говорит, что в отличие от его примеров структура не упорядочена показателями. Каковы наилучшие способы сделать это? В очередной раз благодарим за помощь! - person user1843596; 07.12.2012
comment
@ user1843596: Если структура не упорядочена по показателям, я бы предложил применить преобразование к структуре в более управляемую структуру (например, списки пар Exp-Coeff), тогда вы можете легко отсортировать список с помощью keysort/2 и построить список коэффициентов, аналогичный показанному в этом ответе. - person gusbro; 07.12.2012
comment
Хорошо, теперь у меня есть отсортированный список значений ключа ([Exp-Coeff,... ]), но я не могу создать список [C0,C1,...Cn], как вы сделали это выше. Я был бы очень рад, если бы вы могли помочь мне снова. - person user1843596; 08.12.2012
comment
@ user1843596: Я улучшил ответ, чтобы показать, как вы это сделаете, если у вас есть структура ввода в виде упорядоченного списка кортежей Exp-Coeff. - person gusbro; 09.12.2012
comment
Еще раз большое спасибо за вашу помощь! =) Все работает теперь как надо. - person user1843596; 09.12.2012