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

Felipe Almeida Lessa felipe.lessa at gmail.com
Sat Jun 23 22:26:38 EDT 2007


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.


More information about the Haskell-Cafe mailing list