Изучай Haskell во имя добра! (Липовача) - страница 69
Кажется, здесь избыток скобок! Думаю, нетрудно заметить, насколько более читаемой делает функцию операция композиции.
Иголка в стоге сена
Следующая наша миссия – написание функции, которая принимает на вход два списка и сообщает, содержится ли первый список целиком где-нибудь внутри второго. Например, список >[3,4] содержится внутри >[1,2,3,4,5], а вот >[2,5] – уже нет. Список, в котором мы ищем, назовём стогом, а список, который хотим обнаружить, – иголкой.
Чтобы выбраться из этой передряги, воспользуемся функцией >tails из того же модуля >Data.List. Она принимает список и последовательно применяет к нему функцию >tail. Вот пример:
>ghci> tails "победа"
>["победа","обеда","беда","еда","да","а",""]
>ghci> tails [1,2,3]
>[[1,2,3],[2,3],[3],[]]
Возможно, пока неясно, зачем она нам вообще понадобилась. Сейчас увидим.
Предположим, мы хотим найти строку >"обед" внутри строки >"победа". Для начала вызовем >tails и получим все «хвосты» списка. Затем присмотримся к каждому «хвосту», и если хоть какой-нибудь из них начинается со строки >"обед", значит, иголка найдена! Вот если бы мы искали >"фуу" внутри >"победа" – тогда да, ни один из «хвостов» с >"фуу" не начинается.
Чтобы узнать, не начинается ли одна строка с другой, мы применим функцию >isPrefixOf, снова из модуля >Data.List. Ей на вход подаются два списка, а она отвечает, начинается второй список с первого или нет.
>ghci> "гавайи" `isPrefixOf` "гавайи джо"
>True
>ghci> "ха-ха" `isPrefixOf` "ха"
>False
>ghci> "ха" `isPrefixOf` "ха"
>True
Теперь нужно лишь проверить, начинается ли какой-нибудь из хвостов нашего стога с иголки. Тут поможет функция >any из >Data.
>List. Она принимает предикат и список и сообщает, удовлетворяет ли этому предикату хотя бы один элемент списка. Внимание:
>ghci> any (>4) [1,2,3]
>False
>ghci> any (=='Х') "Грегори Хаус"
>True
>ghci> any (\x -> x > 5 && x < 10) [1,4,11]
>False
Соберём все эти функции вместе:
>import Data.List
>isIn :: (Eq a) => [a] -> [a] -> Bool
>needle `isIn` haystack = any (needle `isPrefixOf`) (tails haystack)
Вот и всё! Функция >tails создаёт список «хвостов» нашего стога, а затем мы смотрим, начинается ли что-нибудь из них с иголки. Проверим:
>ghci> "обед" `isIn` "победа"
>True
>ghci> [1,2] `isIn` [1,3,5]
>False
Ой, подождите-ка! Кажется, только что написанная функция уже есть в >Data.List… Ба-а, и правда! Она называется >isInfixOf и делает в точности то же, что наша >isIn.
Салат из шифра Цезаря
Гай Юлий Цезарь возложил на нас ответственное поручение. Необходимо доставить совершенно секретное сообщение в Галлию Марку Антонию. На случай, если нас схватят, мы закодируем сообщение шифром Цезаря, воспользовавшись с этой целью некоторыми функциями из модуля