Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!samsung!munnari.oz.au!murtoa.cs.mu.oz.au!ditmela!latcs1!mahler
From: mahler@latcs1.oz.au (Daniel Mahler)
Newsgroups: comp.lang.prolog
Subject: Re: A Challenge
Message-ID: <7038@latcs1.oz.au>
Date: 18 Dec 89 04:31:35 GMT
References: <11500022@hpldoda.UUCP>
Reply-To: mahler@latcs1.oz (Daniel Mahler)
Organization: Comp Sci, La Trobe Uni, Australia
Lines: 36


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