i am trying to implement Kadane's Algorithm in Prolog. One of the requirements is a tail call (recursion).
I have tried many possibilities but without success. Here is my code:
max_sum(L, S) :-
S is 0,
H is 0,
max_sum(L, H, S).
max_sum([], S, S).
max_sum([X | L], H, S) :-
( H + X < 0 -> NewH is 0; NewH is H + X),
( S < H + X -> NewS is NewH; NewS is S),
length(L, N),
( N < 1 -> max_sum(L, NewS, NewS); max_sum(L, NewH, NewS)).
NewH, NewS are temp values (we cant assign a value twice in Prolog right?). Can i ask for a hint?
Edit:
[trace] ?- max_sum([1, 2, 3], S).
Call: (7) max_sum([1, 2, 3], _G8907) ? creep
Call: (8) _G8907 is 0 ? creep
Exit: (8) 0 is 0 ? creep
Call: (8) _G8991 is 0 ? creep
Exit: (8) 0 is 0 ? creep
Call: (8) max_sum([1, 2, 3], 0, 0) ? creep
Call: (9) 0+1<0 ? creep
Fail: (9) 0+1<0 ? creep
Redo: (8) max_sum([1, 2, 3], 0, 0) ? creep
Call: (9) _G8994 is 0+1 ? creep
Exit: (9) 1 is 0+1 ? creep
Call: (9) 0<0+1 ? creep
Exit: (9) 0<0+1 ? creep
Call: (9) _G8997 is 1 ? creep
Exit: (9) 1 is 1 ? creep
Call: (9) length([2, 3], _G8998) ? creep
Exit: (9) length([2, 3], 2) ? creep
Call: (9) 2<1 ? creep
Fail: (9) 2<1 ? creep
Redo: (8) max_sum([1, 2, 3], 0, 0) ? creep
Call: (9) max_sum([2, 3], 1, 1) ? creep
Call: (10) 1+2<0 ? creep
Fail: (10) 1+2<0 ? creep
Redo: (9) max_sum([2, 3], 1, 1) ? creep
Call: (10) _G9000 is 1+2 ? creep
Exit: (10) 3 is 1+2 ? creep
Call: (10) 1<1+2 ? creep
Exit: (10) 1<1+2 ? creep
Call: (10) _G9003 is 3 ? creep
Exit: (10) 3 is 3 ? creep
Call: (10) length([3], _G9004) ? creep
Exit: (10) length([3], 1) ? creep
Call: (10) 1<1 ? creep
Fail: (10) 1<1 ? creep
Redo: (9) max_sum([2, 3], 1, 1) ? creep
Call: (10) max_sum([3], 3, 3) ? creep
Call: (11) 3+3<0 ? creep
Fail: (11) 3+3<0 ? creep
Redo: (10) max_sum([3], 3, 3) ? creep
Call: (11) _G9006 is 3+3 ? creep
Exit: (11) 6 is 3+3 ? creep
Call: (11) 3<3+3 ? creep
Exit: (11) 3<3+3 ? creep
Call: (11) _G9009 is 6 ? creep
Exit: (11) 6 is 6 ? creep
Call: (11) length([], _G9010) ? creep
Exit: (11) length([], 0) ? creep
Call: (11) 0<1 ? creep
Exit: (11) 0<1 ? creep
Call: (11) max_sum([], 6, 6) ? creep
Exit: (11) max_sum([], 6, 6) ? creep
Exit: (10) max_sum([3], 3, 3) ? creep
Exit: (9) max_sum([2, 3], 1, 1) ? creep
Exit: (8) max_sum([1, 2, 3], 0, 0) ? creep
Exit: (7) max_sum([1, 2, 3], 0) ? creep
In Call(11) i have a good result (6) from this simple example. How can I end the function at this point without returning? It is my problem.
Result from this code is S = 0, not S = 6.
Final edit (working code):
max_sum(L, S) :-
max_sum(L, 0, 0, S).
max_sum([], _, S, S).
max_sum([X | L], H, F, S) :-
NewH is max(0, H + X),
(F < H + X -> NewF is NewH; NewF is F),
max_sum(L, NewH, NewF, S).
Where:
Thanks for the help :)
I propose a slightly altered version of the solution proposed by @repeat:
:- use_module(library(clpfd)).
zs_max([Z|Zs], MSF) :-
zs_max_(Zs, Z, Z, MSF).
zs_max_([], _, MSF, MSF).
zs_max_([Z|Zs], MEH0, MSF0, MSF) :-
max(Z, MEH0+Z) #= MEH1,
max(MSF0, MEH1) #= MSF1,
zs_max_(Zs, MEH1, MSF1, MSF).
First, the sample queries from the original solution that yield the same results:
?- zs_max([-2,1,-3,4,-1,2,1,-5,4], Max).
Max = 6
?- zs_max([-2,3,4,-5,8,-12,100,-101,7], Max).
Max = 100
However this version is more general, in that it works with arbitrary values (as suggested by @false in the comment to solution). This is accomplished by starting with the value of the first element of the list instead of 0. Thus the following query yields a different result:
?- zs_max([-2,-3,-4], X).
X = -2
?- zs_maxmum([-2,-3,-4], X).
X = 0
Another difference is that the empty list has no solution:
?- zs_max([], X).
no
?- zs_maxmum([], X).
X = 0
I think this behaviour is more reasonable, as the empty list has no sublist and hence no sums of sublists from which to choose a maximum. However, if desired, a special case for the empty list can be easily added:
zs_max([], replaceThisWithAReasonableValue).