Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!mailrus!cornell!uw-beaver!teknowledge-vaxc!sri-unix!quintus!ok
From: ok@quintus
Newsgroups: comp.lang.prolog
Subject: Elegance=efficiency, the continuing story
Message-ID: <177@quintus.UUCP>
Date: 20 Jul 88 01:47:32 GMT
Sender: news@quintus.UUCP
Reply-To: ok@quintus ()
Organization: Quintus Computer Systems, Inc.
Lines: 50

I saw (never mind where) the following definition today:

/*1*/	permute(X, [A|Z]) :-
		select(A, X, Y),
		permute(Y, Z).
	permute([], []).

where select/3 is the usual

	select(Item, [Item|Set], Set).
	select(Item, [OtherItem|Set0], [OtherItem|Set]) :-
		select(Item, Set0, Set).

This version of permute/2 looked ugly to me.
(1) From Clocksin & Mellish 1st edition I learned to put base cases
    _first_.  It is _much_ the clearest place to put them.
(2) It isn't obvious from the code that the induction is really on
    the *first* argument of permute/2: if the first argument is unbound
    permute/2 may fail to terminate even if the second argument is ground.

A version which has neither of these defects is

/*2*/	permute([], []).		% to permute [], return []
	permute([X|Xs], Ys1) :-		% to permute [X|Xs],
		permute(Xs, Ys),	% permute Xs giving Ys
		select(X, Ys1, Ys).	% insert X anywhere in Ys giving Ys1

Now, I think this version is much easier to read.
The reason for the title of this message is that it turns out to be
considerably faster in Quintus Prolog:  4 times faster for tiny lists,
5 times faster for 10 element lists.  I can explain the result after
the event, but I wasn't expecting anywhere near that big a difference.
Elegance pays!

Of course, that version still suffers from the well known problem that
it can't be used to solve for the first argument given the second.
But at least it is a bit less surprising that that is so.  In fact we
can easily fix that bug and produce a satisfactory permute/2:

/*2*/	permute(Xs, Ys) :-
		permute(Xs, Ys, Ys).

	permute([], [], []).
	permute([X|Xs], Ys1, [_|Zs]) :-
		permute(Xs, Ys, Zs),
		select(X, Ys1, Ys).

This is a bit less than twice as slow as version /*2*/, but it is
more than twice as fast as version /*1*/ and works both ways around.
[permute(Xs, Ys, Zs) checks that Xs and Zs are the same length, so
that if Ys is known, it will terminate.]