Как исключить центры затрат в таверсах строк и составлении списков

Я реализую алгоритм поиска мотивов из области биоинформатики с использованием Haskell. Я не буду вдаваться в подробности алгоритма, кроме как сказать, что это поиск по ветвям и привязкам медианной строки.Я планировал сделать свою реализацию более интересной, реализуя параллельный подход (а затем подход STM), чтобы получить многоядерную скорость, но после компиляции с помощью следующих флагов

$ ghc -prof -auto-all -O2 -fllvm -threaded -rtsopts --make main 

и печати профиля я увидел кое-что интересное (и, возможно, очевидно):

COST CENTRE      entries  %time %alloc  
hammingDistance  34677951  47.6   14.7  
motifs           4835446   43.8   71.1  

Ясно, что можно добиться значительного ускорения, даже не приближаясь к многоядерному программированию (хотя это было сделано, и мне просто нужно найти хорошие тестовые данные и разобраться с критериями для этого).

В любом случае, обе эти функции являются чисто функциональными и никоим образом не параллельны. Кроме того, они делают довольно простые вещи, поэтому я был удивлен, что на них уходит так много времени. Вот их код:

data NukeTide = A | T | C | G deriving (Read, Show, Eq, Ord, Enum)

type Motif = [NukeTide] 

hammingDistance :: Motif -> Motif -> Int
hammingDistance [] [] = 0
hammingDistance xs [] = 0 -- optimistic
hammingDistance [] ys = 0 -- optimistic
hammingDistance (x:xs) (y:ys) = case (x == y) of
    True  -> hammingDistance xs ys
    False -> 1 + hammingDistance xs ys

motifs :: Int -> [a] -> [[a]]
motifs n nukeTides = [ take n $ drop k nukeTides | k <- [0..length nukeTides - n] ]

Обратите внимание, что из двух аргументов hammingDistance я могу предположить, что xs будет иметь длину x, а ys будет меньше или равно этому значению, если это открывает место для улучшения.

Как видите, hammingDistance вычисляет расстояние Хэмминга между двумя мотивами, которые представляют собой списки нуклеотидов. Функция motifs принимает число и список и возвращает все подстроки этой длины, например :

> motifs 3 "hello world"
["hel","ell","llo","lo ","o w"," wo","wor","orl","rld"]

. Поскольку задействованные алгоритмические процессы настолько просты, я не могу придумать способ их дальнейшей оптимизации. Однако у меня есть два предположения относительно того, куда мне следует двигаться:

1. HammingDistance: Типы данных, которые я использую (NukeTides и []), медленные / неуклюжие. Это всего лишь предположение, поскольку я не знаком с их реализациями, но я думаю, что определение моего собственного типа данных, хотя и более разборчиво, вероятно, потребует больше накладных расходов, чем я предполагал.Также сопоставление с образцом для меня чуждо, я не знаю, тривиально это или дорого.
2. Мотивы: Если я правильно это читаю, 70% всей памяти выделяется по мотивам, и я предполагаю, что когда-нибудь это придется собирать мусором. Опять же, использование универсального списка может замедлить меня или понимание списка, поскольку стоимость этого для меня невероятно неясна.

Кто-нибудь может посоветовать здесь обычную процедуру? Если проблема заключается в типах данных, будут ли массивы правильным ответом? (Я слышал, они приходят в коробках)

Спасибо за помощь.

Edit: Мне только что пришло в голову, что было бы полезно, если бы я описал способ, которым вызываются эти две функции:

totalDistance :: Motif -> Int
totalDistance motif = sum $ map (minimum . map (hammingDistance motif) . motifs l) dna

Эта функция является результатом другой функции и передается по узлам в дереве. В каждом узле дерева выполняется оценка нуклеотида (длины <= n, то есть, если == n, то это листовой узел), с использованием totalDistance для оценки узла. С этого момента это ваш типичный алгоритм ветвления и привязки.

Редактировать: Джон попросил меня распечатать внесенное мной изменение, которое фактически устранило стоимость мотивов:

scoreFunction :: DNA -> Int -> (Motif -> Int)
scoreFunction dna l = totalDistance
    where
        -- The sum of the minimum hamming distance in each line of dna
        -- is given by totalDistance motif
        totalDistance motif = sum $ map (minimum . map (hammingDistance motif)) possibleMotifs
        possibleMotifs = map (motifs l) dna -- Previously this was computed in the line above

Я не разъяснил это в своем исходном сообщении, но scoreFunction вызывается только один раз, и результат передается в обходе / ветвлении и привязке дерева и используется для оценки узлов. Оглядываясь назад, переосмысление мотивов на каждом этапе пути - не одна из самых ярких вещей, которые я делал.