Миран Липовача - Изучай Haskell во имя добра!

Модули стандартной библиотеки содержат массу функций, способных облегчить программирование на языке Haskell. Познакомимся с некоторыми из них, решая конкретные задачи.

Предположим, что у нас имеется строка, содержащая много слов. Мы хотим выяснить, сколько раз в этой строке встречается каждое слово. Первой функцией, которую мы применим, будет функция wordsиз модуля Data.List. Эта функция преобразует строку в список строк, в котором каждая строка представляет одно слово из исходной строки. Небольшой пример:

ghci> words "всё это слова в этом предложении"

["всё","это","слова","в","этом","предложении"]

ghci> words "всё это слова в этом предложении"

["всё","это","слова","в","этом","предложении"]

Затем воспользуемся функцией group, которая тоже «живёт» в Data.List, чтобы сгруппировать одинаковые слова. Эта функция принимает список и собирает одинаковые подряд идущие элементы в подсписки:

ghci> group [1,1,1,1,2,2,2,2,3,3,2,2,2,5,6,7]

[[1,1,1,1],[2,2,2,2],[3,3],[2,2,2],[5],[6],[7]]

Но что если одинаковые элементы идут в списке не подряд?

ghci> group ["бум","бип","бип","бум","бум"]

[["бум"],["бип","бип"],["бум","бум"]]

Получаем два списка, содержащих "бум", тогда как нам бы хотелось, чтобы все вхождения одного и того же слова попали в один список. Что делать? Мы можем предварительно отсортировать список! Для этого применим функцию sortиз Data.List. Она принимает список элементов, которые могут быть упорядочены, и возвращает новый список, содержащий те же элементы, но упорядоченные от наименьшего к наибольшему:

ghci> sort [5,4,3,7,2,1]

[1,2,3,4,5,7]

ghci> sort ["бум","бип","бип","бум","бум"]

["бип","бип","бум","бум","бум"]

Заметим, что строки упорядочены по алфавиту.

Теперь всё необходимое у нас есть, осталось только записать решение. Берём строку, разбиваем её на список слов, сортируем слова и группируем одинаковые. Затем применяем mapи получаем список вроде ("boom", 3); это означает, что слово "boom"встретилось в исходной строке трижды.

import Data.List

wordNums :: String -> [(String, Int)]

wordNums = map (\ws -> (head ws, length ws)) . group . sort . words

Для написания этой функции мы применили композицию функций. Предположим, что мы вызвали функцию wordNumsдля строки "уа уа уи уа". К этой строке применяется функция words, результатом которой будет список ["уа","уа","уи","уа"]. После его сортировки функцией sortполучим новый список ["уа","уа","уа","уи"]. Группировка одинаковых подряд идущих слов функцией groupдаст нам список [["уа","уа","уа"],["уи"]]. Затем с помощью функции mapк каждому элементу такого списка (то есть к подсписку) будет применена анонимная функция, которая превращает список в пару – «голова» списка, длина списка. В конечном счёте получаем [("уа",3),("уи",1)].

Вот как можно написать ту же функцию, не пользуясь операцией композиции:

wordNums xs = map (\ws -> (head ws, length ws)) (group (sort (words xs)))

Кажется, здесь избыток скобок! Думаю, нетрудно заметить, насколько более читаемой делает функцию операция композиции.

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