Re: Narrowing vs. rewriting

From: Harold Boley <boley_at_informatik.uni-kl.de>
Date: Fri, 4 Jul 97 16:19:17 MET DST

Dear Phil and Friends,

I'm not sure if I understood the current Haskell version for serialise:

        before (x1,y1) (x2,y2) = x1 <= x2
        serialise l = map fst (sortBy before (zip (l, [1..])))

For instance, zip ([d,a,l,l,a,s], [1..]) seems to perform the same pairing
as zip ([d,a,l,l,a,s], [1,2,3,4,5,6]), and I don't see how this
ground pairing, i.e. [[d,1],[a,2],[l,3],[l,4],[a,5],[s,6]], can--via sortBy
and map fst--deliver the solution, [2,1,3,3,1,4], for serialise [d,a,l,l,a,s].

Note the role of logic variables as `declarative pointers' in the Relfun-like
version--created by pairlists `in R' (with some identified by qsort[before])
and ground-instantiated to lexicographic serial numbers only by numbered:

        pairlists([],[]) = []
        pairlists([X|L],[Y|M]) = [[X,Y]|pairlists(L,M)]

        numbered([],N).
        numbered([[X,N]|R],N) :- numbered(R,+(N,1)).

        before([X1,Y1],[X2,Y2]) :- string<(X1,X2).
                               
        serialise(L) = R if numbered(qsort[before](pairlists(L,R)),1)

Here is an inside-out derivation of this serialise solution (for details see
www.dfki.uni-kl.de/~vega/relfun+/sprachint/sprachinte/sprachinte-mainb.ps.gz)

>>>>>> pairlists([d,a,l,l,a,s],R)
[[d,Y1],[a,Y2],[l,Y3],[l,Y4],[a,Y5],[s,Y6]]
R=[Y1,Y2,Y3,Y4,Y5,Y6]

>>>>>> qsort[before]([[d,Y1],[a,Y2],[l,Y3],[l,Y4],[a,Y5],[s,Y6]])
[[a,Y2],[d,Y1],[l,Y3],[s,Y6]]
Y4=Y3
Y5=Y2

>>>>>> numbered([[a,Y2],[d,Y1],[l,Y3],[s,Y6]],1)
true
Y2=1, Y1=2, Y3=3, Y6=4

>>>>>> numbered(
             qsort[before](
                    pairlists([d,a,l,l,a,s],R)
                          ),
             1 )
true
R=[2,1,3,3,1,4]

Cheers, Harold.
Received on Fr Jul 04 1997 - 17:24:00 CEST