Все вхождения подстроки в строке

Question

Мне нужна функция, чтобы найти все индексы подстрок в строке. Ниже вы можете найти свой код, но я просто интересно, если есть лучший способ сделать это:

-- find index of substring in string 
--  index_of_substring "so" "unsomesome" -> Just 2 
--  index_of_substring "to" "unsomesome" -> Nothing 
index_of_substring :: String -> String -> Maybe Int 
index_of_substring _ [] = Nothing 
index_of_substring sub str = case List.isPrefixOf sub str of 
    False -> fmap (+1) $ index_of_substring sub (tail str) 
    True -> Just 0 

-- find all occurences of pattern in a string 
--  all_occurrences_of_pattern_in_string "so" "unsomesomesome" -> [2,6,10] 
all_occurrences_of_pattern_in_string pattern s = helper pattern s [] 0 
    where helper pattern s result last_idx = case index_of_substring pattern s of 
      Just n -> helper pattern (drop (n + 1) s) (result ++ [n + last_idx]) (last_idx + n + 1) 
      Nothing -> result 

Answer 1

Я бы сказал, что это можно сделать проще, по крайней мере. Если точка не должна была написать свой собственный алгоритм с нуля (который я не думаю, что это так, поскольку вы используете Data.List.isPrefixOf), вы можете просто использовать Data.List.elemIndices, чтобы сократить количество проверок, которые Вы должны сделать:

indicesOfSubStr :: String -> String -> [Int] 
indicesOfSubStr [] _ = [] 
indicesOfSubStr sub str = filter (\i -> sub `isPrefixOf` drop i str) $ head sub `elemIndices` str 

indexOfSubStr :: String -> String -> Maybe Int 
indexOfSubStr = listToMaybe .: indicesOfSubStr where (.:) = (.) . (.) 

Итак, здесь я использую elemIndices, чтобы получить все индексы первого символа sub в str, а затем отфильтровать индексы, которые не совпадают, где sub не является префиксом, начинающимся с этого индекса. Это решает проблему поиска всех индексов.

Затем мы можем просто использовать эту функцию для indexOfSubStr. Я мог бы написать функцию, как

indexOfSubStr sub str = listToMaybe $ indicesOfSubStr sub str 

И в самом деле, это целых 8 символов короче, что путь, но я, как правило, оператор (.:) определяется уже и кому не нравится свободна? Если вы смущены тем, что он делает (определение несколько загадочно, как и сигнатура типа), он по существу просто составляет одну функцию аргумента с двумя аргументами.