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

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

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'

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 (=='x') "меч-кладенец"

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

Отображение ключей на значения

Зачастую, работая с данными из некоторого набора, мы совершенно не заботимся, в каком порядке они расположены. Мы просто хотим получить к ним доступ по некоторому ключу. Например, желая узнать, кто живёт по известному адресу, мы ищем имена тех, кто по этому адресу проживает. В общем случае мы говорим, что ищем значение (чьё-либо имя) по ключу (адрес этого человека).

Почти хорошо: ассоциативные списки

Существует много способов построить отображение «ключ–значение». Один из них – ассоциативные списки. Ассоциативные списки (также называемые словарями или отображениями) – это списки, которые хранят неупорядоченные пары «ключ–значение». Например, мы можем применять ассоциативные списки для хранения телефонных номеров, используя телефонный номер как значение и имя человека как ключ. Нам неважно, в каком порядке они сохранены: всё, что нам требуется, – получить телефонный номер по имени. Наиболее простой способ представить ассоциативный список в языке Haskell – использовать список пар. Первый компонент пары будет ключом, второй – значением. Вот пример ассоциативного списка с номерами телефонов:

phoneBook =

  [("оля","555–29-38")

  ,("женя","452–29-28")

  ,("катя","493–29-28")

  ,("маша","205–29-28")

  ,("надя","939–82-82")

  ,("юля","853–24-92")

  ]

За исключением странного выравнивания, это просто список, состоящий из пар строк. Самая частая задача при использовании ассоциативных списков – поиск некоторого значения по ключу. Давайте напишем функцию для этой задачи.

findKey :: (Eq k) => k –> [(k,v)] –> v

findKey key xs = snd . head $ filter ((k,v) –> key == k) xs

Всё довольно просто. Функция принимает ключ и список, фильтрует список так, что остаются только совпадающие ключи, получает первую пару «ключ–значение», возвращает значение. Но что произойдёт, если искомого ключа нет в списке? В этом случае мы будем пытаться получить «голову» пустого списка, что вызовет ошибку времени выполнения. Однако следует стремиться к тому, чтобы наши программы были более устойчивыми к «падениям», поэтому давайте используем тип Maybe. Если мы не найдём ключа, то вернём значение Nothing. Если найдём, будем возвращать Just <то, что нашли>.