[comp.lang.prolog] A Challenge

patch@hpldoda.UUCP (Pat Chkoreff) (12/10/89)

Here's a challenge for you.  It's a stripped-down version of a problem I've
been working on, and I haven't solved it yet.

Write a predicate good/1 which succeeds if and only if its argument is a
list of lists, where all of the lists have the same length.

All of these queries should work:

    ?- good([]).
    Yes
    ?- good([[a,b],[c,d]]).
    Yes
    ?- good([[a],[b,c]]).
    No
    ?- good([_,_,_,[a],_,_,_,[b,c],_,_,_|_]).       % this one's tough.
    No

The predicate should be written using pure Horn clauses -- no calls to !/0
or var/1.

'Same length' is defined by:

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


Maybe I have no business even trying to solve this problem, but it bothers
me that I can't do it.

Please e-mail candidate solutions (or proofs of intractability) to me:  I'll
post the winner.  Thanks.


Patrick Chkoreff   719-590-5983
{hpfcla,hplabs}!hpldola!patch


P.S.  I'm not really at "Hunga Dunga U.", I'm really at Hewlett-Packard,
Electronic Design Division.

mj@cs.brown.edu (Mark Johnson) (12/15/89)

/* good(List1,List2, ... Listn) is true iff List1 ... Listn
 * are all of the same length
 */

good(Lists) :-
	all_null(Lists).
good(OldLists) :-
	minus_firsts(OldLists, NewLists),
	good(NewLists).

/* all_null(List) is true iff every element of List is [] */

all_null([]).
all_null([[]|Rest]) :- all_null(Rest).

/* minus_firsts([[_|List1], ... [_|Listn]], [List1, ..., Listn]) */
minus_firsts([], []).
minus_firsts([[_|List]|OldLists], [List|NewLists]) :-
	remove_firsts(OldLists, NewLists).

Duchier-Denys@cs.yale.edu (Denys Duchier) (12/16/89)

[I tried to mail you, but somehow my mailer choked on your address]

