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

Вы прогуливаетесь по улице, и тут к вам подходит старушка и спрашивает: «Простите, а каково первое натуральное число, сумма цифр которого равна 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

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