Лямбда выражения в haskell
Обновлено: 22.12.2024
Пришло время познакомиться с важной концепцией — лямбда-функцией. Именно с неё всё и началось. Приготовьтесь: в этой главе нас ждут новые открытия.
Истоки
В далёких 1930-х молодой американский математик Алонзо Чёрч задался вопросом о том, что значит «вычислить» что-либо. Плодом его размышлений явилась система для формализации понятия «вычисление», и назвал он эту систему «лямбда-исчислением» (англ. lambda calculus, по имени греческой буквы λ ). В основе этой системы лежит лямбда-функция, которую в некотором смысле можно считать «матерью функционального программирования» в целом и Haskell в частности. Далее буду называть её ЛФ.
В отношении ЛФ можно смело сказать: «Всё гениальное просто». Идея ЛФ столь полезна именно потому, что она предельно проста. ЛФ — это анонимная функция. Вот как она выглядит в Haskell:
Обратный слэш в начале — признак ЛФ. Сравните с математической формой записи:
Похоже, не правда ли? Воспринимайте обратный слэш в определении ЛФ как спинку буквы λ .
ЛФ представляет собой простейший вид функции, эдакая функция, раздетая догола. У неё забрали не только объявление, но и имя, оставив лишь необходимый минимум в виде имён аргументов и внутреннего выражения. Алонзо Чёрч понял: чтобы применить функцию, вовсе необязательно её именовать. И если у обычной функции сначала идёт объявление/определение, а затем (где-то) применение с использованием имени, то у ЛФ всё куда проще: мы её определяем и тут же применяем, на месте. Вот так:
Помните функцию square ? Вот это её лямбда-аналог:
Лямбда-абстракция (англ. lambda abstraction) — это особое выражение, порождающее функцию, которую мы сразу же применяем к аргументу 5 . ЛФ с одним аргументом, как и простую функцию, называют ещё «ЛФ от одного аргумента» или «ЛФ одного аргумента». Также можно сказать и о «лямбда-абстракции от одного аргумента».
Строение
Строение лямбда-абстракции предельно простое:
Соответственно, если ЛФ применяется к двум аргументам — пишем так:
И когда мы применяем такую функцию:
то просто подставляем 10 на место x , а 4 — на место y , и получаем выражение 10 * 4 :
В общем, всё как с обычной функцией, даже проще.
Мы можем ввести промежуточное значение для лямбда-абстракции:
Теперь мы можем применять mul так же, как если бы это была сама лямбда-абстракция:
И здесь мы приблизились к одному важному открытию.
Тип функции
Мы знаем, что у всех данных в Haskell-программе обязательно есть какой-то тип, внимательно проверяемый на этапе компиляции. Вопрос: какой тип у выражения mul из предыдущего примера?
Ответ прост: тип mul такой же, как и у этой лямбда-абстракции. Из этого мы делаем важный вывод: ЛФ имеет тип, как и обычные данные. Но поскольку ЛФ является частным случаем функции — значит и у обыкновенной функции тоже есть тип!
В нефункциональных языках между функциями и данными проведена чёткая граница: вот это функции, а вон то — данные. Однако в Haskell между данными и функциями разницы нет, ведь и то и другое покоится на одной и той же Черепахе. Вот тип функции mul :
Погодите, скажете вы, но ведь это же объявление функции! Совершенно верно: объявление функции — это и есть указание её типа. Помните, когда мы впервые познакомились с функцией, я уточнил, что её объявление разделено двойным двоеточием? Так вот это двойное двоеточие и представляет собой указание типа:
Точно так же мы можем указать тип любых других данных:
Хотя мы знаем, что в Haskell типы выводятся автоматически, иногда мы хотим взять эту заботу на себя. В данном случае мы явно говорим: «Пусть выражение coeff будет равно 12 , но тип его пусть будет Double , а не Int ». Так же и с функцией: когда мы объявляем её — мы тем самым указываем её тип.
Но вы спросите, можем ли мы не указывать тип функции явно? Можем:
Это наша старая знакомая, функция square . Когда она будет применена к значению типа Int , тип аргумента будет выведен автоматически как Int .
И раз функция характеризуется типом так же, как и прочие данные, мы делаем ещё одно важное открытие: функциями можно оперировать как данными. Например, можно создать список функций:
Выражение functions — это список из двух функций. Два лямбда-выражения порождают эти две функции, но до момента применения они ничего не делают, они безжизненны и бесполезны. Но когда мы применяем функцию head к этому списку, мы получаем первый элемент списка, то есть первую функцию. И получив, тут же применяем эту функцию к строке "Hi" :
Это равносильно коду:
При запуске программы мы получим:
Кстати, а каков тип списка functions ? Его тип таков: [String -> String] . То есть список функций с одним аргументом типа String , возвращающих значение типа String .
Локальные функции
Раз уж между ЛФ и простыми функциями фактически нет различий, а функции есть частный случай данных, мы можем создавать функции локально для других функций:
Это — две функции, которые мы определили прямо в where -секции, поэтому они существуют только для основного выражения функции validComEmail . С простыми функциями так поступают очень часто: где она нужна, там её и определяют. Мы могли бы написать и более явно:
Впрочем, указывать тип столь простых функций, как правило, необязательно.
Вот как этот код выглядит с лямбда-абстракциями:
Теперь выражения containsAtSign и endsWithCom приравнены к ЛФ от одного аргумента. В этом случае мы не указываем тип этих выражений. Впрочем, если очень хочется, можно и указать:
Лямбда-абстракция взята в скобки, чтобы указание типа относилось к функции в целом, а не только к аргументу e :
Для типа функции тоже можно ввести псевдоним:
Впрочем, на практике указание типа для лямбда-абстракций встречается исключительно редко, ибо незачем.
Отныне, познакомившись с ЛФ, мы будем использовать их периодически.
И напоследок, вопрос. Помните тип функции mul ?
Что это за буква a ? Во-первых, мы не встречали такой тип ранее, а во-вторых, разве имя типа в Haskell не обязано начинаться с большой буквы? Обязано. А всё дело в том, что буква a в данном случае — это не совсем имя типа. А вот что это такое, мы узнаем в одной из ближайших глав.
Для любопытных
А почему, собственно, лямбда? Почему Чёрч выбрал именно эту греческую букву? По одной из версий, произошло это чисто случайно.
Шли 30-е годы прошлого века, компьютеров не было, и все научные работы набирались на печатных машинках. В первоначальном варианте, дабы выделять имя аргумента ЛФ, Чёрч ставил над именем аргумента символ, похожий на ^ . Но когда он сдавал работу наборщику, то вспомнил, что печатная машинка не сможет воспроизвести такой символ над буквой. Тогда он вынес эту «крышу» перед именем аргумента, и получилось что-то наподобие:
А наборщик, увидев такой символ, использовал заглавную греческую букву Λ :
Читайте также: