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

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

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 "прикажи своим людям"

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

ghci> encode 1 "веселиться вволю"

"гжтжмйуэт!ггпмя"

И вправду закодировано!

Декодирование сообщения – это всего навсего сдвиг обратно на то же количество позиций, на которое ранее проводился сдвиг вперёд.

decode :: Int -> String -> String

decode shift msg = encode (negate shift) msg

Теперь проверим, декодируется ли сообщение Цезаря:

ghci> decode 3 "тулеих#пгун"

"привет марк"

ghci> decode 5 "фхнпелн%цзунс%рйєс"

"прикажи своим людям"

ghci> decode 1 "гжтжмйуэт!ггпмя"

"веселиться вволю"

О строгих левых свёртках

В предыдущей главе мы видели, как работает функция foldl и как с её помощью реализовывать всякие крутые функции. Правда, мы пока не исследовали одну связанную с foldl ловушку: её использование иногда может приводить к так называемым ошибкам переполнения стека, которые случаются, если программе требуется слишком много места в одном специальном разделе памяти (в сегменте стека). Проиллюстрируем проблему, воспользовавшись свёрткой с функцией + для суммирования списка из сотни единиц:

ghci> foldl (+) 0 (replicate 100 1)

100

Пока всё работает. Но что если сделать то же самое для списка, содержащего, спасибо доктору Зло, один миллион единиц?

ghci> foldl (+) 0 (replicate 1000000 1)

*** Exception: stack overflow

Ого, жестоко! Что же случилось? Haskell ленив, поэтому он откладывает реальные вычисления настолько, насколько возможно. Когда мы используем foldl, Haskell не вычисляет аккумулятор на каждом шаге. Вместо этого он откладывает вычисление. На каждом следующем шаге он снова ничего не считает, опять откладывая на потом. Ему, правда, приходится сохранять старое отложенное вычисление в памяти, потому что новому может потребоваться его результат. Таким образом, пока свёртка foldl радостно торопится по списку, в памяти образуется куча отложенных вычислений, каждое из которых занимает некоторый объём памяти. Рано или поздно это может привести к ошибке переполнения стека.