Итак, в первую очередь начнём применять функцию (^2) к бесконечному списку [1..]. Затем отфильтруем список, чтобы в нём были только нечётные элементы. Далее возьмём из него значения, меньшие 10000. И, наконец, получим сумму элементов этого списка. Нам даже не нужно задавать для этого функцию – достаточно будет одной строки в GHCi:
ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
166650
Потрясающе! Мы начали с некоторых начальных данных (бесконечный список натуральных чисел) и затем применяли к ним функцию, фильтровали, прореживали до тех пор, пока список не удовлетворил нашим запросам, а затем просуммировали его. Можно было бы воспользоваться генераторами списков для той же цели:
ghci> sum (takeWhile (<10000) [m | m <– [n^2 | n <– [1..]], odd m])
166650
В следующей задаче мы будем иметь дело с рядами Коллатца. Берём натуральное число. Если это число чётное, делим его на два. Если нечётное – умножаем его на 3 и прибавляем единицу. Берём получившееся значение и снова повторяем всю процедуру, получаем новое число, и т. д. В сущности, у нас получается цепочка чисел. С какого бы значения мы ни начали, цепочка заканчивается на единице. Если бы начальным значением было 13, мы бы получили такую последовательность: 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Всё по вышеприведённой схеме: 13 × 3 + 1 равняется 40; 40, разделённое на 2, равно 20, и т. д. Как мы видим, цепочка имеет 10 элементов.
Теперь требуется выяснить: если взять все стартовые числа от 1 до 100, как много цепочек имеют длину больше 15? Для начала напишем функцию, которая создаёт цепочку:
chain :: Integer -> [Integer]
chain 1 = [1]
chain n
| even n = n:chain (n `div` 2)
| odd n = n:chain (n*3 + 1)
Так как цепочка заканчивается на единице, это базовый случай. Получилась довольно-таки стандартная рекурсивная функция.
ghci> chain 10
[10,5,16,8,4,2,1]
ghci> chain 1
[1]
ghci> chain 30
[30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
Так! Вроде бы работает правильно. Ну а теперь функция, которая ответит на наш вопрос:
numLongChains :: Int
numLongChains = length (filter isLong (map chain [1..100]))
where isLong xs = length xs > 15
Мы применяем функцию chain к списку [1..100], чтобы получить список цепочек; цепочки также являются списками. Затем фильтруем их с помощью предиката, который проверяет длину цепочки. После фильтрации смотрим, как много цепочек осталось в результирующем списке.
ПРИМЕЧАНИЕ. Эта функция имеет тип numLongChains :: Int, потому что length возвращает значение типа Int вместо экземпляра класса Num – так уж сложилось исторически. Если мы хотим вернуть более общий тип, имеющий экземпляр класса Num, нам надо применить функцию fromIntegral к результату, возвращённому функцией length.
Функция map для функций нескольких переменных
Используя функцию map, можно проделывать, например, такие штуки: map (*) [0..] – если не для какой-либо практической цели, то хотя бы для того, чтобы продемонстрировать, как работает каррирование, и показать, что функции (частично применённые) – это настоящие значения, которые можно передавать в другие функции или помещать в списки (но нельзя представлять в виде строк). До сих пор мы применяли к спискам только функции с одним параметром, вроде map (*2) [0..], чтобы получить список типа (Num a) => [a], но с тем же успехом можем использовать (*) [0..] безо всяких проблем. При этом числа в списке будут применены к функции *, тип которой (Num a) => a –> a –> a. Применение только одного параметра к функции двух параметров возвращает функцию одного параметра. Применив оператор * к списку [0..], мы получаем список функций, которые принимают только один параметр, а именно (Num a) => [a –> a]. Список, возвращаемый выражением map (*) [0..], также можно получить, записав [(0*),(1*),(2*),(3*),(4*),(5*)…
ghci> let listOfFuns = map (*) [0..]
ghci> (listOfFuns !! 4) 5
20
Элемент с номером четыре из списка содержит функцию, которая выполняет умножение на четыре – (4*). Затем мы применяем значение 5 к этой функции. Это то же самое, что записать (4*) 5 или просто 4 * 5.
Лямбда-выражения
Лямбда-выражения – это анонимные функции, которые используются, если некоторая функция нужна нам только однажды. Как правило, мы создаём анонимные функции с единственной целью: передать их функции высшего порядка в качестве параметра. Чтобы записать лямбда-выражение, пишем символ \ (напоминающий, если хорошенько напрячь воображение, греческую букву лямбда – λ), затем записываем параметры, разделяя их пробелами. Далее пишем знак –> и тело функции. Обычно мы заключаем лямбду в круглые скобки, иначе она продолжится до конца строки вправо.