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

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 meta-predicate 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 logical-purity, 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]
...