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

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'

2

ghci> digitToInt 'F'

15

ghci> digitToInt 'z'

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

Функция digitToInt работает с символами из диапазона от '0' до '9' и от 'A' до 'F' (также и строчными).