CODEWITHSUNDEEP
prolog
BleachedAxe
BleachedAxe

Reputation: 403

Checking if the second list is half the size of first list

I am a noob prolog programmer and facing a difficulty with one of the basic problems that have been given in the book where I am learning from. The question. The question basically asks us to write down a Prolog procedure that takes two lists as arguments, and succeeds if the first list is twice the size of the second list and the two lists start with the same element. The procedure should return false if the two lists are empty.

For example it should return true if we pass the query:

a2b([a,a,a,a],[a,b]).

and would fail with a query like:

a2b([a,a],[a,b,b,b]).

I don't know how to solve this problem recursively, any help would be appreciated. Thanks!

Upvotes: 2

Views: 1167

Answers (3)

Nicholas Carey
Nicholas Carey

Reputation: 74277

Don't overthink things: just describe the solution and let Prolog sort it out.

The solution doesn't require counting or predicates other than its trivial self. It's all pattern matching. We have a special (terminating case), asserting that a list of length 2 is twice as long as a list of length 1 (which should be pretty obvious):

is_twice_as_long_as( [_,_] , [_] ) .

Then there is the general case, which asserts that given two lists of arbitrary length, the left is twice as long as the right IF we can (A) remove 2 items from the left, (B) remove 1 item from right, and recursively assert that their respective remainders are likewise twice as long:

is_twice_as_long_as( [_,_|A] , [_|B] ) :- is_twice_as_long_as( A , B ) .

Giving us the finished product:

is_twice_as_long_as( [_,_]   , [_]   ) .
is_twice_as_long_as( [_,_|A] , [_|B] ) :- is_twice_as_long_as( A , B ) .

Easy!

Edited to note the requirement that the two lists begin with the same element:

Depending on how that is interpreted...

  • this requires that the lists have a common head on each iteration:

    is_twice_as_long_as( [A,_]   , [A]   ) .
is_twice_as_long_as( [A,_|L] , [A|R] ) :- is_twice_as_long_as( L , R ) .

  • this does the check for a common head just once::

    is_twice_as_long_as( [A|As] , [A|Bs] ) :-
  is_2x([A|As],[A|Bs]) .

is_2x( [_,_]   , [_] ) .
is_2x( [_,_|L] , [_|R] ) :- is_2x( L , R ) .

Upvotes: 0

pasaba por aqui
pasaba por aqui

Reputation: 3529

First, the request about lengths:

/* empty list fulfills request */   
a2b_length([],[]). 
/* non-empty: discard two elements of first list, 
                one of second list, and verify
                remainder */
a2b_length([_,_|Q1],[_|Q2]) :- 
   a2b_length(Q1,Q2).

Now, we can add the requirement "starts by the same term and are non empty", and write the last clause:

a2b([X,_|Q1],[X|Q2]) :-
   a2b_length(Q1,Q2).

Upvotes: 3

Paulo Moura
Paulo Moura

Reputation: 18663

Cute problem. It can be solved using the following code:

% fail of the first element of each list don't unify
% or if one or both lists are empty
a2b([First| List1], [First| List2]) :-
    % calculate the length of the second list
    % while traversing both lists in parallel
    a2b_first(List2, 1, N, List1, Rest1),
    % check that the length of the rest of the first
    % list is equal to the length of the second list
    a2b_second(Rest1, N).

a2b_first([], N, N, Tail1, Tail1).
a2b_first([_| Tail2], N0, N, [_| Tail1], Rest1) :-
    N1 is N0 + 1,
    a2b_first(Tail2, N1, N, Tail1, Rest1).

a2b_second([], 0).
a2b_second([_| Tail1], N) :-
    M is N - 1,
    a2b_second(Tail1, M).

Of course, there's a simpler (but not as fun to code!) solution:

% fail of the first element of each list don't unify
% or if one or both lists are empty
a2b([First| List1], [First| List2]) :-
    length([First| List1], N1),
    length([First| List2], N2),
    N1 is 2 * N2.

The length/2 predicate is usually available either as a built-in predicate or as a library predicate.

For learning Prolog, studying the first solution is interesting. For example, it exemplifies how to take advantage of first-argument indexing and how to use accumulators for writing predicates that are tail-recursive (and thus space efficient).

Also, the first solution can be more efficient than the second solution. In the second solution, we always traverse both lists to the end to find their lengths. But, in the first solution, that is not always necessary.

Upvotes: 1

Related Questions