Есть ли лучший способ написать метод «string contains 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, безусловно, решить эту проблему, однако в случае длинных стога или perverse¹ игл вы должны рассмотреть более продвинутое string matching algorithms с намного лучше средней и худшим случаем сложностью.

---

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

Answer 3

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