CODEWITHSUNDEEP
listrecursionprolog
pinkyring
pinkyring

Reputation: 1

Prolog: Choosing NOT to insert an element during list recursion

I've made a predicate that takes 2 list as arguments and returns a list concatenated with the product of "recipesub", however I need to make a third rule that prohibits the product from being inserted if the product at hand is an empty list.

So the first list could look like this:

recipe([ingredient(rice,4),ingredient(salt,3),ingredient(water,5)]).

And the second one like this:

ingredients([ingredient(rice,3),ingredient(salt,4),ingredient(water,4),

At the moment it returns: List = [ingredient(rice,1),[],ingredient(water,1)]

I WANT it to return: List = [ingredient(rice,1),ingredient(water,1)]

need_to_buy([],_,List):- List = [].
need_to_buy([H|Hs],[X|Xs],[Difference|List]):-
   H = ingredient(Type,Amount),
   recipesub(Type,Amount,[X|Xs],Difference),
   need_to_buy(Hs,[X|Xs],List).

Below is how far I've gotten with the solution.

/*need_to_buy([H|Hs],[X|Xs],List):-
   H = ingredient(Type,Amount),
   recipesub(Type,Amount,[X|Xs],Difference),
   Difference = [],
   need_to_buy(Hs,[X|Xs],List).*/

And this is the support-predicate, recipesub.

recipesub(Type,Amount,[],Difference):-
    Difference = ingredient(Type,Amount).
recipesub(Type,Amount,[Z|_],Difference):-
    Z = ingredient(Type,Stock),
    Amount>Stock,
    NewAmount is Amount-Stock,
    Difference = ingredient(Type,NewAmount).
recipesub(Type,Amount,[Z|_],Difference):-
    Z = ingredient(Type, Stock),
    Stock >= Amount,
    Difference = [].
recipesub(Type,Amount,[Z|Zs],Difference):-
    Z = ingredient(WrongType,_),
    WrongType \= Type,
    recipesub(Type,Amount,Zs,Difference).

Upvotes: 0

Views: 89

Answers (2)

pinkyring
pinkyring

Reputation: 1

I ultimately solved it by splitting the second rule of need_to_buy into two rules, one which handles the case where difference is an empty list, and on where it isnt an empty list.

I had some trouble with it at first but it turns out the "orientation" of the rules was giving me trouble, so I had to place the rule which handles the case where Difference \= [], above the one where Difference = []. It now looks like this: 

need_to_buy([],_,List):- List = [].
need_to_buy([H|Hs],[X|Xs],[Difference|List]):-
   H = ingredient(Type,Amount),
   recipesub(Type,Amount,[X|Xs],Difference),
   Difference \= [],
   need_to_buy(Hs,[X|Xs],List).
need_to_buy([H|Hs],[X|Xs],List):-
   H = ingredient(Type,Amount),
   recipesub(Type,Amount,[X|Xs],Difference),
   Difference = [],
   need_to_buy(Hs,[X|Xs],List).

Upvotes: 0

Daniel Lyons
Daniel Lyons

Reputation: 22803

I normally don't do a bunch of nested conditionals but it "felt right" this time, and this is the solution I found:

need_to_buy([], _, []).
need_to_buy([ingredient(Type, AmountNeeded)|Ingredients], OnHand, Needed) :-
    % Do we have any on-hand?
    member(ingredient(Type, AmountOnHand), OnHand) ->

        % If the amount on-hand is greater than the amount needed, 
        % just hand off the rest
        (AmountOnHand >= AmountNeeded ->
             need_to_buy(Ingredients, OnHand, Needed)

         % otherwise, calculate the amount needed and recur
         ; (AmountToBuy is AmountNeeded - AmountOnHand,
            need_to_buy(Ingredients, OnHand, RestNeeded),
            Needed = [ingredient(Type, AmountToBuy)|RestNeeded]))

    % If we have none on-hand, we can just use the amount needed
    % to form the request, and recur
    ; need_to_buy(Ingredients, OnHand, RestNeeded),
      Needed = [ingredient(Type, AmountNeeded)|RestNeeded].

Otherwise I think you'll have a lot of fairly inefficient testing and retesting. The main mistake I see in your code is that you're pattern matching on the second argument. It's easier to rely on member/2 or memberchk/2 to do the dirty work of finding the right ingredient in the stuff you have on-hand.

If I did it with a bunch of clauses instead it would probably look like this:

need_to_buy([], _, []).

% case 1: we don't have the ingredient at all
need_to_buy([ingredient(Type, AmountNeeded) | Ingredients],
            OnHand,
            [ingredient(Type, AmountNeeded)|Needed]) :-
    \+ memberchk(ingredient(Type, _), OnHand),
    need_to_buy(Ingredients, OnHand, Needed).

% case 2: we have it, but not enough
need_to_buy([ingredient(Type, AmountNeeded) | Ingredients],
            OnHand,
            [ingredient(Type, AmountToBuy)|RestNeeded]) :-
    memberchk(ingredient(Type, AmountOnHand), OnHand),
    AmountNeeded > AmountOnHand,
    AmountToBuy is AmountNeeded - AmountOnHand,
    need_to_buy(Ingredients, OnHand, RestNeeded).

% case 3: we have enough
need_to_buy([ingredient(Type, AmountNeeded) | Ingredients],
            OnHand,
            RestNeeded) :-
    memberchk(ingredient(Type, AmountOnHand), OnHand),
    AmountNeeded =< AmountOnHand,
    need_to_buy(Ingredients, OnHand, RestNeeded).

This leaves a choice point on the stack and just generally seems like a lot of retesting the same conditions and re-traversal for my taste. But if it looks better to you it should work the same.

Upvotes: 1

Related Questions