-1

I have to determine whether the number of elements from a list is even or not without counting them. This is a problem that i need to solve in Prolog, so I guess that the solution needs to be recursive. I was thinking about counting the frequencies of all elements and then adding them all, but I am not sure that this is a good idea.

repeat
  • 18,496
  • 4
  • 54
  • 166
dd1714
  • 139
  • 1
  • 6
  • 3
    You should show some attempt here. But as a big hint: consider that `[_, _|T]` is a list with at least two elements. And, `[]` is a list of 0 elements, which is even. You can use this to your advantage in your recursive solution. :) – lurker Oct 21 '15 at 16:03
  • It is not clear what you mean by "without counting". There must be counting of some sort: after all, "even" is defined in terms of natural numbers. And how will counting the frequencies help? Would it be enough to use the length of the list and check if it's even? –  Oct 21 '15 at 17:05

2 Answers2

3

Here is a pure, reified version:

evenlength_t([], true).
evenlength_t([_|Xs], T) :-
   i_evenlength_t(Xs, T).

i_evenlength_t([], false).
i_evenlength_t([_|Xs], T) :-
   evenlength_t(Xs, T).

It will give true or false as the second argument for actual lists, and will fail for terms that are neither lists nor partial lists. Reified predicates can be used as conditions for the monotonic if_/3.

The following more straight-forward version cannot distinguish between non-lists and lists of odd length:

evenlength([]).
evenlength([_,_|Xs]) :-
   evenlength(Xs).

As a downside, both versions will loop for so called infinite lists.

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
0

This is without counting:

list_even_length(List, Len) :-
    length(List, Len),
    Len rem 2 =:= 0.

If you actually mean "without arithmetic", this is something different. You can see here an example of how to skip all elements at even positions. Whay you need to do is much simpler: just consume a list exactly two elements at a time.

Community
  • 1
  • 1
  • 3
    The call to `length/2` counts the elements in the list. – Paulo Moura Oct 21 '15 at 18:39
  • 1
    @PauloMoura So does any kind of iteration over it.... –  Oct 21 '15 at 18:54
  • 2
    Although to @PauloMoura 's point, one could argue that `length/2` literally implements a counter, whereas there are alternatives that recurse to the end without having to count and can determine evenness by the final state of the recursion. – lurker Oct 21 '15 at 19:13
  • @lurker I get your point and I agree with Paulo, but this feels like a technicality. As you are certainly aware, just replace 0 with `[]`, and n and n' with `X` and `[_|X]`: are we counting natural numbers or iterating through a list? –  Oct 21 '15 at 19:57
  • Yeah it is a technicality. Semantics. :) – lurker Oct 21 '15 at 20:32