Изучай Haskell во имя добра!

Иголка в стоге сена

Следующая наша миссия – написание функции, которая принимает на вход два списка и сообщает, содержится ли первый список целиком где-нибудь внутри второго. Например, список [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.

Салат из шифра Цезаря

Гай Юлий Цезарь возложил на нас ответственное поручение. Необходимо доставить совершенно секретное сообщение в Галлию Марку Антонию. На случай, если нас схватят, мы закодируем сообщение шифром Цезаря, воспользовавшись с этой целью некоторыми функциями из модуля Data.Char.

Шифр Цезаря – это простой метод кодирования сообщения путём сдвига каждого символа на фиксированное количество позиций алфавита. На самом деле мы реализуем некую вариацию шифра Цезаря, поскольку не будем ограничиваться только алфавитом, а возьмём весь диапазон символов Unicode.

Для сдвига символов вперёд и назад по кодовой таблице будем применять функции ord и chr, находящиеся в модуле Data.Char. Эти функции преобразуют символы к соответствующим кодам и наоборот:

ghci> ord 'a'

97

ghci> chr 97

'a'

ghci> map ord "abcdefgh"

[97,98,99,100,101,102,103,104]

Функция ord 'a' возвращает 97, поскольку символ 'a' является девяносто седьмым символом в таблице символов Unicode.

Разность между значениями функции ord для двух символов равна расстоянию между ними в кодовой таблице.

Напишем функцию, которая принимает количество позиций сдвига и строку и возвращает новую строку, где каждый символ сдвинут вперёд по кодовой таблице на указанное число позиций.

import Data.Char

encode :: Int -> String -> String

encode offset msg = map (\c -> chr $ ord c + offset) msg

Кодирование строки тривиально настолько, насколько легко взять сообщение и пройтись по каждому его символу функцией, преобразующей его в соответствующий код, прибавляющей смещение и конвертирующей результат обратно в символ. Любитель композиции записал бы такую функцию как (chr . (+offset) . ord).

ghci> encode 3 "привет марк"

"тулеих#пгун"

ghci> encode 5 "прикажи своим людям"

"фхнпелн%цзунс%рйєс"