Поищем числа

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

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

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

ghci> digitToInt '2'

ghci> digitToInt 'F'

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