[Haskell-cafe] Re: Need for speed: the Burrows-Wheeler Transform

[Felipe Almeida Lessa]

On 6/23/07, Bertram Felgenhauer <bertram.felgenhauer at googlemail.com> wrote:
> "rbwt" implements the corresponding inverse BWT. It's a fun knot tying
> exercise.
>
> > rbwt xs = let
> >     res = sortBy (\(a:as) (b:bs) -> a `compare` b) (zipWith' (:) xs res)
> >   in
> >     tail . map snd . zip xs $ head res

Indeed it's very fun =). Although I must admit that, even after
staring at the code for some time, I still don't see how it works. Is
it too much to ask for a brief explanation?

I see that zipWith' creates all the lazy list without requiring any
knowledge of the second list, which means that the list to be sorted
is created nicely. But when sortBy needs to compare, say, the first
with the second items, it forces the thunk of the lazy list. But that
thunk depends on the sorted list itself!

What am I missing? ;)

Thanks in advance,

-- 
Felipe.