How to check which items in the list meet a certain condition?

5

How to make a function called LinhasLongas , which receives 2 parameters at least, to decide if a bus line is long or not?

The data is in a list of punctuated pairs, such as:

((1 . 2)(2 . 3)(5 . 3)(2 . 7)(10 . 20))

Line number in the example is the 1st of the first dotted pair, and how many dots the line has is the first dotted pair of 2.

There must be a list of points that have a number of points greater than the last parameter. Suppose a function called maior exists, which receives a and b and returns a>b .

    
asked by anonymous 18.06.2015 / 00:11

1 answer

1

Prolog uses an execution strategy called deep search with backspace . This means that given two calls, it will try to find a solution for the first, then one for the second, and if for some reason the second fails it "undoes" what it has done so far and tries to find some other solution for the first call, trying again the second, etc., until he finds some solution or concludes that there is none.

In this way, given the built-in member/2 (which succeeds if the X element is in the L list) and the maior/2 function that - as stated in the question - receives A and B and succeeds if A > B

Prolog has no functions, it has relationships , so strictly speaking a Prolog relationship does not "return" anything)

?- L = [[1,2], [2,3], [5,3], [2,7], [10,20]], member([Linha,Pontos], L), maior(Pontos, 3).

What the Prolog engine will do is:

  • The first member of L is [1,2] , then [Linha,Pontos] = [1,2] ; that is, Linha = 1 and Pontos = 2 ;
  • maior(2, 3) will fail; the backscatter will "unbound" Linha and Ponto , returning them to be free variables;
  • The next member of L is [2,3] , then [Linha,Pontos] = [2,3] ; as before, maior(3,3) will fail and rewind will occur again;
  • The next member of L is [5,3] , then [Linha,Pontos] = [5,3] ; as before, maior(3,3) will fail and rewind will occur again;
  • The next member of L is [2,7] , then [Linha,Pontos] = [2,7] ;
  • maior(7,3) will succeed. As the last call is, the entire expression will have completed successfully, and what will be returned is:

    Linha = 2
    Pontos = 7
    

If you ask for "more results" ( ; on the command line) then it will rewind, trying the [10,20] pair (which will succeed) and returning it. If you request "more results" again, since there is no longer any element in the list it will return no (or false , depending on the implementation).

OK, but what if you do not want a result but all results? That's where the built-in findall/3 comes in. : it establishes a "target" variable, a predicate to be tested, and unifies the third argument with the list of values for that variable that satisfy the given predicate. Example:

?- findall(Linha, (
       L = [[1,2], [2,3], [5,3], [2,7], [10,20]], member([Linha,Pontos], L), maior(Pontos, 3)
   ), Lista).

Lista = [2,10]

?- findall(Linha, (
       L = [[1,2], [2,3], [5,3], [2,7], [10,20]], member([Linha,Pontos], L), maior(Pontos, 2)
   ), Lista).

Lista = [2,5,2,10]

In other words, what findall does is more or less the same as you doing a query and asking for "more results" until you have none, and build a list with any expression involving each result. / p>

In conclusion, assuming you have a way of reading your input and transforming it into a list of pairs ( in that related question

a> I give a response showing a way to do this, via DCG), what remains then is to encapsulate the above logic into a separate relation:

lista_maiores(L, Valor, Maiores) :-
    findall(Linha, (member([Linha,Pontos], L), maior(Pontos, Valor)), Maiores).

?- lista_maiores([[1,2], [2,3], [5,3], [2,7], [10,20]], 2, Lista).

    Lista = [2,5,2,10]

Example in ideone .

    
18.06.2015 / 03:12