Пролог - преобразование в хвостовую рекурсию

Как новичок в Prolog, я узнал, что хвостовая рекурсия оптимизирована. Поэтому я пытаюсь преобразовать следующую программу в хвосторекурсивные.

sum([], 0).
sum([H|T], N):-
    sum(T, X),
    N is X + H.

Вот что я пробовал, и очевидно, что что-то упустил в своей логике:

sum(List,Sum):-
    sum1(List,0,Sum).

sum1([Element|List],Accumulator,Sum):-
    (NewAccumulator is Accumulator + Element,
    sum1(List,NewAccumulator,Sum);

    List=[] -> Sum = Accumulator
    ).

Проблема в моей программе - складывать все числа, кроме последнего в списке. Как я могу улучшить эту программу? Спасибо.


accumulator prolog
person Woden    schedule 20.03.2021    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я согласен с решением TA_intern, но вот дополнение, чтобы показать вам, почему ваша программа пошла не так.

Следующая программа оставляет максимально возможную часть вашего кода, но является правильной:

sum(List,Sum):-
    sum1(List,0,Sum).

sum1([Element|List],Accumulator,Sum):-
    NewAccumulator is Accumulator + Element,
    (sum1(List,NewAccumulator,Sum);
    List=[] -> Sum = NewAccumulator
    ).

У вас было List=[] -> Sum = Accumulator, это означает, что в случае, если хвост вашего списка был пуст, вы взяли Accumulator, который является суммой всех предыдущих элементов до Element.

Альтернатива, которая сохраняет еще больше вашего кода:

sum1([Element|List], Accumulator, Sum) :-
        (   NewAccumulator is Accumulator+Element,
            sum1(List, NewAccumulator, Sum)
        ;   List=[]
        ->  Sum is Accumulator+Element
        ).

Однако лично я предпочел бы решение TA_intern.

person tiffi    schedule 20.03.2021
comment
Могу я спросить, почему программа не предпочтительна? - person Woden; 20.03.2021
comment
Я не сказал, что это нежелательный simpliciter, я сослался только на свои личные предпочтения, на которые, конечно, влияет обычная практика. Для меня это менее читабельно, чем другое решение, и я нахожу использование ИЛИ (; часто довольно сбивает с толку. Использование -> также сбивает меня с толку. Я думаю, что с точки зрения эффективности оба решения в основном равны, поэтому единственная причина моего предпочтения - удобочитаемость. - person tiffi; 20.03.2021
comment
Спасибо за разъяснение! Мне это полезно знать, поскольку я также пытаюсь улучшить читаемость и эффективность. - person Woden; 20.03.2021
comment
Не могли бы вы использовать стандартный отступ? - person false; 20.03.2021
comment
@false: что ты имеешь в виду? - person tiffi; 20.03.2021
comment
Скажите listing(sum1) (если вы используете SWI) и используйте этот отступ. Точка с запятой в конце строки после некоторых целей действительно является ноно. - person false; 20.03.2021
comment
Выполнено. Однако сейчас сходство с кодом, представленным в вопросе, уже неочевидно. - person tiffi; 20.03.2021

arrow_upward
2
arrow_downward

Проблема в том, что вы неправильно написали программу. Это было бы правильно:

sum(List, Sum) :-
    sum_1(List, 0, Sum).

sum_1([], Sum, Sum).
sum_1([H|T], Sum0, Sum) :-
    Sum1 is Sum0 + H,
    sum_1(T, Sum1, Sum).

но вы могли бы погуглить некоторую версию этого здесь, в stackoverflow.

Это тоже тривиальная складка в списке:

sum([H|T], Sum) :-
    foldl(add, T, H, Sum).

add(X, Y, Z) :- Z is X + Y.
person TA_intern    schedule 20.03.2021
comment
Спасибо! Но могу я спросить, в чем логика sum_1([],Sum,Sum).? В чем разница между помещением в блок if else и его базовым вариантом? - person Woden; 20.03.2021
comment
@Woden: так работают аккумуляторы: когда список пуст, аккумулятор является суммой. - person TA_intern; 20.03.2021
comment
хорошо понял. Спасибо! - person Woden; 20.03.2021