3

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:

  • S - final result,
  • F - maximum_so_far,
  • H - maximum_ending_here,
  • X - head of list,
  • L - list,
  • NewH, NewF - temp values.

Thanks for the help :)

Improve this question
2
  • 1
    What exactly is the problem? When you say without success, what does that mean? And, correct, you cannot re-assign (more properly stated, reinstantiate) a variable within a predicate clause without backtracking. Commented Mar 30, 2016 at 14:46
  • Thanks for the tips, the question is edited now. Commented Mar 30, 2016 at 15:36

3 Answers 3

Reset to default
3

  1. This question is, in fact, a duplicate of "Finding the maximum sublist in Prolog".

  2. There is a bounty is offered for it, so it cannot be flagged as a duplicate.

  3. I propose using my previous solution—it is based on and runs with SWI-Prolog.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Note to self is still valid.
A HO-free version may help. Otherwise there is too much at the same time.
2
+100

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).
Improve this answer

Comments

1

the standard way is to add an output parameter, that gets unified when the recursion stops. Something like

max_sum(L, S) :-
    max_sum(L, 0, 0, S).

max_sum([], _, S, S).
...

Then, your code is way more complex than needed: both versions listed on Wikipedia don't require any test, or length/2 computation. Try to simplify it leaving just the computation (you can use for instance Max_ending_here is max(0, H + X), and the tail recursive call.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.