Re: Narrowing vs. rewriting

From: Harold Boley <>
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([[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

>>>>>> pairlists([d,a,l,l,a,s],R)

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

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

>>>>>> numbered(
             1 )

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

This archive was generated by hypermail 2.3.0 : So Jul 05 2020 - 07:15:03 CEST