# Глава 14. Функции высшего порядка ФВП, или Функции Высшего Порядка (англ. HOF, Higher Order Functions) — важная концепция в Haskell, с которой, однако, мы уже знакомы. Как мы узнали из предыдущих глав, функциями можно оперировать как значениями. Так вот функции, оперирующие другими функциями как аргументами и/или как результирующим выражением, носят название функций высшего порядка. Так, оператор композиции функций `.` является ФВП, потому что он, во-первых, принимает функции в качестве аргументов, а во-вторых, возвращает другую функцию (в виде ЛФ) как результат своего применения. Использование функций в качестве аргументов — чрезвычайно распространённая практика в Haskell. ## Отображение Рассмотрим функцию `map`. Эта стандартная функция используется для отображения (англ. mapping) функции на элементы списка. Пусть вас не смущает такой термин: отображение функции на элемент фактически означает её применение к этому элементу. {#block-map} Вот объявление функции `map`: {#block-polymorphic-types} ```haskell map :: (a -> b) -> [a] -> [b] ``` Вот опять эти маленькие буквы! Помните, я [обещал](/courses/haskell/chapters/haskell_chapter_0120#block-mul-declaration) рассказать о них? Рассказываю: малой буквой принято именовать полиморфный (англ. polymorphic) тип. Полиморфизм — это многообразность, многоформенность. В данном случае речь идёт не об указании конкретного типа, а о «типовой заглушке». Мы говорим: функция `map` применяется к функции из какого-то типа `a` в какой-то тип `b` и к списку типа `[a]`, а результат её работы — это другой список типа `[b]`. Типовой заглушкой я назвал их потому, что на их место встают конкретные типы, что делает функцию `map` очень гибкой. Например: {#block-data-char} ```haskell {.example_for_playground} 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` в верхний регистр: ```haskell toUpper 'a' = 'A' ``` Вот её объявление: ```haskell toUpper :: Char -> Char ``` Функция из `Char` в `Char` выступает первым аргументом функции `map`, подставим сигнатуру: ``` map :: (a -> b) -> [a] -> [b] (Char -> Char) ``` Ага, уже теплее! Мы сделали два новых открытия: во-первых, заглушки `a` и `b` могут быть заняты одним и тем же конкретным типом, а во-вторых, сигнатура позволяет нам тут же понять остальные типы. Подставим их: ``` map :: (a -> b) -> [a] -> [b] (Char -> Char) [Char] [Char] ``` А теперь [вспомним](/courses/haskell/chapters/haskell_chapter_0090#block-string) о природе типа `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'`. Схема такова: ``` 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`, и это очень хорошо! Чем меньше функции знают друг о друге, тем проще и надёжнее использовать их друг с другом. Напишите функцию `toStr`, которая превращает список чисел с плавающей точкой в список строк. {.task_text} В теле функции `main` используйте операторы композиции и применения для вывода в консоль результата применения `toStr` к списку `[1.2, 1.4, 1.6]`. {.task_text} ```haskell {.task_source #haskell_chapter_0140_task_0010} module Main where -- Your code here main :: IO () main = -- And here ``` Стандартная функция `show` переводит свой единственный аргумент в строковый вид. В теле `toStr` примените `map` к функции `show` и списку чисел. {.task_hint} ```haskell {.task_answer} module Main where toStr :: [Double] -> [String] toStr numbers = map show numbers main :: IO () main = print . toStr $ [1.2, 1.4, 1.6] ``` Касательно этой задачи. Мы воспользовались функцией `show`. И раз уж мы работаем с числами типа `Double`, тип функции `show` такой: ```haskell show :: Double -> String ``` Подставим в сигнатуру функции `map`: ``` 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 {.example_for_playground} 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`: она уже является нашим хвостом! Что выведет этот код? В случае ошибки напишите `error`. {.task_text} ```haskell {.example_for_playground} module Main where f :: Int -> Int -> Int -> Int f x y z = x * y * z main :: IO () main = let g = f 2 in print $ g 3 4 ``` ```consoleoutput {.task_source #haskell_chapter_0140_task_0020} ``` Функция `f` принимает 3 числа и возвращает их произведение. Выражение `g` — это частичное применение `f` к 2. Применение `g` к 3 и 4 раскрывается как произведение 2, 3 и 4. {.task_hint} ```haskell {.task_answer} 24 ``` Рассмотрим ещё один пример частичного применения, дабы закрепить наше понимание: ```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`. Используем круглые скобки, дабы яснее показать, что есть что: ``` main = print . (map (\n -> n * 10)) $ [1.2, 1,4, 1.6] │ частично │ └─ применённая map ┘ │ композиция функции │ │ print и частично │ └───── применённой map ────┘ аргумент для композиции ``` Гибко, не правда ли? Теперь мы знакомы с частичным применением функции. Напишите функцию `mult`, которая принимает два аргумента: {.task_text} - функцию из целого в целое (назовем ее `f`); - целое число (пусть будет `x`). {.task_text} Функция `mult` должна возвращать перемножение двух результатов функции `f` от `x`. {.task_text} В функции `main` в секции `let` заведите ЛФ, принимающую аргумент и умножающую его на 10. Также в `let` заведите частичное применение `mult` к ЛФ и назовите его `g`. {.task_text} ```haskell {.task_source #haskell_chapter_0140_task_0030} module Main where -- Your code here main :: IO () main = let -- And here in print . g $ 5 ``` Объявление функции `mult`: `mult :: (Int -> Int) -> Int -> Int`. {.task_hint} ```haskell {.task_answer} module Main where mult :: (Int -> Int) -> Int -> Int mult f x = f x * f x main :: IO () main = let ten = \x -> x * 10 g = mult ten in print . g $ 5 ``` ## Композиция для отображения Вернёмся к функции `map`. Если мы можем передать ей некую функцию для работы с элементами списка, значит мы можем передать ей и композицию двух или более функций. Например: ```haskell {.example_for_playground} 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`, и последующих главах мы увидим множество других ФВП. Отныне они будут нашими постоянными спутниками. ## Функция filter Мы выяснили, что функция `map f lst` используется для применения функции `f` к каждому элементу списка `lst`. Вторая функция высшего порядка, которая крайне полезна при работе со списками — это функция `filter`: ```haskell filter f lst ``` Она принимает два аргумента: предикат `f` (предикат — это функция, возвращающая `True` либо `False`) и список `lst`. Функция `filter` применяет предикат `f` к каждому элементу списка `lst`. И возвращает новый список, сформированный из элементов, удовлетворяющих предикату. В этом примере в качестве предиката выступает встроенная функция `odd`, которая возвращает `True` для нечетных чисел: ```haskell main :: IO () main = print $ filter odd [1, 4, 17, 46, 100] ``` ``` [1,17] ``` А здесь мы передали в `filter` свою собственную функцию: ```haskell {.example_for_playground} isLongLine :: String -> Bool isLongLine line = length line > 3 main :: IO () main = print $ filter isLongLine ["coq", "idris", "ml", "scala"] ``` ``` ["idris","scala"] ``` В качестве предиката подойдет и ЛФ. Перепишем предыдущий пример: ```haskell {.example_for_playground} main :: IO () main = print $ filter (\line -> length line > 3) ["coq", "idris", "ml", "scala"] ``` ``` ["idris","scala"] ``` Допустимо даже использование операторов: ```haskell {.example_for_playground} main :: IO () main = print $ filter (>128) [3, 55, 129, 4, 200] ``` ``` [129,200] ``` Очень часто функции `filter` и `map` объединяются в цепочки! {.task_text} Напишите функцию `findEmails`, которая принимает список строк. Она приводит к нижнему регистру и возвращает те строки, в которых содержится символ `@`. {.task_text} Для приведения символа к нижнему регистру воспользуйтесь функцией `toLower` из модуля `Data.Char`. {.task_text} ```haskell {.task_source #haskell_chapter_0140_task_0040} module Main where -- Your code here main :: IO () main = do print $ findEmails ["x", "x@mail.com", "haskell", "HaskEll@lst.org"] print $ findEmails ["mail", "MAIL@team.ru"] ``` Импортируйте модуль `Data.Char`. Напишите вспомогательную функцию для приведения всей строки к нижнему регистру. В функции `findEmails` напишите композицию функций `filter` и `map`: сначала `filter` проверяет, входит ли в строку символ `@`. Эту проверку можно сделать с помощью функции `elem`, [описанной](/courses/haskell/chapters/haskell_chapter_0090#block-useful-functions) в главе про списки. Результат работы `filter` передается в функцию `map`, которая применяет к каждой подходящей строке приведение к нижнему регистру. {.task_hint} ```haskell {.task_answer} module Main where import Data.Char toLowerCase :: String -> String toLowerCase str = map toLower str findEmails :: [String] -> [String] findEmails lst = map toLowerCase $ filter (\s -> elem '@' s) lst main :: IO () main = do print $ findEmails ["x", "x@mail.com", "haskell", "HaskEll@lst.org"] print $ findEmails ["mail", "MAIL@team.ru"] ```