Thursday, 29 September 2011

Seven in Seven - Prolog is doing my head in.

It's day 2 of the Prolog section and my brain is suffering, I had forgotten how much unlike other languages Prolog is, and we haven't even got to backtracking yet. Things got so bad that I dug out my original copy of Clocksin and Mellish -It is so old the pages have actually yellowed and the reference implementations are for a DEC-10 and PDP-11! It seems to be helping to think of Prolog as a goal-seeking database, i.e. a collection of facts that you can ask questions of, it's quite cute that when you run a program Prolog answers 'yes' or 'no'.

Anyway the exercises, trivially they can be answered thus :

| ?- reverse([12,4,5,7],SL).

SL = [7,5,4,12]

| ?- min_list([12,4,5,7],SL).

SL = 4

| ?- sort([12,4,5,7],SL).  

SL = [4,5,7,12]

(1 ms) yes

But we ought to try a bit harder, so :

revappend([], Ys, Ys).
revappend([X|Xs], Ys, Zs) :- revappend(Xs, [X|Ys], Zs).

rev(Xs,Ys) :- revappend(Xs,[],Ys).

I pinched this in the end, after repeated attempts to use 'is' on something that isn't an arithmetic expression.

smallest(S,[H|T]) :- smallest(Ss,T), H >= Ss, S is Ss.
smallest(S,[H|T]) :- smallest(Ss,T), H < Ss, S is H.
This one is all mine, alas. It's not tail-recursive so it would be inefficient. Here I have added a rule for each case -but it might be possible to use an 'if' statement.

Finally the sort -I can't imagine that this is very efficient either, it works by taking the smallest member off the original list and putting it add the head of a new list, this happens repeatedly (through recursion) until the original list is empty :-

jsort([], Ys, Ys).
jsort(Xs, Ys, Zs) :- min_list(Xs,S), delete(Xs,S,X1s), jsort(X1s, [S|Ys], Zs).

sortj(Xs,Ys) :- jsort(Xs,[],Ys).

No comments:

Post a Comment