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

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

Лямбда-выражения – это анонимные функции, которые используются, если некоторая функция нужна нам только однажды. Как правило, мы создаём анонимные функции с единственной целью: передать их функции высшего порядка в качестве параметра. Чтобы записать лямбда-выражение, пишем символ \(напоминающий, если хорошенько напрячь воображение, греческую букву лямбда – λ), затем записываем параметры, разделяя их пробелами. Далее пишем знак –>и тело функции. Обычно мы заключаем лямбду в круглые скобки, иначе она продолжится до конца строки вправо.

Если вы обратитесь к примеру, приведённому в предыдущем разделе, то увидите, что мы создали функцию isLongв секции whereфункции numLongChainsтолько для того, чтобы передать её в фильтр. Вместо этого можно использовать анонимную функцию:

numLongChains :: Int

numLongChains = length (filter (\xs –> length xs > 15) (map chain [1..100]))

Анонимные функции являются выражениями, поэтому мы можем использовать их таким способом, как в примере. Выражение (\xs –> length xs > 15)возвращает функцию, которая говорит нам, больше ли 15длина переданного списка.

Те, кто не очень хорошо понимает, как работает каррирование и частичное применение функций, часто используют анонимные функции там, где не следует. Например, выражения map (+3) [1,6,3,2]и map (\x –> x + 3) [1,6,3,2]эквивалентны, так как (+3)и (\x –> x + 3)– это функции, которые добавляют тройку к аргументу. Излишне говорить, что использование анонимной функции в этом случае неоправданно, так как частичное применение значительно легче читается.

Как и обычные функции, лямбда-выражения могут принимать произвольное количество параметров:

ghci> zipWith (\a b –> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5]

[153.0,61.5,31.0,15.75,6.6]

По аналогии с обычными функциями, можно выполнять сопоставление с образцом в лямбда-выражениях. Единственное отличие в том, что нельзя определить несколько образцов для одного параметра – например, записать для одного параметра образцы []и (x: xs)и рассчитывать, что выполнение перейдёт к образцу (x:xs)в случае неудачи с []. Если сопоставление с образцом в анонимной функции заканчивается неудачей, происходит ошибка времени выполнения, так что поосторожнее с этим!