Prolog

Question

作为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
    ).

我程序中的问题是将列表中除最后一个数字之外的所有数字相加。我怎样才能改进这个程序？谢谢

Answer 1

问题是你程序写错了。这是正确的：

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).

但你可以在 Whosebug 上用谷歌搜索这个的一些版本。

这也是一个简单的折叠列表：

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

add(X, Y, Z) :- Z is X + Y.

Answer 2

我同意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的解决方案。

Prolog - 转换为尾递归

Prolog - transforming to tail recursion

accumulator