1

I'm studying this new concept of logical programming with Prolog. I've worked with cuts, fails, and now I'm at the topic of lists. I have the following task to do: -Write a function evenmember(Element, List), which will show if an element is at an even position in a list. For example evenmember(X,[1,5,3,2]) will show consecutively the solutions X=5,X=2.

I've been playing around for a while and have written the following: 

evenmember(_, []) :- !, fail.  
evenmember(_, [_]) :- !, fail.  
evenmember(X, [_, X]) :- !.  
evenmember(Elem, List):-  
    [_, Elem1|Tail] = List,  
    Elem is Elem1,  
    evenmember(Elem1, Tail).

The only way to show the results that worked for me was to introduce write function, but it does not work for the task. As far as I remember, we cannot use Elem and List directly, so I'm kind of confused. I ask for assistance and I'm going to be grateful for your help =)

false
  • 10,264
  • 13
  • 101
  • 209
skipper
  • 171
  • 2
  • 11
  • 1
    I'm unfamiliar with the liberal use of `!` and `fail`. My understanding is that they should be reserved for those cases when they are necessary, and avoided otherwise. But I am fairly to new to Prolog myself, so I might be mistaken here. Could you point me towards the reference material you're working with that recommends this style? Also, I'm unclear on the meaning of these remarks: "The only way to show the results that worked for me was to introduce write function, but it does not work for the task. As far as I remember, we cannot use Elem and List directly, so I'm kind of confused." – Shon Oct 09 '13 at 21:19
  • 1
    aBathologist, I am very VERY new to Prolog =) The material I'm using is basically the tasks from the university. The liberal use of cuts is mostly for increasing the efficiency of the program. As far as I know, the green cuts are used here for the fact that if it is the case of the first function, then there is no point in verifying the other functions. The fails are used, so that the result to be false. The phrase you did not understand means the following: We can use `writeln(Elem1)` in the last implementation and it showes the results. hope that clears some things. – skipper Oct 11 '13 at 06:52

3 Answers3

2

In Prolog it often helps to think about the problem in logical natural language first, then try to translate that to Prolog.

What you are asking for is a rule evenmember( X, L ) which is true if X is an even member of L. If we can properly define this rule, the solutions will be each even member of L. So expressing in natural language:

1) X is an even member of L if X is the second element of L.

So I'll state that in Prolog:

evenmember(X, [_, X|_]).   % The 2nd member of a 2-element list is an even member

That only describes the first even member. The remaining even members can be described recursively:

2) X is an even member of L if X is an even member of the tail of L
   ignoring the first two elements.

Translate this into Prolog and see what you get. This one doesn't need a cut, either. You have to be conservative with cuts. They mean that you want to prune the search tree. In this case that would mean you could stop seeking valid solutions (finding all the even members).

Note that the description I'm giving assumes you want to get a single (the next, more specifically) even member of the list on each call to the predicate, rather than the entire even list at once, since that's what the original description indicates.

lurker
  • 56,987
  • 9
  • 69
  • 103
  • Thanks for the help! This really clarified some things and the result turned out to be correct. – skipper Oct 11 '13 at 07:05
1

Here's a solution:

%% evenmembers(+List, -ListOfEvenPlacedMembers).
%    true when ListOfEvenPlacedMembers is a list of the elements of List at even places.
% 
1| evenmembers([],[]).
2| evenmembers([_Odd], []).
3| evenmembers([_Odd,Even|List], [Even|Evens]) :-
4|    evenmembers(List, Evens).

Here's a translation of the lines:

  1. The even members of an empty list is an empty list (there are none).
  2. The even members of a list with one element is an empty list (again, there are none).
  3. The even members of a list with the first two elements _Odd, and Even, and the rest List, is a list whose first member is [Even] and whose subsequent members are Evens IF
  4. the even members of List are Evens.

The rule at line 4 picks off the first two elements of a list and puts the second, even placed, element into the list of evenly placed elements. If you're running this in the swi-prolog interpreter, it should give you the solutions without you having to use write/1. However, if you wanted to use an io predicate to format the output, you can do so by adding a helper predicate:

format_evenmembers(List) :-
    evenmember(List, Evens),
    format("Even members are ~w", [Evens]).
Shon
  • 3,989
  • 1
  • 22
  • 35
  • Well, basically it is the point. The first parameter of the function is mostly used to see what are the elements of the list step-by-step. Plus, in case we have an empty list we do not care what the first parameter is, because it will return False anyway. – skipper Oct 11 '13 at 06:57
  • @andru6a I see. I misunderstood your original question, and assumed that the variable to unify with your result would be in the second argument. Poor reading on my part. – Shon Oct 11 '13 at 20:48
1

This looks like homework, but I'll point you in the right direction by showing a similar example.

even_members([], []).
even_members([_], []) :- !.
even_members([_,Even|Tail], [Even|Result]) :-
  even_members(Tail, Result).

which gives

?- even_members([1,5,3,2], X).
X = [5, 2].

We take the 2nd element in the head of the list (which will always be the evenly positioned element), and add it to the list which will contain the answer. Then recursively iterate through the list using the tail.

The base case is when we reach the end of the list. Since we traverse the list 2 elements at a time, for an even length list we'll reach an empty list, and for an odd length list there'll be a single element left (as pointed out by aBathologist). Once we reach a base case, we build the list going back up the recursion tree.

My example stores the answer in a list, which is typically what you'd want (lists are common in Prolog). In your solution, you don't want to store the results in a list.

P.S. It's been over a year since I wrote any Prolog, so hopefully I still know what I'm talking about.

Dennis
  • 56,821
  • 26
  • 143
  • 139
  • 1
    This almost works--I posted pretty much the same answer at the same time (tho I think that your explanation of the recursive definition is clearer than my natural-language translation). However, you left out the case of a single-element list, which means that your solution returns `false` on any odd-lengthed list. – Shon Oct 09 '13 at 23:48
  • 1
    Note that you don't want to use a cut like in my answer when not storing even members in a list (and rather showing them one at a time). In that case, @mbratch's answer is more appropriate, so I upvoted it. – Dennis Oct 10 '13 at 23:15
  • This actually is homework, but I was not asking for the answer, but more for the advice on what to do. I probably have trouble with understanding recursion in Prolog, and believe me I've tried; I downloaded a couple of books, looked at different resources, but most of the information is either too little, or it goes too advanced. – skipper Oct 11 '13 at 07:00
  • @andru6a It's okay that it's homework, but you should make that obvious when asking a question on SO. As for Prolog, you'll get better at it with practice. Try using trace to trace execution, it helps when trying to follow the recursion. – Dennis Oct 11 '13 at 07:34
  • -1 the cut is misplaced, and the question was about one member at a time. – false Oct 11 '13 at 21:00
  • @andru6a recursion is very simple. you start by imagining you have your function already available to you. Of course it must follow certain laws, to do what it is supposed to be doing. you just write down these laws. and that is the definition. that's it. :) And in Prolog, we read predicates as "to do this, we must do that". e.g. "to prove `even_members([_,Even|Tail], [Even|Result])`, we must prove (`:-`) that `even_members(Tail, Result)`". – Will Ness Oct 12 '13 at 19:56
  • @andru6a I [tried to explain recursion once](http://stackoverflow.com/a/11666815/849891), see if it helps. :) – Will Ness Oct 12 '13 at 20:08