Лямбда-функция

Пришло время познакомиться с важной концепцией — лямбда-функцией. Именно с неё всё и началось. Приготовьтесь: в этой главе нас ждут новые открытия.

Истоки

В далёких 1930-х молодой американский математик Алонзо Чёрч задался вопросом о том, что значит «вычислить» что-либо. Плодом его размышлений явилась система для формализации понятия «вычисление», и назвал он эту систему «лямбда-исчислением» (англ. lambda calculus, по имени греческой буквы λ). В основе этой системы лежит лямбда-функция, которую в некотором смысле можно считать «матерью функционального программирования» в целом и Haskell в частности. Далее буду называть её ЛФ.

В отношении ЛФ можно смело сказать: «Всё гениальное просто». Идея ЛФ столь полезна именно потому, что она предельно проста. ЛФ — это анонимная функция. Вот как она выглядит в Haskell:

\x -> x * x

Обратный слэш в начале — признак ЛФ. Сравните с математической формой записи:

λx . x * x

Похоже, не правда ли? Воспринимайте обратный слэш в определении ЛФ как спинку буквы λ.

ЛФ представляет собой простейший вид функции, эдакая функция, раздетая догола. У неё забрали не только объявление, но и имя, оставив лишь необходимый минимум в виде имён аргументов и внутреннего выражения. Алонзо Чёрч понял: чтобы применить функцию, вовсе необязательно её именовать. И если у обычной функции сначала идёт объявление/определение, а затем (где-то) применение с использованием имени, то у ЛФ всё куда проще: мы её определяем и тут же применяем, на месте. Вот так:

(\x -> x * x) 5

Помните функцию square? Вот это её лямбда-аналог:

(\x -> x * x)      5

лямбда-абстракция  аргумент

Лямбда-абстракция (англ. lambda abstraction) — это особое выражение, порождающее функцию, которую мы сразу же применяем к аргументу 5. ЛФ с одним аргументом, как и простую функцию, называют ещё «ЛФ от одного аргумента» или «ЛФ одного аргумента». Также можно сказать и о «лямбда-абстракции от одного аргумента».

Строение

Строение лямбда-абстракции предельно простое:

\        x          ->  x * x
признак  имя            выражение
ЛФ       аргумента

Соответственно, если ЛФ применяется к двум аргументам — пишем так:

\        x          y          ->  x * y
признак  имя 1      имя 2          выражение
ЛФ       аргумента  аргумента

И когда мы применяем такую функцию:

(\x y -> x * y) 10 4

то просто подставляем 10 на место x, а 4 — на место y, и получаем выражение 10 * 4:

  (\x y -> x * y) 10 4
= 10 * 4
= 40

В общем, всё как с обычной функцией, даже проще.

Мы можем ввести промежуточное значение для лямбда-абстракции:

main :: IO ()
main = print (mul 10 4)
  where mul = \x y -> x * y

Теперь мы можем применять mul так же, как если бы это была сама лямбда-абстракция:

  mul 10 4
= (\x y -> x * y) 10 4
= 10 * 4

И здесь мы приблизились к одному важному открытию.

Тип функции

Мы знаем, что у всех данных в Haskell-программе обязательно есть какой-то тип, внимательно проверяемый на этапе компиляции. Вопрос: какой тип у выражения mul из предыдущего примера?

  where mul = \x y -> x * y  -- Какой тип?

Ответ прост: тип mul такой же, как и у этой лямбда-абстракции. Из этого мы делаем важный вывод: ЛФ имеет тип, как и обычные данные. Но поскольку ЛФ является частным случаем функции — значит и у обыкновенной функции тоже есть тип!

В нефункциональных языках между функциями и данными проведена чёткая граница: вот это функции, а вон то — данные. Однако в Haskell между данными и функциями разницы нет, ведь и то и другое покоится на одной и той же Черепахе. Вот тип функции mul:

mul :: a -> a -> a

Погодите, скажете вы, но ведь это же объявление функции! Совершенно верно: объявление функции — это и есть указание её типа. Помните, когда мы впервые познакомились с функцией, я уточнил, что её объявление разделено двойным двоеточием? Так вот это двойное двоеточие и представляет собой указание типа:

mul  ::     a -> a -> a

вот  имеет  │   вот   │
это  тип    └─ такой ─┘

Точно так же мы можем указать тип любых других данных:

let coeff = 12 :: Double

Хотя мы знаем, что в Haskell типы выводятся автоматически, иногда мы хотим взять эту заботу на себя. В данном случае мы явно говорим: «Пусть выражение coeff будет равно 12, но тип его пусть будет Double, а не Int». Так же и с функцией: когда мы объявляем её — мы тем самым указываем её тип.

Но вы спросите, можем ли мы не указывать тип функции явно? Можем:

square x = x * x

Это наша старая знакомая, функция square. Когда она будет применена к значению типа Int, тип аргумента будет выведен автоматически как Int.

И раз функция характеризуется типом так же, как и прочие данные, мы делаем ещё одно важное открытие: функциями можно оперировать как данными. Например, можно создать список функций:

