ФВП

ФВП, или Функции Высшего Порядка (англ. 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, и последующих главах мы увидим множество других ФВП. Отныне они будут нашими постоянными спутниками.