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

Question

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

Вот пример преобразованного слова

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

Вот функция

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

Запустить его