Я хочу написать функцию Haskell с такой подписью типа:
findStr :: String -> String -> Maybe Int
findStr pat str попытается найти подстроку pat в строке str. В случае успеха он вернет Just n, где n – позиция pat в str.
Example:
findStr "abc" "abcdefg" -- returns Just 0
Попробуй это:
findStr :: String -> String -> Maybe Int
findStr pat str = findStrHelp pat str 0
where
findStrHelp _ [] _ = Nothing
findStrHelp pat [email protected](x:xs) n
| pat == (take (length pat) s) = Just n
| otherwise = findStrHelp pat xs (n+1)
findStr вызывает вспомогательную функцию, которая отслеживает текущий индекс. findStrHelp тогда просто нужно проверить, соответствует ли введенный шаблон следующей подстроке длины шаблона. Если это так, он возвращает Just <index> а затем проверяет следующую подстроку. Если он встречает пустой список, он терпит неудачу и возвращает Nothing.
Здесь другое решение, также использующее рекурсию:
findStr :: String -> String -> Maybe Int
findStr sub s
| length sub > length s = Nothing
| take (length sub) s == sub = Just 0
| otherwise = fmap (+1) $ findStr sub $ drop 1 s
Существует два условия завершения: либо подстрока больше, чем строка, и в этом случае Nothing возвращается (и мы останавливаем рекурсию), либо подстрока соответствует началу строки, и в этом случае мы останавливаем рекурсию, потому что имеем совпадение (мы return Just 0).
В случае, если ни одно из условий завершения не достигнуто, мы подсчитываем, где мы находимся, и возвращаем, отбрасывая первый символ строки.
Попробуй это:
findStr :: String -> String -> Maybe Int
findStr x y
| (length $ filtered x y) == 0 = Nothing
| otherwise = Just $ fst $ head $ filtered x y
filtered :: String -> String -> [(Int, String)]
filtered x y = filter (\(p,q) -> q == x) $ zip [0..(1 + lenY - lenX)] [take lenX $ drop n y | n <- [0..(lenY - lenX)]]
where lenX = length x
lenY = length y
filtered – вспомогательная функция, которая использует zip для создания списка пар ключ-значение индекса и соответствующей подстроки длины, равной длине pat, а затем получает те пары, которые соответствуют pat. findStr затем возвращает Nothing если приведенный выше список пуст, т.е. не найдено ни одного совпадения, или Just k где k – первый индекс соответствия.