Есть ли лучший способ написать метод "строка содержит X"?

Question

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

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

Остальные возможности я использовал для сопоставления с образцом. Вот что я придумал:

stringExists "" wordToCheckAgainst = False
stringExists wordToCheckFor "" = False
stringExists wordToCheckFor wordToCheckAgainst | length wordToCheckAgainst < length wordToCheckFor = False
                                               | length wordToCheckAgainst == length wordToCheckFor = wordToCheckAgainst == wordToCheckFor
                                               | take (length wordToCheckFor) wordToCheckAgainst == wordToCheckFor = True
                                               | otherwise = stringExists wordToCheckFor (tail wordToCheckAgainst)

Answer 1

Если вы ищете Hoogle для подписи искомой функции (String -> String -> Bool), вы должны увидеть isInfixOf среди лучших результатов.

Answer 2

isInfixOf из Data.List наверняка решит проблему, однако в случае более длинных стогов сена или извращенных игл вам следует рассмотреть более продвинутые алгоритмы сопоставления строк с гораздо лучшим средними сложность наихудшего случая.

---

¹ Рассмотрим действительно длинную строку, состоящую только из a и иголку с большим количеством a в начале и одним b вконец.

Answer 3

Подумайте об использовании пакета text (text в Hackage, теперь также является частью платформы Haskell) для ваших потребностей в обработке текста. Он предоставляет текстовый тип Unicode, который более экономичен во времени и пространстве, чем встроенный список String. Для поиска строк пакет text реализует a алгоритм Бойера-Мура , который имеет более сложную структуру, чем простой метод, используемый Data.List.isInfixOf.

Пример использования:

Prelude> :s -XOverloadedStrings
Prelude> import qualified Data.Text as T
Prelude Data.Text> T.breakOnAll "abc" "defabcged"
[("def","abcged")]
Prelude Data.Text> T.isInfixOf "abc" "defabcged"
True