main :: IO ()
main = putStrLn ((head functions) "Hi")
  where
    functions = [ \x -> x ++ " val1"
                , \x -> x ++ " val2"
                ]

Выражение functions — это список из двух функций. Два лямбда-выражения порождают эти две функции, но до момента применения они ничего не делают, они безжизненны и бесполезны. Но когда мы применяем функцию head к этому списку, мы получаем первый элемент списка, то есть первую функцию. И получив, тут же применяем эту функцию к строке "Hi":

putStrLn ((head functions)  "Hi")

          │    первая    │  её
          │   функция    │  аргумент
          └─ из списка ──┘

Это равносильно коду:

putStrLn ((\x -> x ++ " val1") "Hi")

При запуске программы мы получим:

Hi val1

Кстати, а каков тип списка functions? Его тип таков: [String -> String]. То есть список функций с одним аргументом типа String, возвращающих значение типа String.

Локальные функции

Раз уж между ЛФ и простыми функциями фактически нет различий, а функции есть частный случай данных, мы можем создавать функции локально для других функций:

-- Здесь определены функции
-- isInfixOf и isSuffixOf.
import Data.List

validComEmail :: String -> Bool
validComEmail email =
    containsAtSign email && endsWithCom email
  where
    containsAtSign e = "@" `isInfixOf` e
    endsWithCom e = ".com" `isSuffixOf` e

main :: IO ()
main = putStrLn (if validComEmail my
                   then "It's ok!"
                   else "Non-com email!")
  where
    my = "[email protected]"

Несколько наивная функция validComEmail проверяет .com-адрес. Её выражение образовано оператором && и двумя выражениями типа Bool. Вот как образованы эти выражения:

containsAtSign e = "@" `isInfixOf` e
endsWithCom e = ".com" `isSuffixOf` e

Это — две функции, которые мы определили прямо в where-секции, поэтому они существуют только для основного выражения функции validComEmail. С простыми функциями так поступают очень часто: где она нужна, там её и определяют. Мы могли бы написать и более явно:

validComEmail :: String -> Bool
validComEmail email =
    containsAtSign email && endsWithCom email
  where
    -- Объявляем локальную функцию явно.
    containsAtSign :: String -> Bool
    containsAtSign e = "@" `isInfixOf` e

    -- И эту тоже.
    endsWithCom :: String -> Bool
    endsWithCom e = ".com" `isSuffixOf` e

Впрочем, указывать тип столь простых функций, как правило, необязательно.

Вот как этот код выглядит с лямбда-абстракциями:

validComEmail :: String -> Bool
validComEmail email =
    containsAtSign email && endsWithCom email
  where
    containsAtSign = \e -> "@" `isInfixOf` e
    endsWithCom = \e -> ".com" `isSuffixOf` e

Теперь выражения containsAtSign и endsWithCom приравнены к ЛФ от одного аргумента. В этом случае мы не указываем тип этих выражений. Впрочем, если очень хочется, можно и указать:

containsAtSign =
    (\e -> "@" `isInfixOf` e) :: String -> Bool

    лямбда-абстракция            тип этой абстракции

Лямбда-абстракция взята в скобки, чтобы указание типа относилось к функции в целом, а не только к аргументу e:

containsAtSign =
    \e -> "@" `isInfixOf` e :: String -> Bool

                               в этом случае это
                               тип аргумента e,
                               а вовсе не всей
                               функции!

Для типа функции тоже можно ввести псевдоним:

-- Псевдоним для типа функции.
type Func = String -> Bool

validComEmail :: String -> Bool
validComEmail email =
    containsAtSign email && endsWithCom email
  where
    containsAtSign = (\e -> "@" `isInfixOf` e) :: Func
    endsWithCom = (\e -> ".com" `isSuffixOf` e) :: Func

Впрочем, на практике указание типа для лямбда-абстракций встречается исключительно редко, ибо незачем.

Отныне, познакомившись с ЛФ, мы будем использовать их периодически.

И напоследок, вопрос. Помните тип функции mul?

mul :: a -> a -> a

Что это за буква a? Во-первых, мы не встречали такой тип ранее, а во-вторых, разве имя типа в Haskell не обязано начинаться с большой буквы? Обязано. А всё дело в том, что буква a в данном случае — это не совсем имя типа. А вот что это такое, мы узнаем в одной из ближайших глав.

Для любопытных

А почему, собственно, лямбда? Почему Чёрч выбрал именно эту греческую букву? По одной из версий, произошло это чисто случайно.

Шли 30-е годы прошлого века, компьютеров не было, и все научные работы набирались на печатных машинках. В первоначальном варианте, дабы выделять имя аргумента ЛФ, Чёрч ставил над именем аргумента символ, похожий на ^. Но когда он сдавал работу наборщику, то вспомнил, что печатная машинка не сможет воспроизвести такой символ над буквой. Тогда он вынес эту «крышу» перед именем аргумента, и получилось что-то наподобие:

^x . x * 10

А наборщик, увидев такой символ, использовал заглавную греческую букву Λ:

Λx . x * 10

Вот так и получилось, лямбда-исчисление.