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

ghci> filter (<15) (filter even [1..20])

[2,4,6,8,10,12,14]

Здесь мы берём список [1..20]и фильтруем его так, чтобы остались только чётные числа. Затем список передаётся функции filter (<15), которая избавляет нас от чисел 15и больше. Вот версия с генератором списка:

ghci> [ x | x <- [1..20], x < 15, even x]

[2,4,6,8,10,12,14]

Мы используем генератор для извлечения элементов из списка [1..20], а затем указываем условия, которым должны удовлетворять элементы результирующего списка.

Помните нашу функцию быстрой сортировки (см. предыдущую главу, раздел «Сортируем, быстро!»)? Мы использовали генераторы списков для фильтрации элементов меньших (или равных) и больших, чем опорный элемент. Той же функциональности можно добиться и более понятным способом, используя функцию filter:

quicksort :: (Ord a) => [a] –> [a]

quicksort [] = []

quicksort (x:xs) =

let smallerSorted = quicksort (filter (<= x) xs)

biggerSorted = quicksort (filter (> x) xs)

in smallerSorted ++ [x] ++ biggerSorted

Давайте найдём наибольшее число меньше 100 000, которое делится на число 3829 без остатка. Для этого отфильтруем множество возможных вариантов, в которых, как мы знаем, есть решение.

largestDivisible :: Integer

largestDivisible = head (filter p [100000,99999..])

where p x = x `mod` 3829 == 0

Для начала мы создали список всех чисел меньших 100 000 в порядке убывания. Затем отфильтровали список с помощью предиката. Поскольку числа отсортированы в убывающем порядке, наибольшее из них, удовлетворяющее предикату, будет первым элементом отфильтрованного списка. Нам даже не нужно использовать конечный список для нашего базового множества. Снова «лень в действии»! Поскольку мы используем только «голову» списка, нам неважно, конечен полученный список или бесконечен. Вычисления прекращаются, как только находится первое подходящее решение.

Теперь мы собираемся найти сумму всех нечётных квадратов меньших 10 000. Но для начала познакомимся с функцией takeWhile: она пригодится в нашем решении. Она принимает предикат и список, а затем начинает обход списка с его «головы», возвращая те его элементы, которые удовлетворяют предикату. Как только найден элемент, не удовлетворяющий предикату, обход останавливается. Если бы мы хотели получить первое слово строки "слоны умеют веселиться", мы могли бы сделать такой вызов: takeWhile (/=' ') "слоны умеют веселиться", и функция вернула бы "слоны".

Итак, в первую очередь начнём применять функцию (^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