Fact for each element of a list Prolog

Tag: prolog Author: kounan0711 Date: 2014-02-03

I want to solve this problem in Prolog. i want give a list of natural numbers to find all the elements in the list that satisfy this condition:

All elements on the left of it are smaller than it and all the elements on the right of it are larger than it.

For example give a list [3,2,4,1,5,7,8,9,10,8] the answer would be 5,7

So far I've manage to make this function that given an element of the list it returns true or false if the element satisfises the condition described above.

check(Elem, List) :-
    seperate(Elem, List, List1, List2),
    lesser(Elem, List1, X1),
    bigger(Elem, List2, X2),
    size(X1, L1),
    size(X2, L2),
    size(List, L3),
    match(L1, L2, L3),

Now I want to make another predicate that given a list, it does the above computations for each element of the list. Due to the fact that more than one element may satisfy it I want to create another list with all the elements that satisfy the problem.

The question would be something like ?-predicate_name([[3,2,4,1,5,7,8,9,10,8],N). and the result would be a list of elements.

Sry If I am not using the right terms of Prolog. I will describe what I want to do in sequential logic language to be more specific although it's not a good idea to think like that. If we consider a the predicate check as a function that given a list and element of the list it would return true or false whether or not the element satisfied the conditions of the problem. Now I want to parse each element of the list and for each one of it call the function check. If that would return true then I would add the element in another list a.k.a result. I want to do this in Prolog but I don't know how to iterate a list.

Your check relation has three arguments but your check2 relation calls it with two arguments. Do you want check to return as a variable List2 a list containing only one item, namely Elem?
What you wrote tests whether check is true for all elements. What do you want exactly? Do not think in "Do this Do that" describe it more with "this means that"
@alpha I edited the post, I've forgotten one argument.
@User the check works fine. I don't give any further information since it doesn't matter what it really does.
Now I want to make another predicate that given a list it does the above computations for each element of the list. Against what list? Do you mean, given a list, you want to run check on each element of that list against the full original list? And then in check2, what do you want to do with the resulting list from check, if anything?

Best Answer

I'm going to take a different approach on the problem.

We want to find all of the values that meet the criteria of being a "mid" value, which is one defined as being greater than all those before it in the list, and less than all those after.

Define a predicate mid(L, M) as meaning M is a "mid" value of L:

mid([X|T], X) :-         % The first element of a list is a "mid" if...
    less(X, T).          %    it is less than the rest of the list
mid([X|T], M) :-         % M is a "mid" of [X|T] if...
    mid(T, X, M).        %    M is a "mid" > X
                         %    (NOTE: first element is not a "mid" by definition)

mid([X|T], LastM, X) :-  % X is a "mid" > Y if...
    X > LastM,           %    X > the last "mid"
    less(X, T).          %    X < the rest of the list, T
mid([X|T], LastM, M) :-  % Also, M is a "mid" if...
    Z is max(X, LastM),  %    Z is the larger of X and the last "mid"
    mid(T, Z, M).        %    M is the "mid" of T which is > Z

less(X, [Y|T]) :-        % X is less than the list [Y|T] if...
    X < Y,               %    X < Y, and
    less(X, T).          %    X < the tail, T
less(_, []).             % An element is always less than the empty list

Each query will find the next "mid":

| ?- mid([3,2,4,1,5,7,8,9,10,8], M).

M = 5 ? ;

M = 7 ? ;


Then they can be captured with a findall:

mids(L, Ms) :-
    findall(M, mid(L, M), Ns).

| ?- mids([3,2,4,1,5,7,8,9,10,8], Ms).

Ms = [5,7]


| ?- mids([2], L).

L = [2]

(1 ms) yes

This is probably not the most computationally efficient solution since it doesn't take advantage of a couple of properties of "mids". For example, "mids" will all be clustered together contiguously, so once a "mid" is found, it doesn't make sense to continue searching if an element is subsequently encountered which is not itself a "mid". If efficiency is a goal, these sorts of ideas can be worked into the logical process.


With credit to @false for reminding me about maplist, the above predicate call less(X, T) could be replaced by maplist(<(X), T) eliminating the definition of less in the above implementation.


I can't find words to thank you! Thx a lot for your time and effort
@Mario no problem. Expressing the problem in logical language that maps nicely to prolog goes a long way to finding the solution.
As I see it I have a lot to learn in prolog :)
mids([2],[2]). fails. But all elements to the left and right are smaller/greater.
@false, yes that's by design. I wasn't sure what the OP meant to do with the extremes. Now that you mention it, an element should be considered greater than or less than the empty list. I've updated the answer accordingly.

Other Answer1

Here is a version using DCGs and assuming we want to compare arithmetically.

list_mid(L, M) :-
   phrase(mid(M), L).

mid(M) -->

seq([]) -->
seq([E|Es]) -->

Often it is not worth optimizing this any further. The first seq(Sm) together with the subsequent maplist/2 might be merged together. This is a bit tricky, since one has to handle separately the cases where Sm = [] and Sm = [_|_].

mid(M) -->
   (  [M]
   |  max(Mx),
      {Mx < M}

max(M) -->
   maxi(E, M).

maxi(E, E) -->
maxi(E, M) -->
   {G is max(F,E)},
   maxi(G, M).

min(_) -->
min(M) -->
   {M < E},


Cool (+1). I was thinking about trying a DCG approach and didn't get to it.
Oops I think you meant maplist(>(M),Sm) and maplist(<(M),Gr).
@mbratch: thank you!