M обозначает функцию, а N обозначает аргумент. Все функции являются функциями одного аргумента, но
они могут принимать и возвращать функции. Поэтому применение трёх аргументов к функции F un будет
выглядеть так:
216 | Глава 14: Лямбда-исчисление
((( F un Arg 1) Arg 2) Arg 3)
Третье правило говорит о том как создавать функции. Специальный символ лямбда ( λ) в выражении
( λx. M ) говорит о том, что мы собираемся определить функцию с аргументом x и телом функции M . С та-
кими функциями мы уже сталкивались. Это безымянные функции. Приведём несколько примеров функций.
Начнём с самого простого, определим тождественную функцию:
( λx. x)
Функция принимает аргумент x и тут же возвращает его в теле. Теперь посмотрим на константную функ-
цию:
( λx. ( λy. x))
Константная функция является функцией двух аргументов, поэтому наш терм принимает переменную
x и возвращает другой терм функцию ( λy. x). Эта функция принимает y, а возвращает x. В Haskell мы бы
написали это так:
\x -> (\y -> x)
Точка сменилась на стрелку, а лямбда потеряла одну ножку. Теперь определим композицию. Композиция
принимает две функции одного аргумента и направляет выход второй функции на вход первой:
( λf. ( λg. ( λx. ( f ( gx)))))
Переменные f и g – это функции, которые участвуют в композиции, а x это вход результирующей функ-
ции. Уже в таком простом выражении у нас пять скобок на конце. Давайте введём несколько соглашений,
которые облегчат написание термов:
Пишем
Подразумеваем
Опустим внешние скобки:
λx. x
( λx. x)
В применении группируем скобки
f ghx
(( f g) h) x
влево:
Ф функциях группируем скобки
λx. λy. x
( λx. ( λy. x))
вправо:
Пишем функции нескольких
λxy. x
( λx. ( λy. x))
аргументов с одной лямбдой:
С этими соглашениями мы можем переписать терм для композиции так:
λf gx. f ( gx)
Сравните с выражением на языке Haskell:
\f g x -> f (g x)
Выражения очень похожи. Haskell иногда называют засахаренной версией лямбда исчисления. В лямбда-
исчислении мы не будем ставить пробелы для применения аргументов к функции. Мы будем считать, что
все имена однобуквенные. При этом переменные мы будем писать с маленькой буквы, а составные термы с
большой.
Определим ещё несколько функций. Например так выглядит функция flip: