All geek questions in one place

Find progressively large items in the prolog list

Given the prologue list, I want to create a second one containing ever larger elements. For instance,

L = [ 1, 5, 2, 3, 4, 10, 15, 11, 12, 13, 20 ] Answer = [ 1, 5, 10, 15, 20 ]

My code is:

 local_max([],_,_). local_max([XH|XT],Y,temp) :- ( XH =< temp -> local_max(XT,Y,temp) ; local_max(XT,[XH|Y],XH) ).

I thought that this should lead to the fact that I answered just the opposite, but it is not. Just false.

The list contains only positive integers, so I just did

 local_max([ 1, 5, 2, 3, 4, 10, 15, 11, 12, 13, 20 ],Answer,0).
+5
source share
2 answers

You made some small mistakes:

  • temp not a valid variable name, it must be temp ,
  • _ not the correct result, when the input list is empty, it must be [] , Construction
  • [XH|Y] not what you combine with a recursive call when expanding a list. Pass a new variable, say R , and then build Y by combining Y = [XH|R]

Here is your bug fix program:

 local_max([],[],_). local_max([XH|XT],Y,Temp) :- ( XH =< Temp -> local_max(XT,Y,Temp) ; local_max(XT,R,XH), Y = [XH|R] ).

This gives the expected result ( demo ).

+3
source

Since you are using Prolog (;) / 2 - if-then-else for the task, you may need if_ / 3 . In addition, the predicate can be made more universal by using CLP (FD) (for details, see, for example, Swi-Prolog manual writing to CLP (FD) ). And, in addition, I would suggest using a call predicate with two arguments, namely a list and a list of gradually increasing elements. To emphasize the relational nature of the predicate, give it a more descriptive name, for example list_ascendings / 2:

 :- use_module(library(clpfd)). list_ascendings([],[]). list_ascendings([X|Xs],A) :- X0 #= X-1, list_ascendings_([X|Xs],A,X0).

The first rule list_ascendings / 2 is for handling an empty list. If you do not want to include this case, just omit the rule. The second rule calls the predicate list_ascendings_ / 3 with a rotation value ( X0 ) that is smaller than the list title, so the latter is included in the list of gradually increasing elements. The defensive version of a higher ratio (used as the first argument to if_ / 3 ) can be defined as follows:

 bool_t(1,true). bool_t(0,false). #<(X,Y,Truth) :- X #< Y #<==> B, bool_t(B,Truth).

