Стандартные функции высших порядков

В стандартный набор библиотек входит много достаточно общих функций высших порядков. Я их приведу сейчас вместе с определениями, но самое главное в этих функциях, конечно – это не их код: он тривиален. Самое главное – идея достаточно общего поведения, которое кто-то заметил и оформил в функцию высших порядков:

takeWhile :: (a -> Bool) -> [a] -> [a]

takeWhile p [] = []

takeWhile p (x:xs)

| p x = x : takeWhile p xs

| otherwise = []

dropWhile :: (a -> Bool) -> [a] -> [a]

dropWhile p [] = []

dropWhile p (x:xs)

| p x = dropWhile p xs

| otherwise = (x:xs)

Обычные функции take и drop брали или, соответственно, выбрасывали из списка заданное количество элементов, а функция filter берет или выбрасывает элементы из списка по какому-то условию, применяемому ко всем элементам поочередно. Функции takeWhile и dropWhile проверяют условие и берут или выкидывают элементы только до первого случая, когда условие не срабатывает.

takeWhile (not.wtspc) "They are coming. They are here" → "They are coming" where

wtspc = `elem` ".,!?"

Или вот еще:

any, all :: (a -> Bool) -> [a] -> Bool

any p = or . map p

all p = and . map p

Надеюсь, для вас уже не составляет труда расшифровать любое из этих определений как:

any p xs = or (map p xs)

all p xs = and (map p xs)

Эти две функции проверяют, выполняется ли определенное условие хотя бы на одном (или, соответственно, на всех) элементе списка:

all (>0) [1,2,3,-5] → False

all (>0) [1,2,3] → True

Обратите внимание, у нас уже одни функции высших порядков (any, all) выражаются через другие (map), и так и должно быть! Всегда, когда вам нужно реализовать какую-то функциональность, постарайтесь увидеть, как эта функциональность реализуется через уже известные вам функции высших порядков, и только потом уже пишите реализацию свою.

($) :: (a -> b) -> a -> b

($) f x = f x

Функция ($), как мы видим, это просто применение функции. Отличается она от обычного применения только приоритетом. Выражение sin x + 1 будет означать (sin x) + 1, а выражение sin $ x + 1 будет вычисляться как sin (x + 1). Таким образом, пробел можно условно рассматривать как бинарный оператор применения функции к аргументу, имеющий наивысший приоритет; тогда как функция ($) имеет, наоборот, наименьший.

zipWith :: (a->b->c) -> [a]->[b]->[c]

zipWith z (a:as) (b:bs) = z a b : zipWith z as bs

zipWith _ _ _ = []

Очень полезная функция zipWith позволяет "слить" вместе два списка, применяя к элементам, стоящим на соответствующих местах, заданную функцию. Например, даже обычная функция zip на самом деле может быть реализована с помощью zipWith (\x y -> (x,y)), а кроме этого:

zipWith (+) [1,1,2,3,5,8] [1,2,3,5,8,13] →

[2,3,5,8,13,21]

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Ой, мы случайно написали функцию, находящую бесконечный список чисел Фибоначчи. Да, с Haskell такое бывает…

curry :: ((a,b) -> c) -> (a -> b -> c)

curry f x y = f (x,y)

uncurry :: (a -> b -> c) -> ((a,b) -> c)

uncurry f p = f (fst p) (snd p)

Помните, мы давным-давно говорили о том, что все функции в Haskell принимают ровно один параметр? Помните про каррированные и некаррированные функции? Вот эти две функции позволяют преобразовывать каррированную функцию (принимающую параметры по одному) в некаррированную (принимающую все параметры разом, в виде кортежа) – и наоборот.

span, break :: (a -> Bool) -> [a] -> ([a],[a])

span p [] = ([],[])

span p (x:xs)

| p x = (x:ys, zs)

| otherwise = ([], x:xs)

where (ys,zs) = span p xs

break p = span (not . p)

Функции span и break выполняют сразу работу и takeWhile и dropWhile вместе взятых. Они принимают условие p и список xs, разделяют xs на две части: в первую часть попадает значение takeWhile p xs, а во вторую – dropWhile p xs.

Во второй части этого материала, в задачнике, в главе про списочные функции высших порядков приведены примеры других функций, реально имеющихся в стандартной поставке, и потенциально возможных для реализации. Очень рекомендую со всеми ними ознакомиться, потому что не будет особым преувеличением сказать, что сила функционального программирования заключается именно в широком применении функций высших порядков, совместно с быстрой и удобной подготовкой рабочих функций для них с помощью частичного применения и лямбда-функций.