CODEWITHSUNDEEP
prolog
Bogdan M.
Bogdan M.

Reputation: 2191

Avoid recursion in predicate

I have the following question for the following predicate, how can i drop the recursive call f(T,S1) from both predicates.

Flow model: (i,o)

f([],0).
f([H|T],S):-
    f(T,S1),
    S1 > 2,!,
    S is S1 + H.
f([_|T],S):-
    f(T,S1),
    S is S1 + 1.

This is a trick question, and I am not that good with prolog. the second predicate fails always.= > can be droped, but what about the second. As I see this method is a list elements counter. Thanks.

Is that even possible?

Upvotes: 2

Views: 111

Answers (2)

false
false

Reputation: 10142

OK, this is a complex issue. You assume it is a trick question, but is it really one? How can we be sure? I will let library(clpfd) do the thinking for me. First I will rewrite your program:

:- use_module(library(clpfd)).

fx([],0).
fx([H|T],S):-
    fx(T,S1),
    S1 #> 2,
    S #= S1 + H.
fx([_|T],S):-
    fx(T,S1),
    S1 #=< 2,
    S #= S1 + 1.

(And just a remark: putting these tests after the recursion twice will make this program require exponentially many inferences, but let's stick to it...)

So I would like to reason about that program in the most general manner. Therefore, I will not take concrete values and then try to figure out a theory. Instead I will ask very general questions (using SICStus):

| ?- assert(clpfd:full_answer).
yes
| ?- length(L,N), fx(L,S).
   L = [],
   N = 0,
   S = 0 ?
;
   L = [_A],
   N = 1,
   S = 1 ?
;
   L = [_A,_B],
   N = 2,
   S = 2 ?
;
   L = [_A,_B,_C],
   N = 3,
   S = 3 ?
;
   L = [_A,_B,_C,_D],
   N = 4,
   _A+3#=S,
   _A in inf..sup,
   S in inf..sup ?
;
   L = [_A,_B,_C,_D,_E],
   N = 5, ...

So please look at the answers N = 0 up to N = 3: There no constraints are involved, effectively all the elements of the list [_A,_B,...] are ignored. However, starting with N = 4 the first element _A now influences the "sum" S since the equation S #= _A+3 holds! With larger values things become more and more complex.

In any case, I cannot see how this could be a trick question. The last three elements are ignored. Well, that's kind of a trick. But otherwise elements (or at least some of them) influence the outcome!

Upvotes: 3

repeat
repeat

Reputation: 18726

How about the following? It's efficient!-)

f([],0).
f([H|T],S):-
    f(T,S1),
    (  S1 > 2
    -> S is S1 + H
    ;  S is S1 + 1
    ).

Upvotes: 2

Related Questions