Modifying and Adding to a list in Haskell

Question

I am implementing Burrows-Wheeler Transformation in Haskell. A combination of all cycled strings is generated and stored in a matrix as the first step of the transform. I am using Haskell List to construct the matrix. The list will store the original word on list head and its cyclic combinations down in tail.

Here is an Example of a transformed word

I have written a function that outputs the first cycled string. However, if I call the function again as a recursion, I face an infinite loop.

Here is the function

type BWT = [String] -- List of Strings for Burrows Wheeler matrix
samplebwt = ["BANANA$"] -- Sample input

rotateBWT:: BWT -> BWT
rotateBWT a = if (head (last a)) /= '$' 
    then [tail (head a) ++ [head (head a)]] ++ rotateBWT [tail (head a) ++ [head (head a)]] 
    else a

    rotateBWT samplebwt 
-- returns ["ANANA$B"]
--expected output ["ANANA$B", "NANA$BA", "ANA$BNA", "NA$BANA", "A$BANAN", "$BANANA"]

What am I missing?

break your code up into smaller parts that can be tested separately, or carefully trace the evaluation on your input with a pen and paper — jberryman
– jberryman, Commented Apr 26, 2016 at 15:39
Your code does generate all combinations (it duplicates the last one) but evidently you are not running the code you think you are. — user2407038
– user2407038, Commented Apr 26, 2016 at 15:45

TeWu · Accepted Answer · 2016-04-27 01:42:24Z

You can get into infinite loop when you invoke rotateBWT on string that doesn't contain $ character.

There you have a solution that generate output you've shown in example:

type BWT = [String] -- List of Strings for Burrows Wheeler matrix

genBWTmatrix :: String -> BWT
genBWTmatrix str = rotateBWT [str ++ "$"]

rotateBWT :: BWT -> BWT
rotateBWT a = if (head l) == '$' then a
              else a ++ rotateBWT n
                where l = last a
                      n = [(tail l) ++ [head l]]

main = mapM_ putStrLn $ genBWTmatrix "BANANA" -- Prints: BANANA$
                                              --         ANANA$B
                                              --         NANA$BA
                                              --         ANA$BAN
                                              --         NA$BANA
                                              --         A$BANAN
                                              --         $BANANA

Run it

Collectives™ on Stack Overflow

Modifying and Adding to a list in Haskell

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related