check/3 predicate to get alternate elements from a list

Question

I have a predicate check/3 used as, e.g., check(A,B,C). All three arguments are lists:

• C is the master list
• A contains items which have an odd index
• B contains items which have an even index

For example,

check([1,3],[2,4],[1,2,3,4]) % is true
check([1,2],[3,4],[1,2,3,4]) % is false

I am trying to just check and not create two lists with even and odd parity. Here is the program I wrote:

check( [] , [] , []      ).
check( O  , C  , [O,_|C] ) :- check(O,C,A).

I am trying to solve it by removing alternate elements from third list and put it in 1st list while placing the remaining elements in the second list. But I see that it's enough if I compare them. But I couldn't get an idea of how to implement it without any arithmetic or built in predicates.

Answer 1

To partition a list C into a list of odd and even elements based on the ordinal position of the element within the list (its *index), this should the trick, if you count the first item in the list as odd (having an index of 1):

check( []     , []     , []       ) .  % the empty list has neither an even nor an odd element.
check( [O]    , []     , [O]      ) .  % a list of length 1 has only an odd element
check( [O|Os] , [E|Es] , [O,E|Xs] ) :- % a list of length > 1 has both an even and an odd element
  check(Os,Es,Xs) .                    % - park them on the respective lists and recurse down.

If, on the other hand, you want to count the first item as even, (having an index of 0), it's not much different:

check( []     , []     , []       ) .  % the empty list has neither an even nor an odd element.
check( []     , [E]    , [E]      ) .  % a list of length 1 has only an even element
check( [O|Os] , [E|Es] , [E,O|Xs] ) :- % a list of length > 1 has both an even and an odd element
  check(Os,Es,Xs) .                    % - park them on the respective lists and recurse down.

You can also accomplish the same thing by using a helper predicate with a flag that toggles to indicate state:

check( Os , Es , Xs ) :-        % to partition list C into odd and even components...
  check( odd , Os , Es , Xs ) . % - just invoke the helper with an appropriate seed value.

check( _    , []     , []     , []     ) .  % we're done when we hit the end of the list.
check( odd  , [X|Os] , Es     , [X|Xs] ) :- % otherwise, place the head of the source list on the odd result list
  check( even , Os , Es ,Xs ) .             % - and recurse down, toggling state to even.
check( even , Os     , [X|Es] , [X|Xs] ) :- % otherwise, place the head of the source list on the even result list
  check( odd  , Os , Es ,Xs ) .             % - and recurse down toggling state to odd.

You'll note that in the above example, we've seeded the helper with odd to indicate that the 1st element has an odd position (1-relative). Just switch the seed value to even if you want the first element to have an even position (0-relative).

However... There's a simpler way: on each recursion, just switch the position of the two result lists:

check( []     , [] , []     ) .
check( [X|As] , Bs , [X|Cs] ) :- check( Bs , As , Cs ) .

Sweet!

Answer 2

You're actually really close. Your second clause should be:

check([O|Os], [E|Es], [O,E|Rest]) :- check(Os, Es, Rest).

Note that this doesn't guarantee anything about oddness or evenness, just that the third list will be composed of alternating items from the first two lists. It will generate. If you're unable to use arithmetic operations, there obviously isn't going to be any way to make guarantees about the arithmetic properties of the items of the lists. But that probably isn't what's really wanted here. This will satisfy your example queries.

In my opinion, this clause shows one of the hardest things to understand about Prolog: the flow of information through the clause. You could imagine each variable being reused as something like an arrow: you have an arrow from the first item of the first argument to the first item of the third and another arrow from the first item of the second argument to the second item of the third, and then arrows from all of the list remainders to the body, saying essentially "to prove this relationship, prove that it holds recursively on the tails of the lists." This is very weird and I think you either got hung up on this or on the pattern matching in the head. My variable names may not be perfect but I suspect they will help with seeing the relationship more than O and C do.

I bet if you look at that and look at yours you'll see the problems yourself, but here they are:

• check(O, C, ...) is confused on type. O and C would need to be lists here, but list items in the body of the clause (well, C wouldn't, but there's a problem there too).
• check(..., [O,_|C]) says that the first item of the list would be O, then something unspecified, and then C would be the tail of the list.
• A is a singleton in the body, which means it's not really doing anything. Whenever you get a singleton warning, replace the variable with an underscore and see if it still looks like it makes sense. If it does not, you have a misunderstanding and probably need to make changes to your clause.

To review list constructors, [X|Xs] says X is the first item, and the rest of the list is Xs. The | operator divides items from the tail of the list. So if you're dealing with a flat (monotonic) list, everything on the left should be items and the thing on the right is another list. You can also only have one thing on the right, but you can have several items separated by commas before it (as you do).

Hope this helps!