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