Изменение и добавление к списку в Haskell

Question

Я реализую преобразование Burrows-Wheeler в Haskell. Комбинация всех циклических строк генерируется и сохраняется в матрице в качестве первого шага преобразования. Я использую Haskell List для построения матрицы. Список сохранит исходное слово в заголовке списка и его циклические комбинации в хвосте.

Here is an Example of a transformed word

Я написал функцию, которая выводит первую строку циклически. Однако, если я снова вызову функцию как рекурсию, я столкнулся с бесконечным циклом.

Вот функция

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"] 

Что мне не хватает?

Answer 1

Вы можете получить бесконечный цикл, когда вы вызываете rotateBWT на строку, которая не содержит символ $.

Там у вас есть решение, которое генерирует выходной сигнал вы показали в примере:

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