Naive Sort in Prolog

The simplest way to code a sort in Prolog is to describe what a sorted list looks like.  A sorted list is a permutation of some given list such that elements that appear earlier in the list are smaller than elements that appear later in the list.  In SWI Prolog:

srt(X,Y) :- permutation(X,Y), isSrt(Y).

isSrt([]).
isSrt([_]).
isSrt([H,I|J]) :- H=<I, isSrt([I|J]).

The beauty of this solution is that Prolog does all the dirty work of finding a sorted Y for our given X. The darker side is that Prolog’s satisfaction mechanism carries out a brute force search through all possible permutations of the given list. This is dangerous; compare the runtimes of our naive sort and the Prolog built-in sort (which is decidedly less naive):

% 5 seconds vs. something < 0.01 seconds
reverse([1,2,3,4,5,6,7,8,9,10],X), profile(srt(X,Y)).
reverse([1,2,3,4,5,6,7,8,9,10],X), profile(msort(X,Y)).

Not great, and notice how fast the worst case time of O(n!) grows:

% 55 seconds vs. something < 0.01 seconds
reverse([1,2,3,4,5,6,7,8,9,10,11],X), profile(srt(X,Y)).
reverse([1,2,3,4,5,6,7,8,9,10,11],X), profile(msort(X,Y)).

This is to be expected; if we want to be picky about how the job gets done, we can be more explicit in our description. So let’s ignore performance and and see how to write a declarative “permutation” predicate from scratch.

Ugly Permutations

Skip this section unless you’re interested in how a simple idea is translated into a complex and unattractive Prolog solution.

Abandoning all performance considerations for a kind of extreme descriptive minimalism, I considered the following definition for a permutation of a list: each item in the given list is in the permutation and each item in the permutation is in the list. As Prolog searches for all possible lists that satisfy this rule, it should produce all permutations of the given list.

I started by trying to define a membr/2 predicate such that it would succeed when all items in the first list are in the second list. Attempts at extending this into something that would produce permutations caused infinite loops and stack overflows until I settled on this definition:

membr([H|T],Y) :- 
    length(Y,L), length(T,M), M<L, 
    member(H,Y), membr(T,Y).
membr([],Y) :- allNonVar(Y). 

allNonVar([]).
allNonVar([H|T]) :- nonvar(H), allNonVar(T).

srt(X,Y) :- membr(X,Y), isSrt(Y), !.

Where member/2 is a built-in predicate with a straightforward Prolog implementation.

The clauses dealing with length prevent len(Y) < len(X) if X contains duplicates. The predicate allNonVar/1 prevents Y from having extra, un-unified anonymous variables. These can be left unbound when Y is forced to be a certain length, but duplicates in X always match to the first occurrence of the duplicate value in Y. These can also be left unbound when the member/2 goal posits extra anonymous variables; membr(X,[Y|_junk1,_junk2]) would otherwise be true.

Finally, the cut at the end of srt/2 prevents the consideration of equivalent permutations of the input list when it contains duplicates.

Pretty Permutations

The implementation of a simple definition of permutation ended up looking rather ugly because it had to fight the Prolog search mechanism.

A prettier implementation of a permutation predicate is given in Clocksin and Mellish, Programming in Prolog, Springer, 2003:

perm([],[]).
perm(L,[H|T]) :- 
    append(V,[H|U],L), 
    append(V,U,W), 
    perm(W,T).

This states that a permutation of L is something that has as its head an element H drawn from L, and which is followed by something that is a permutation of the remaining elements of L.  Most of the permutation definitions on the web are built like this one, but I like its use of append/3.

Advertisements

Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: