Hi,<br><br>I think that version is still a brute-force solution. The only difference is that it uses EOF (sentinel) so that it can sort the suffixes instead of rotations.<br>However, the big-O complexity is the same.<br><br>Let's take the rbwt for example:<br><pre>&gt; rbwt xs = let
&gt;     res = sortBy (\(a:as) (b:bs) -&gt; a `compare` b) (zipWith' (:) xs res)
&gt;   in
&gt;     tail . map snd . zip xs $ head res</pre>Here we can see that, although the infinity res is lazy-evaluated, it actually sorts the matrix N times, adding one column per evaluation.<br>each time there are N elements to be sorted and the length of every element grows proportion to N, <br>so the time is O( N * (N^2) * \lg (N^2) ) = O(N^3 \lg N)<br><br>While my brute-force program provided in previous post is as same as O(N^3 \lg N).<br><br>However, if the random access time is O(1) (on array) but not O(N) (on list), my 2nd program is much faster:<br>Here is the modified version with Array. (import Data.Array)<br><br>ibwt'' :: (Ord a) =&gt; ([a], Int) -&gt; [a]<br>ibwt'' (r, i) =&nbsp; fst $ iterate f ([], i) !! n where<br>&nbsp;&nbsp;&nbsp; t = listArray (0, n-1) $ map snd $ sort $ zip r [0..]<br>&nbsp;&nbsp;&nbsp; ra = listArray (0, n-1) r<br>&nbsp;&nbsp;&nbsp; f (s, j) = let j' = t ! j in (s++[ra ! j'], j')<br>&nbsp;&nbsp;&nbsp; n = length r<br><br>This version only sort the input data 1 time, (proportion to O(N * \lg N), after that the transform vector t is generated.<br>Then it iterates N times on t to get the result. so the total time is O(N * \lg N) + O(N) = O(N * \lg N)<br><br>This should be much better than the brute force one. the idea is that, we can get the result without reconstructing the complete matrix,<br>Only two columns (L &amp; F) are enough.<br><br>But how to turn the random access idea of transform-vector into purely functional settings? here I mean what if Haskell<br>doesn't provide constant access time array? One idea is to to turn the transform vector T into a function, just like what we've done in KMP implementation in FP way. Does such solution exist?<br><br>Regards.<br>--<br>Larry, LIU Xinyu<br>https://github.com/liuxinyu95/AlgoXY<br><br>On Friday, June 24, 2011 6:50:46 AM UTC+8, Henning Thielemann wrote:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><br>On Wed, 22 Jun 2011, larry.liuxinyu wrote:<p>&gt; Hi,<br>&gt; <br>&gt; I read a previous thread about BWT implementation in Haskell:<br>&gt; <a href="http://www.mail-archive.com/haskell-cafe@haskell.org/msg25609.html" target="_blank">http://www.mail-archive.com/<wbr>haskell-cafe@haskell.org/<wbr>msg25609.html</a><br>&gt; and<br>&gt; <a href="http://sambangu.blogspot.com/2007/01/burrows-wheeler-transform-in-haskell" target="_blank">http://sambangu.blogspot.com/<wbr>2007/01/burrows-wheeler-<wbr>transform-in-haskell</a><br>&gt; <br>&gt; They are all in a `brute-force' way, that is implement based on Burrows-Wheeler's definition like below:</p><p>I thought that the knot-tying solution by Bertram Felgenhauer in the same <br>thread was both elegant and efficient:<br>&nbsp; &nbsp;<a href="http://www.mail-archive.com/haskell-cafe%40haskell.org/msg25692.html" target="_blank">http://www.mail-archive.com/<wbr>haskell-cafe%40haskell.org/<wbr>msg25692.html</a></p><p>______________________________<wbr>_________________<br>Haskell-Cafe mailing list<br><a>Haskel...@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/<wbr>mailman/listinfo/haskell-cafe</a><br></p><p></p><p></p></blockquote>