On 6/23/07, Bertram Felgenhauer
"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.