ФВП, или Функции Высшего Порядка (англ. HOF, Higher Order Functions) — важная концепция в Haskell, с которой, однако, мы уже знакомы. Как мы узнали из предыдущих глав, функциями можно оперировать как значениями. Так вот функции, оперирующие другими функциями как аргументами и/или как результирующим выражением, носят название функций высшего порядка.
Так, оператор композиции функций является ФВП, потому что он, во-первых, принимает функции в качестве аргументов, а во-вторых, возвращает другую функцию (в виде ЛФ) как результат своего применения. Использование функций в качестве аргументов — чрезвычайно распространённая практика в Haskell.
Рассмотрим функцию map
. Эта стандартная функция используется для отображения (англ. mapping) функции на элементы списка. Пусть вас не смущает такой термин: отображение функции на элемент фактически означает её применение к этому элементу.
Вот объявление функции map
:
map :: (a -> b) -> [a] -> [b]
Вот опять эти маленькие буквы! Помните, я обещал рассказать о них? Рассказываю: малой буквой принято именовать полиморфный (англ. polymorphic) тип. Полиморфизм — это многообразность, многоформенность. В данном случае речь идёт не об указании конкретного типа, а о «типовой заглушке». Мы говорим: «Функция map
применяется к функции из какого-то типа a
в какой-то тип b
и к списку типа [a]
, а результат её работы — это другой список типа [b]
». Типовой заглушкой я назвал их потому, что на их место встают конкретные типы, что делает функцию map
очень гибкой. Например:
import Data.Char
toUpperCase :: String -> String
toUpperCase str = map toUpper str
main :: IO ()
main = putStrLn . toUpperCase $ "haskell.org"
Результатом работы этой программы будет строка:
HASKELL.ORG
Функция map
применяется к двум аргументам: к функции toUpper
и к строке str
. Функция toUpper
из стандартного модуля Data.Char
переводит символ типа Char
в верхний регистр:
toUpper 'a' = 'A'
Вот её объявление:
toUpper :: Char -> Char
Функция из Char
в Char
выступает первым аргументом функции map
, подставим сигнатуру:
map :: (a -> b) -> [a] -> [b]
(Char -> Char)
Ага, уже теплее! Мы сделали два новых открытия: во-первых, заглушки a
и b
могут быть заняты одним и тем же конкретным типом, а во-вторых, сигнатура позволяет нам тут же понять остальные типы. Подставим их:
map :: (a -> b) -> [a] -> [b]
(Char -> Char) [Char] [Char]
____ ____
____ ____
А теперь вспомним о природе типа String
:
map :: (a -> b) -> [a] -> [b]
(Char -> Char) String String
Всё встало на свои места. Функция map
в данном случае берёт функцию toUpper
и бежит по списку, последовательно применяя эту функцию к его элементам:
map toUpper ['h','a','s','k','e','l','l','.','o','r','g']
Так, на первом шаге функция toUpper
будет применена к элементу 'h'
, на втором — к элементу 'a'
, и так далее до последнего элемента 'g'
. Когда функция map
бежит по этому списку, результат применения функции toUpper
к его элементам служит элементами для второго списка, который и будет в конечном итоге возвращён. Так, результатом первого шага будет элемент 'H'
, результатом второго — элемент 'A'
, а результатом последнего — элемент 'G'
. Схема такова:
map toUpper [ 'h' >> [ 'H'
, 'a' >> , 'A'
, 's' >> , 'S'
, 'k' >> , 'K'
, 'e' >> , 'E'
, 'l' >> , 'L'
, 'l' >> , 'L'
, '.' >> , '.'
, 'o' >> , 'O'
, 'r' >> , 'R'
, 'g' >> , 'G'
] ]
Вот и получается:
map toUpper "haskell.org" = "HASKELL.ORG"
Работа функции map
выглядит как изменение списка, однако, в виду неизменности последнего, в действительности формируется новый список. Что самое интересное, функция toUpper
пребывает в полном неведении о том, что ею в конечном итоге изменяют регистр целой строки, она знает лишь об отдельных символах этой строки. То есть функция, являющаяся аргументом функции map
, ничего не знает о функции map
, и это очень хорошо! Чем меньше функции знают друг о друге, тем проще и надёжнее использовать их друг с другом.
Рассмотрим другой пример, когда типовые заглушки a
и b
замещаются разными типами:
toStr :: [Double] -> [String]
toStr numbers = map show numbers
main :: IO ()
main = print . toStr $ [1.2, 1,4, 1.6]
Функция toStr
работает уже со списками разных типов: на входе список чисел с плавающей точкой, на выходе список строк. При запуске этой программы мы увидим следующее:
["1.2","1.0","4.0","1.6"]
Уже знакомая нам стандартная функция show
переводит свой единственный аргумент в строковый вид:
show 1.2 = "1.2"
В данном случае, раз уж мы работаем с числами типа Double
, тип функции show
такой:
show :: Double -> String
Подставим в сигнатуру функции map
:
map :: (a -> b) -> [a] -> [b]
(Double -> String) [Double] [String]
______ ______
====== ======
Именно так, как у нас и есть:
map show [1.2, 1,4, 1.6] = ["1.2","1.0","4.0","1.6"]
Функция map
применяет функцию show
к числам из первого списка, на выходе получаем второй список, уже со строками. И как и в случае с toUpper
, функция show
ничего не подозревает о том, что ею оперировали в качестве аргумента функции map
.
Разумеется, в качестве аргумента функции map
мы можем использовать и наши собственные функции:
ten :: [Double] -> [Double]
ten = map (\n -> n * 10)
main :: IO ()
main = print . ten $ [1.2, 1,4, 1.6]
Результат работы:
[12.0,10.0,40.0,16.0]
Мы передали функции map
нашу собственную ЛФ, умножающую свой единственный аргумент на 10
. Обратите внимание, мы вновь использовали краткую форму определения функции ten
, опустив имя её аргумента. Раскроем подробнее:
main = print . ten $ [1.2, 1,4, 1.6] =
_____/ \_____
/ \
/ \
main = print . map (\n -> n * 10) $ [1.2, 1,4, 1.6]
Вы спросите, как же вышло, что оператор применения расположен между двумя аргументами функции map
? Разве он не предназначен для применения функции к единственному аргументу? Совершенно верно. Пришло время открыть ещё один секрет Haskell.
Функция map
ожидает два аргумента, это отражено в её типе. Но что будет, если применить её не к двум аргументам, а лишь к одному? В этом случае произойдёт ещё одно «магическое» превращение, называющееся частичным применением (англ. partial application) функции. Частичным называют такое применение, когда аргументов меньше чем ожидается.
Вспомним сокращённое определение функции ten
:
ten = map (\n -> n * 10)
первый а где же
аргумент второй??
есть
Функция map
получила лишь первый аргумент, а где же второй? Второй, как мы уже знаем, будет получен ею уже потом, после того, как мы подставим это выражение на место функции ten
. Но что же происходит с функцией map
до этого? А до этого с ней происходит частичное применение. Понятно, что она ещё не может выполнить свою работу, поэтому, будучи применённой лишь к одному аргументу, она возвращает ЛФ! Сопоставим с типом функции map
, и всё встанет на свои места:
map :: (a -> b) -> [a] -> [b]
map (\n -> n * 10)
только первый
аргумент
│ частично │
│ применённая │
└─────── map ───────┘
аргумент ответ
для частично
применённой
функции map
[1.2, 1,4, 1.6]
Тип ЛФ, возвращённой после применения map
к первому аргументу — [a] -> [b]
. Это «типовой хвост», оставшийся от полного типа функции map
:
map :: (a -> b) -> [a] -> [b]
голова └── хвост ─┘
Поскольку голова в виде первого аргумента типа (a -> b)
уже дана, осталось получить второй аргумент. Поэтому ЛФ, порождённая частичным применением, ожидает единственный аргумент, которым и будет тот самый второй, а именно список [1.2, 1,4, 1.6]
.
Сопоставим тип функции ten
с типом map
, чтобы понять, где наш хвост:
ten :: [Double] -> [Double]
map :: (a -> b) -> [a] -> [b]
голова └────── хвост ─────┘
Вот почему мы можем использовать краткую форму определения для функции ten
: она уже является нашим хвостом!
Рассмотрим ещё один пример частичного применения, дабы закрепить наше понимание:
replace :: String -> String -> String -> String
Это объявление функции replace
, принимающей три строки: первая содержит то, что ищем, вторая содержит то, на что заменяем, а в третьей лежит то, где ищем. Например:
replace "http"
"https"
"http://google.com" = "https://google.com"
Определение функции replace
нас сейчас не интересует, рассмотрим пошаговое применение:
main :: IO ()
main = putStrLn result
where
first = replace "http"
second = first "https"
result = second "http://google.com"
Тип выражения first
— String -> String -> String
, оно явилось результатом частичного применения функции replace
к первому аргументу, строке "http"
. Тип выражения second
— String -> String
, оно явилось результатом вторичного частичного применения функции first
к уже второму аргументу, строке "https"
. И наконец, применив функцию second
к третьему аргументу, строке "http://google.com"
, мы наконец-то получаем конечный результат, ассоциированный с выражением result
.
Из этого мы делаем интересное открытие:
Функция от нескольких аргументов может быть разложена на последовательность применений временных функций от одного аргумента каждая.
Поэтому мы и смогли подставить частично применённую map
на место выражения ten
. Используем круглые скобки, дабы яснее показать, что есть что:
main = print . (map (\n -> n * 10)) $ [1.2, 1,4, 1.6]
│ частично │
└─ применённая map ┘
│ композиция функции │
│ print и частично │
└───── применённой map ────┘
аргумент для
композиции
Гибко, не правда ли? Теперь мы знакомы с частичным применением функции.
Вернёмся к функции map
. Если мы можем передать ей некую функцию для работы с элементами списка, значит мы можем передать ей и композицию двух или более функций. Например:
import Data.Char
pretty :: [String] -> [String]
pretty = map (stars . big)
where
big = map toUpper
stars = \s -> "* " ++ s ++ " *"
main :: IO ()
main = print . pretty $ ["haskell", "lisp", "coq"]
Мы хотим украсить имена трёх языков программирования. Для этого мы пробегаемся по списку композицией двух функций, big
и stars
. Функция big
переводит строки в верхний регистр, а функция stars
украшает имя двумя звёздочками в начале и в конце. В результате имеем:
["* HASKELL *","* LISP *","* COQ *"]
Пройтись по списку композицией stars . big
равносильно тому, как если бы мы прошлись сначала функцией big
, а затем функцией stars
. При этом, как мы уже знаем, обе эти функции ничего не знают ни о том, что их скомпоновали, ни о том, что эту композицию передали функции map
.
Ну что ж, теперь мы знаем о функции map
, и последующих главах мы увидим множество других ФВП. Отныне они будут нашими постоянными спутниками.