Изучай Haskell во имя добра! (Липовача) - страница 53

Теперь мы собираемся найти сумму всех нечётных квадратов меньших 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

>[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]

Так! Вроде бы работает правильно. Ну а теперь функция, которая ответит на наш вопрос: