开发者

Prolog - return value from base case

开发者 https://www.devze.com 2023-01-22 03:56 出处:网络
Ok, here\'s the deal: I\'ve got two piles of shirts I want to take a random shirt from each pile and put them in a new pile

Ok, here's the deal:

  • I've got two piles of shirts
  • I want to take a random shirt from each pile and put them in a new pile
  • Then get the new pile out

And here is the code:

mix([],[],_).
mix(P1,P2, Pile):-
    takeshirt(P1,1,Taken1,Rem1), takeshirt(P2,1,Taken2,Rem2), #Take one
    append(Pile,Taken1,New),     append(New,Taken2,NewPile),  #Put both of them
    mix(Remain1,Remain2,NewPile).

This is what the result look like:

1 ?- mix([a,b],[c,d],NewPile).
NewPile = [] .

I want it to look like:

1 ?- mix([a,b],[c,d],NewPile).
NewPile = [b, d, a,开发者_如何学JAVA c] .

Or whatever the result is. I checked via the graphical debugger and found out that when the final call to mix happens, the bindings are:

P1 = Taken1 = [b]
P2 = Taken2 = [c]
Pile           = [a, d]
Rem1 = Rem2 = []
New         = [a, d, b]
NewPile     = [a, d, b, c] #<--- Interresting  

So the wanted value is in NewPile when the final call to:

mix([],[],_). 

happens. After this is it collapses like a house of cards.

So the question is:

mix([],[],_).

I'd like to return the _ value from the base case, this rule mix is actually used from a higher instance where I send in two piles and get the new pile out.

Update:

To clarify some comments about the takeshirt rule, here it is:

takeshirt(_,0,[],_).
takeshirt(List,Number,[Element|Taken],Remain) :- N > 0,
    length(List,Len),
    Index is random(Len) + 1,
    removeshirt_at(Element,List,Index,Remain),
    Number1 is Number - 1,
    takeshirt(Remain,Number1,Taken,Remain). 


Consider the following modifications to your code:

mix([], [], []) :- !.
mix(P1, P2, Pile) :-
    takeshirt(P1, 1, Taken1, Rem1), 
    takeshirt(P2, 1, Taken2, Rem2),
    append(Taken1, Taken2, Pile0),
    mix(Rem1, Rem2, Pile1),
    append(Pile0, Pile1, Pile).

It seems you need to accumulate the 'shirts' (as list atoms). Here, we are recursively appending them onto the third argument of mix/3 (Pile), until the base case (the first clause) is hit when both input lists are empty lists (note that the cut ! is necessary here as the binding pattern for the second clause matches the first, so we want to exclude it). The behaviour of the second clause, which takes a shirt from each input list for every step, requires that they must have been of equal length to start with.

To test this, I used the following definition of takeshirt/4:

takeshirt(Ps, _, [P], Rem) :-
    select(P, Ps, Rem).

Note that the second argument here is unused, as select/3 is being used to take a single element (a shirt) from the list, and return the remainder. The absence of a cut (!) after the select allows this predicate to backtrack in selecting all other elements (shirts) from the list. If we now execute your example query with this definition, we can get:

1 ?- mix([a,b],[c,d],NewPile).
NewPile = [a, c, b, d] ;
NewPile = [a, d, b, c] ;
NewPile = [b, c, a, d] ;
NewPile = [b, d, a, c] ;
false.

...we can see that mix/3 enumerates all possible 'piles' on backtracking by taking a shirt from the first pile (first input list), then a shirt from the second pile (second input list), and so on, until both input lists are empty. If your definition of takeshirt/4 doesn't leave choice-points, (is non-backtracking), then you could only get one solution, if any.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号