Based on this, a predicate describing the actual relationship can be defined as follows:

 list_ascendings_([],[],_). list_ascendings_([X|Xs],A,X0) :- if_(X0#<X, (A=[X|As], X1=X), (A=As, X1=X0)), list_ascendings_(Xs,As,X1).

Depending on whether the rotation value of the header head is less or not, the list of ascending elements ( A ) and the new rotation value ( X1 ) are described respectively.

Now let's see how the predicate works. Your sample query gives the desired result:

  ?- list_ascendings([1,5,2,3,4,10,15,11,12,13,20],A). A = [1,5,10,15,20]

Note that the predicate deterministically succeeds if the first argument is grounded (no selection points remain open, so no need to click ; after a single solution). You can also ask the opposite question: which lists have [1,5,10,15,20] as the largest gradually increasing sublist?

  ?- list_ascendings(L,[1,5,10,15,20]). L = [1,5,10,15,20] ? ; L = [1,5,10,15,20,_A], _A in inf..20 ? ; L = [1,5,10,15,20,_A,_B], _A in inf..20, _B in inf..20 ? ...

Obviously, there are infinitely many answers to this question. However, it would be nice to get the answers in a more equitable order, that is, all answers for lists of length 6 before lists of length 7, etc. You can achieve this by pre-setting the query with a target length of / 2:

  ?- length(L,_), list_ascendings(L,[1,5,10,15,20]). L = [1,5,10,15,20] ? ; L = [1,5,10,15,20,_A], _A in inf..20 ? ; L = [1,5,10,15,_A,20], _A in inf..15 ? ; L = [1,5,10,_A,15,20], _A in inf..10 ? ; ... L = [1,5,10,15,20,_A,_B], _A in inf..20, _B in inf..20 ? ; L = [1,5,10,15,_A,20,_B], _A in inf..15, _B in inf..20 ? ; L = [1,5,10,15,_A,_B,20], _A in inf..15, _B in inf..15 ? ; ...

You can also get answers with specific numbers by restricting the L elements to a domain using ins / 2 and labeling it. For example: what lists of length 7 and numbers from 0 to 20 are such that [1,5,10,15,20] is the largest ascending ascending list? The corresponding request provides all the answers for 1997:

  ?- length(L,7), L ins 0..20, list_ascendings(L,[1,5,10,15,20]), label(L). L = [1,5,10,15,20,0,0] ? ; L = [1,5,10,15,20,0,1] ? ; L = [1,5,10,15,20,0,2] ? ; ... L = [1,5,10,15,20,2,15] ? ; ... L = [1,0,5,10,4,15,20] ? ; ...

EDIT:

As for your question in the comments, the description of the gradual descending sublist is pretty simple coming from the upstream version. You just need to slightly modify two goals:

 list_descendings([],[]). list_descendings([X|Xs],A) :- X0 #= X+1, % <- change list_descendings_([X|Xs],A,X0). list_descendings_([],[],_). list_descendings_([X|Xs],A,X0) :- if_(X#<X0, (A=[X|As], X1=X), (A=As, X1=X0)), % <- change list_descendings_(Xs,As,X1).

This gives the desired result:

  ?- list_descendings([20,15,3,5,7,8,2,6,2],A). A = [20,15,3,2]

On the other hand, if you mean one predicate that does both (see the last query below), you need a few more changes. First you need to add an update version of the relationship for the downstream sublists:

 #>(X,Y,Truth) :- X #> Y #<==> B, bool_t(B,Truth).

Since the first rotation value is calculated differently for the ascending and descending sublists, it is oppurtune to delegate that to the new predicate:

 x_pivot_wrt(X,X0,#>) :- X0 #= X+1. x_pivot_wrt(X,X0,#<) :- X0 #= X-1.

Then the calling predicate needs an additional argument to indicate in what respect the sub-list should progress. It would also be beneficial to rename it to reflect its new behavior:

 list_progressives_wrt([],[],_). list_progressives_wrt([X|Xs],P,Rel) :- x_pivot_wrt(X,X0,Rel), list_progressives_wrt_([X|Xs],P,Rel,X0).

Finally, the predicate describing the actual relation also has an additional argument, namely the relation indicated. The first if_ / 3 argument calls the specified relation ( Rel ) along with the rotation value ( X0 ) and the head of the list ( X ). Note that the last argument (true value) is missing in the call, as is the first if_ / 3 argument in list_ascendings_ / 3 and list_descendings_ / 3.

 list_progressives_wrt_([],[],_,_). list_progressives_wrt_([X|Xs],P,Rel,X0) :- if_(call(Rel,X0,X), (P=[X|Ps], X1=X), (P=Ps, X1=X0)), list_progressives_wrt_(Xs,Ps,Rel,X1).

A query that matches your example produces the desired result:

  ?- list_progressives_wrt([1,5,2,3,4,10,15,11,12,13,20],P,#<). P = [1,5,10,15,20]

Since relationships that can be specified appear in x_pivot_wrt / 3, you can specify both options by leaving the last argument variable:

  ?- list_progressives_wrt([20,15,3,21,5,7,8,2,6,30,2],P,Rel). P = [20,15,3,2], Rel = #> ? ; P = [20,21,30], Rel = #<
+5
source

Source: https://habr.com/ru/post/1269650/

More articles:


All Articles