Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!lee
From: lee@munnari.oz.au (Lee Naish)
Newsgroups: comp.lang.prolog
Subject: Re: A Challenge
Message-ID: <2949@munnari.oz.au>
Date: 21 Dec 89 06:36:45 GMT
References: <11500022@hpldoda.UUCP>
Sender: news@cs.mu.oz.au
Reply-To: lee@munmurra.UUCP (Lee Naish)
Organization: Comp Sci, University of Melbourne
Lines: 115

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