Решение задач средствами стандартных модулей

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

 

Подсчёт слов

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

1 В тех же целях издательством «ДМК Пресс» выпущена книга: Душкин Р. В. Справочник по языку Haskell. – М.: ДМК Пресс, 2008. – 544 стр., ил. ISBN 5–94074–410–9.

 

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

РЕШЕНИЕ ЗАДАЧ СРЕДСТВАМИ СТАНДАРТНЫХ МоДулЕй 129

Ой, подождите-ка! Кажется, только что написанная функция уже есть в 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 радостно торопится по списку, в памяти образу- ется куча отложенных вычислений, каждое из которых занимает некоторый объём памяти. Рано или поздно это может привести к ошибке переполнения стека.

Вот как Haskell вычисляет выражение foldl (+) 0 [1,2,3]:

foldl (+) 0 [1,2,3] =

foldl (+) (0 + 1) [2,3] =

foldl (+) ((0 + 1) + 2) [3] =

foldl (+) (((0 + 1) + 2) + 3) [] =

((0 + 1) + 2) + 3 =

(1+2) + 3 =

3 + 3 =

6

 

Здесь видно, что сначала строится большой стек из отложен- ных вычислений. Затем, по достижении конца списка, начинаются реальные вычисления. Для маленьких списков никакой проблемы нет, а вот если список громадный, с миллионом элементов или даже больше, вы и получите переполнение стека. Дело в том, что все эти отложенные вычисления выполняются рекурсивно. Было бы неплохо, если бы существовала функция, которая вычисления не откладывает, правда же? Она бы работала как-то так:

foldl' (+) 0 [1,2,3] =

foldl' (+) 1 [2,3] =

foldl' (+) 3 [3] =

foldl (+) 6 [] = 6

Вычисления между шагами свёртки не откладываются – они тут же выполняются. Ну что ж, нам повезло: строгая версия функции foldl в модуле Data.List есть, и называется она именно foldl'. Поп- робуем-ка с её помощью вычислить сумму миллиона единиц:

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

1000000

Потрясающий успех! Так что, если, используя foldl, получите ошибку переполнения стека, попробуйте переключиться на foldl'. Кстати, у foldl1 тоже есть строгая версия, она называется foldl1'.

 

Поищем числа

Вы прогуливаетесь по улице, и тут к вам подходит старушка и спрашивает: «Прос- тите, а каково первое натуральное число, сумма цифр которого равна 40?»

Ну что, сдулись? Давайте применим Haskell-магию и найдём это число. Если мы, к примеру, просуммируем цифры чис- ла 123, то получим 6. У какого же числа тог- да сумма цифр равна 40?

Первым делом напишем функцию, ко- торая считает сумму цифр заданного числа. Внимание, хитрый трюк! Воспользуемся

 

функцией show и преобразуем наше число в строку. Когда у нас будет строка из цифр, мы переведём каждый её символ в число и просум- мируем получившийся числовой список. Превращать символ в чис- ло будем с помощью функции digitToInt из модуля Data.Char. Она принимает значение типа Char и возвращает Int:

ghci> digitToInt '2'

ghci> digitToInt 'F' 15

ghci> digitToInt 'z'

*** Exception: Char.digitToInt: not a digit 'z'

Функция digitToInt работает с символами из диапазона от '0'

до '9' и от 'A' до 'F' (также и строчными).

Вот функция, принимающая число и возвращающая сумму его цифр:

import Data.Char import Data.List

 

digitSum:: Int -> Int

digitSum = sum. map digitToInt. show

Преобразуем заданное число в строку, пройдёмся по строке функцией digitToInt, суммируем получившийся числовой список. Теперь нужно найти первое натуральное число, применив к ко-

торому функцию digitSum мы получим в качестве результата число 40. Для это- го воспользуемся функцией find из мо- дуля Data.List. Она принимает предикат и список и возвращает первый элемент списка, удовлетворяющий предикату. Правда, тип у неё несколько необыч- ный:

ghci>:t find

find:: (a -> Bool) -> [a] -> Maybe a

Первый параметр – предикат, вто- рой – список, с этим всё ясно. Но что с возвращаемым значением? Что это за

 

Maybe a? Это тип, который нам до сих пор не встречался. Значение с типом Maybe a немного похоже на список типа [a]. Если список мо- жет иметь ноль, один или много элементов, то значение типа Maybe a может иметь либо ноль элементов, либо в точности один. Эту штуку можно использовать, если мы хотим предусмотреть возмож- ность провала. Значение, которое ничего не содержит, – Nothing. Оно аналогично пустому списку. Для конструирования значения, которое что-то содержит, скажем, строку "эй", будем писать Just "эй". Вот как всё это выглядит:

ghci> Nothing Nothing

ghci> Just "эй" Just "эй"

ghci> Just 3

Just 3

ghci>:t Just "эй"

Just "эй":: Maybe [Char] ghci>:t Just True

Just True:: Maybe Bool

Видите, значение Just True имеет тип Maybe Bool. Похоже на то, что список, содержащий значения типа Bool, имеет тип [Bool].

Если функция find находит элемент, удовлетворяющий преди- кату, она возвращает этот элемент, обёрнутый в Just. Если не нахо- дит, возвращает Nothing:

ghci> find (>4) [3,4,5,6,7]

Just 5

ghci> find odd [2,4,6,8,9]

Just 9

ghci> find (=='х') "меч-кладенец" Nothing

Вернёмся теперь к нашей задаче. Мы уже написали функцию digitSum и знаем, как она работает, так что пришла пора собрать всё вместе. Напомню, что мы хотим найти число, сумма цифр ко- торого равна 40.

firstTo40:: Maybe Int

firstTo40 = find (\x -> digitSum == 40) [1..]

 

Мы просто взяли бесконечный список [1..] и начали искать первое число, значение digitSum для которого равно 40.

ghci> firstTo40 Just 49999

А вот и ответ! Можно сделать более общую функцию, которой нужно передавать искомую сумму в качестве параметра:

firstTo:: Int -> Maybe Int

firstTo n = find (\x -> digitSum x == n) [1..]

И небольшая проверка:

ghci> firstTo 27

Just 999

ghci> firstTo 1

Just 1

ghci> firstTo 13

Just 49