Your problem was somewhat underspecified. I assumed that you did not
want any variables to become instantiated as a result of a call to
good/1. The trick I use is List \= a which means that List must not be
unifiable with atom a (in particular, it can't be a variable). I
tested the following with sbprolog:

good(Lists) :- are_lists(Lists,Length).

is_list(List,Length) :- List \= a, List = [], Length = 0.
is_list(List,Length) :- List \= a, List = [Head|Tail],
	is_list(Tail,TailLength), Length is 1 + TailLength.

are_lists(Lists,Length) :- Lists \= a, Lists = [].
are_lists(Lists,Length) :- Lists \= a, Lists = [Head|Tail],
	is_list(Head,Length), are_lists(Tail,Length).


--Denys

mahler@latcs1.oz.au (Daniel Mahler) (12/18/89)

I tried replying by email but it bounced.
So, here it is.

good([A, B| Rest]) :-
	same_length(A, B),
	good([B |Rest]).
good([_]).
good([]).

The recursion uses transitivity of equality (of length).
The complexity should be linear with (size of lists * number of lists)
If you have an intelligent optimising compiler,
it might execute in constant space by not constructing
the [B |Rest] but simply taking the CDR of the initial list.

This can be hacked for efficiency as follows:

good([A, B| Rest]) :-
	(	A == B
		;
		same_length(A, B)
	),
	!,
	good([B |Rest]).

and the base case clauses can be given a body containing only the cut,
though I do not think that this would achieve anything.
The cut before recursion can save heaps when the goal is going to fail.
The == represents non-logical equality (lisp's eq),
it saves recursing down the lists when both are in the same location,
and therefore the same list.

Hope this is what you meant
	Daniel Mahler
	LaTrobe Uni

lee@munnari.oz.au (Lee Naish) (12/21/89)

Sorry if some people get this twice - I tried to post it before but it
didn't seem to get anywhere.  Sorry also if you get a garbled copy of
another recent article of mine - a slip of the mouse, and I couldn't
cancel the article because it was posted by 'news', not by me!

In article <11500022@hpldoda.UUCP> patch@hpldoda.UUCP (Pat Chkoreff) writes:
>
>Write a predicate good/1 which succeeds if and only if its argument is a
>list of lists, where all of the lists have the same length.
>
>All of these queries should work:
>
>    ?- good([]).
>    Yes
>    ?- good([[a,b],[c,d]]).
>    Yes
>    ?- good([[a],[b,c]]).
>    No
>    ?- good([_,_,_,[a],_,_,_,[b,c],_,_,_|_]).       % this one's tough.
>    No
>
The last query causes problems for some of the other proposed solutions,
since they can instantiate variables to longer and longer lists.  One
proposed solution used a non-logical hack (Var \= a) to avoid this.  A
much nicer way is to use coroutines.  Here is a solution in NU-Prolog:

?- good(LL) when LL.	% not really necessary
good([]).
good(A.As) :-
        all_same_length(As, A).

        % all elements of first list (of lists) have same
        % length as second list
	% The when declaration stops the outer list being instantiated
?- all_same_length(As, _) when As.
all_same_length([], _).
all_same_length(A.As, B) :-
        same_length(A, B),
        all_same_length(As, B).

        % two lists have the same length
	% The when declaration stops the inner lists being
	% instantiated unless there is another inner lists
	% which is already longer.
?- same_length(L1, L2) when L1 or L2.
same_length([], []).
same_length([_|Xs], [_|Ys]) :-
        same_length(Xs, Ys).

17?- good([]).
true.
18?- good([[a, b], [c, d]]).
true.
19?- good([[a], [b, c]]).
fail.
20?- good([_, _, _, [a], _, _, _, [b, c], _, _, _|_]).
fail.
21?- good([A, B, [C], D.E|F]).
Warning: Goal floundered.
F = F,
E = [],
D = D,
C = C,
B = [_WEIL],
A = [_WEIP] ;
fail.
22?- 

The last goal illustrates a bit more than what was originally requested.
The system determines that A and B must be lists of length 1 and E must
be the empty list.  The goal flounders because the program is smart
enough not to instantiate F (there are an infinite number of ways to do
so).

As well as the power of coroutines, the program illustrates a couple of
other points.  The first is the use of an auxillary predicate
all_same_length, rather than having one predicate which looks at two
list elements at a time.  There are advantages in terms of clause
indexing (no choice points are created, and no cuts are needed) and
structure creation (no extra cons cells are created, even with todays
not so clever compilers).

The second point is the representation of the length of lists.  The
worst way to do it is to call length and get an integer representation
for the length of the first list, then use length again to test
subsequent lists.  Using 'is' to add one to an integer is slower that
doing a simple unification in many Prolog system, and indexing is
generally more difficult with integers (typically you want to
distinguish between the zero case and non zero case).  Another, more
serious problem is that you can't hold incomplete information in
integers.  Consider the following query:

22?- good([[a], [a, b | T]]).
fail.

We know the second list has length greater than one, though the exact
length cannot be expressed as an integer.  Using integers to represent
lists, this query will not fail unless the Prolog system has fancy
numeric constraint handling.  The next most obvious alternative to
integers is to use the successor notation to represent list lengths.
In the example above the lengths are s(0) and s(s(X)), where X depends
on the length of T.  Since these two terms don't unify, the goal can be
made to fail easily (and the code for calculating lenghts is simpler and
probably faster).

This representation of list lengths can still be improved on slightly.
We can use the list itself to represent the length (as in the program
above).  There is no need to create any extra structures and we can use
indexing and simple unification nicely.  The program does not create any
choice points, even when the inner lists are constructed (the when
declaration on same_length causes indexing on both arguments).  The
program can therefore be run using stream and-parallelism, with no
changes.

	lee

markh@csd4.csd.uwm.edu (Mark William Hopkins) (12/24/89)

In article <11500022@hpldoda.UUCP> patch@hpldoda.UUCP (Pat Chkoreff) writes:
>Here's a challenge for you.  It's a stripped-down version of a problem I've
>been working on, and I haven't solved it yet.
>
>Write a predicate good/1 which succeeds if and only if its argument is a
>list of lists, where all of the lists have the same length.

This one I think is worth posting, because of the style in addition to its
being a solution.  It makes full use of the user-defineable precedence
grammar, as all good Prolog programs should, with the effect of giving it
the feel of natural language.

:- op(50, xf, good).
:- op(50, xfx, are_length).
:- op(50, xfx, is_length).

[] good :- !.
[Xs | Xss] good :- Xs is_length L, Xss are_length L.

[] are_length _ :- !.
[Xs | Xss] are_length L :- Xs is_length L, Xss are_length L.

[] is_length 0 :- !.
[_ | Xs] is_length L1 :- Xs is_length L, L1 is L + 1.

>The predicate should be written using pure Horn clauses -- no calls to !/0
>or var/1.

You can replace the clauses with cuts in them by unit-clauses.

>'Same length' is defined by:
>
>    same_length([], []).
>    same_length([_|Xs], [_|Ys]) :-
>        same_length(Xs, Ys).

same_length(Xs, Ys) :- Xs is_length L, Ys is_length L.

lee@munnari.oz.au (Lee Naish) (12/29/89)

In article <1633@uwm.edu> markh@csd4.csd.uwm.edu (Mark William Hopkins) writes:
>
>This one I think is worth posting, because of the style in addition to its
>being a solution.

In the absence of RAOK, I will make some comments...

>
>:- op(50, xf, good).
>:- op(50, xfx, are_length).
>:- op(50, xfx, is_length).
>
>[] good :- !.
>[Xs | Xss] good :- Xs is_length L, Xss are_length L.
>
>[] are_length _ :- !.
>[Xs | Xss] are_length L :- Xs is_length L, Xss are_length L.
>
>[] is_length 0 :- !.
>[_ | Xs] is_length L1 :- Xs is_length L, L1 is L + 1.
>
>You can replace the clauses with cuts in them by unit-clauses.

Then why put the cuts there???
None of the predicates work when their first argument is a variable.
When their first arguments are non-variables, any decent Prolog system
will use clause indexing the make the cuts redundent (they just make the
code confusing and, if the compiler isn't clever, slower).  The cuts do
prevent some infinite loops but at the cost of *incorrect* failure.

The definition of is_length can be made much more efficient by using an
accumulator (so it is tail-recursive).  It would also be nice if it
could be run backwards (not so easy, but possible).

>>'Same length' is defined by:
>>
>>    same_length([], []).
>>    same_length([_|Xs], [_|Ys]) :-
>>        same_length(Xs, Ys).
>
>same_length(Xs, Ys) :- Xs is_length L, Ys is_length L.

As I mentioned in my previous posting on this topic, representing list
lengths by Prolog integers is bad.  Consider the query
?- same_length([], [a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a]).
Using integers, the length of the second list has to be calculated, then
compared with zero.  Using other representations the query can fail
almost immediately.  It is also easier to make the code work when either
or both lists are input (the code above only works if both lists are
iput, since is_length is not reversible).  This makes good/1 less
flexible.

OK, enough criticism.  Here is a version of good/1 which is guaranteed
to finitely fail if (the existential closure of) the query is false in
all models.  The way to ensure this is to make it a binary program (no
clause body has more than one subgoal).  What we really need is a fair
computation rule, and what we have is Prolog's left to right rule.  If
the program is binary then the computation rule never has a choice and
therefore it must be fair.  Turning a non-binary program into a binary
program is always possible, but it can be a bit tricky to develop a
reasonably efficient version which has the right set of models:

good(Oss) :-
        good1(Oss, L, L).

        % First arg is lists of lists
        % Second arg is length of first list
        % Third arg is length of all subsequent list
good1([], _, _).
good1([].Oss, 0, LO) :-
        good1(Oss, LO, LO).
good1((_.Os).Oss, s(L), LO) :-
        good1((Os).Oss, L, LO).

Unfortunately, this version gets into a loop with the following
(relatively simple) query: ?- good([A, [a], [a,b]]). (Several other
posted "solutions" do also).  The reason is that there is an instance
which is true in a (non-Herbrand) model.

Here is a version which does work, though it is very complicated (and
took ages to write/debug).  There are probably simpler binary programs
with the "right" set of models - the challenge is still open I guess.
Alternatively, there might be non-binary programs which work ok even for
Prolog's computation rule.

	% idea is to scan lists in "diagonal" fashion
	% ie, first N elements of first list are scanned
	% in (about) the same time as the first N-1 elements
	% of the second list and the first element of the
	% Nth list (and the N+1th list is not examined at all
	% until after then).
good(Oss) :-
	good1([], L, Oss, [], [], L).

        % Maybe we could do it with fewer args, but.... 
	% First arg is front of outer list, with
	% elements of inner lists trimmed of diagonally.
	% Second arg is length of all elements.
	% Third arg is tail of original list (the bit not in first
	% arg).
	% Fourth+fifth args accumulate first arg with one more diagonal
	% trimmed off until first arg is scanned completely (need two
	% args to stop list being reversed - first is whole list,
	% second is tail).
	% Sixth arg is length of first element of first
	% arg (if first arg is not []).
good1([], _L, [], [], [], _LT).
good1([], s(L), [], TTs.TTss, [], _LT) :-
	good1(TTs.TTss, L, [], TTssA, TTssA, L).
good1([], L, Os.Oss, TTss, [], _LT) :-
	good1(Os.TTss, L, Oss, TTssA, TTssA, L).
good1([].[], L, Oss, TTss, [], 0) :-
	good1([], L, Oss, TTss, [], 0).
good1((_.TTs).Tss, L, Oss, TTss, TTs.TTssT, s(LT)) :-
	good1(Tss, L, Oss, TTss, TTssT, LT).

Its doesn't seem easy to add control information so this program won't
generate infinite answers but still fails when it can.  It also needs
complex clause indexing to run efficiently (ie, without creating choice
points).

I think I prefer the first version I posted :-).

	lee