CODEWITHSUNDEEP
listrecursionprolog
spjz
spjz

Reputation: 23

How can I compare two lists in prolog, returning true if the second list is made of every other element of list one?

I would solve it by comparing the first index of the first list and adding 2 to the index. But I do not know how to check for indexes in prolog. Also, I would create a counter that ignores what is in the list when the counter is an odd number (if we start to count from 0). Can you help me? Example: everyOther([1,2,3,4,5],[1,3,5]) is true, but everyOther([1,2,3,4,5],[1,2,3]) is not.

Upvotes: 2

Views: 3701

Answers (2)

repeat
repeat

Reputation: 18726

We present three logically-pure definitions even though you only need one—variatio delectat:)

  1. Two mutually recursive predicates list_oddies/2 and skipHead_oddies/2:

    list_oddies([],[]).
list_oddies([X|Xs],[X|Ys]) :-
   skipHead_oddies(Xs,Ys).

skipHead_oddies([],[]).
skipHead_oddies([_|Xs],Ys) :-
   list_oddies(Xs,Ys).

  2. The recursive list_oddies/2 and the non-recursive list_headless/2:

    list_oddies([],[]).
list_oddies([X|Xs0],[X|Ys]) :-
   list_headless(Xs0,Xs),
   list_oddies(Xs,Ys).

list_headless([],[]).
list_headless([_|Xs],Xs).

  3. A "one-liner" which uses foldl/4 in combination with Prolog lambdas:

    :- use_module(library(lambda)).

list_oddies(As,Bs) :-
   foldl(\X^(I-L)^(J-R)^(J is -I,( J < 0 -> L = [X|R] ; L = R )),As,1-Bs,_-[]).

All three implementations avoid the creation of useless choicepoints, but they do it differently:

  • #1 and #2 use first-argument indexing.
  • #3 uses (->)/2 and (;)/2 in a logically safe way—using (<)/2 as the condition.

Let's have a look at the queries @WouterBeek gave in his answer!

?- list_oddies([],[]),
   list_oddies([a],[a]),
   list_oddies([a,b],[a]),
   list_oddies([a,b,c],[a,c]),
   list_oddies([a,b,c,d],[a,c]),
   list_oddies([a,b,c,d,e],[a,c,e]),
   list_oddies([a,b,c,d,e,f],[a,c,e]),
   list_oddies([a,b,c,d,e,f,g],[a,c,e,g]),
   list_oddies([a,b,c,d,e,f,g,h],[a,c,e,g]).
true.                                           % all succeed deterministically

Thanks to , we get logically sound answers—even with the most general query: 

?- list_oddies(Xs,Ys).
  Xs = [],                        Ys = []
; Xs = [_A],                      Ys = [_A]
; Xs = [_A,_B],                   Ys = [_A]
; Xs = [_A,_B,_C],                Ys = [_A,_C]
; Xs = [_A,_B,_C,_D],             Ys = [_A,_C]
; Xs = [_A,_B,_C,_D,_E],          Ys = [_A,_C,_E]
; Xs = [_A,_B,_C,_D,_E,_F],       Ys = [_A,_C,_E]
; Xs = [_A,_B,_C,_D,_E,_F,_G],    Ys = [_A,_C,_E,_G]
; Xs = [_A,_B,_C,_D,_E,_F,_G,_H], Ys = [_A,_C,_E,_G]
...

Upvotes: 3

Wouter Beek
Wouter Beek

Reputation: 3407

There are two base cases and one recursive case:

  1. From an empty list you cannot take any odd elements.
  2. From a list of length 1 the only element it contains is an odd element.
  3. For lists of length >2 we take the first element but not the second one; the rest of the list is handled in recursion.

The code looks as follows:

odd_ones([], []).
odd_ones([X], [X]):- !.
odd_ones([X,_|T1], [X|T2]):-
  odd_ones(T1, T2).

Notice that in Prolog we do not need to maintain an explicit index that has to be incremented etc. We simply use matching: [] matches the empty list, [X] matches a singleton list, and [X,_|T] matches a list of length >2. The | separates the first two elements in the list from the rest of the list (called the "tail" of the list). _ denotes an unnamed variable; we are not interested in even elements. Also notice the cut (!) which removes the idle choicepoint for the second base case.

Example of use:

?- odd_ones([], X).
X = [].
?- odd_ones([a], X).
X = [a].
?- odd_ones([a,b], X).
X = [a].
?- odd_ones([a,b,c], X).
X = [a, c].
?- odd_ones([a,b,c,d], X).
X = [a, c].
?- odd_ones([a,b,c,d,e], X).
X = [a, c, e].

Upvotes: 1

Related Questions