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