Re: Narrowing vs. rewriting

From: Harold Boley <boley_at_informatik.uni-kl.de>
Date: Tue, 8 Jul 97 15:32:50 MET DST

The serialise program can be based on a non-ground functional qsort
performing unfications instead of ground-equality comparisons for
duplicate removals (generally, `unifiables identifications'), and
still avoiding the problem for ground arguments pointed out by Phil
(the syntax is as earlier in this thread, augmented by a deterministic
conditional):

qsort[Cr]([]) = []
qsort[Cr]([X|Y]) = qsort[Cr](Sm) ++ [X] ++ qsort[Cr](Gr)
   if [Sm,Gr] = partition[Cr](X,Y)

partition[Cr](X,[]) = [[],[]]
partition[Cr](X,[Y|Z]) = cond( Cr(Y,X), [[Y|Sm],Gr], % apply relation
                                 Y=X, [Sm,Gr], % unify elements
                                 true, [Sm,[Y|Gr]] ) % catch all case
   if [Sm,Gr] = partition[Cr](X,Z)

before([X1,Y1],[X2,Y2]) :- string<(X1,X2).

While in serialise the second elements of pairs are always (pairlists-
generated) logic variables, this qsort can also be used--with the above
`selective' comparison relation before--on lists of pairs of constants.

Thus Phil's sample ground call

        qsort[before]([[a,1],[a,2]])

returns [[a,1],[a,2]], but the non-ground call

        qsort[before]([[a,Y2],[a,Y5]])

returns [[a,Y2]] and identifies Y5 with Y2.

Thanks for pointing out this subtle issue, Harold.
Received on Di Jul 08 1997 - 16:41:00 CEST