Re: Narrowing vs. rewriting

From: Philip Wadler <wadler_at_research.bell-labs.com>
Date: Mon, 07 Jul 1997 11:43:37 -0400

I think the serialise example is too small to be of serious interest,
but to be polite I owe Harold a reply. I misread Harold's
specification of serialise, so my Haskell program is incorrect.
I give a correct one below.

However, Harold's program seems to require a rather odd sort.
I could reasonably expect that

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

returns either [[a,1],[a,2]] or [[a,2],[a,1]], depending on whether it
is a stable sort or not, but I gather that Harold's version returns
neither, yielding failure instead (since it cannot equate 1 and 2).
It would be helpful to see the code for qsort -- I gather there's
something rather subtle going on there.

Here's the corrected Haskell version.

        serialise l = map (lookup s) l
                    where s = zip (nub (sortBy before l), [1..])
        before (x1,y1) (x2,y2) = x1 <= x2
        lookup xys x0 = head [ y | (x,y) <- xys, x == x0 ]

Here nub removes duplicates from a list; or one could rewrite sortBy
to remove duplicates.

Cheers, -- P
Received on Mo Jul 07 1997 - 18:44:00 CEST