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

Просто посмотрел на 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)

Ответ 1

Вы проверили Hoogle?

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

Ответ 2

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

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

Ответ 3

Рассмотрите возможность использования пакета text (text в Hackage, теперь также являющегося частью платформы Haskell) для ваших потребностей в обработке текста. Он предоставляет текстовый тип Unicode, который более эффективен по времени и пространству, чем встроенный String на основе списка. Для поиска строк пакет text реализует Boyer-Moore алгоритм, который имеет лучшую сложность, чем наивный метод, используемый 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