Функции как числа

предыдущая серия

Как определить числа с помощью одних только функций? Строго говоря, мы определяем не числа, известные нам как абсолютные арифметические понятия, а некоторые условные сущности, которые в нашем контексте лямбда-исчислений ведут себя как натуральные числа. Такие сущности называются нумералы Чёрча.

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

Соответственно, ноль — это нулевое количество применений функции следования (просто возвращается сам аргумент без аппликации):

ZERO = lambda f: lambda z: z

Единица — применяем один раз, двойка — два раза, и т. д.

ONE   = lambda f: lambda z: f(z)
TWO   = lambda f: lambda z: f(f(z))
THREE = lambda f: lambda z: f(f(f(z)))

Исключая нуль, для остальных чисел можно выделить повторяющийся кусочек f(f(…)) в отдельную функцию композиции:

compose = lambda f,g: lambda x: f(g(x))

Тогда, более наглядно

TWO   = lambda f: compose(f,f)
THREE = lambda f: compose(f,compose(f,f))

Чтобы превратить нумералы в реальные числа, надо определить простую функцию увеличения значения на единицу, и начать итерации аппликаций с нуля:

natify = lambda c: c(lambda x: x+1)(0)

natify(THREE) # вернёт 3

По сути, мы делаем что-то такое:

p1 = lambda x: x+1
p1(p1(p1(0)))

Теперь сложение нумералов N и M. Очевидно, нам надо применить итерации функции f сперва N раз, а потом M раз:

SUM = lambda n: lambda m: lambda f: compose(n(f),m(f))

FIVE = SUM (TWO) (THREE)
natify(FIVE) # вернёт 5

Так же элегантно записывается и умножение:

MUL = lambda n: lambda m: lambda f: compose(m,n)(f)
FOUR = MUL (TWO) (TWO)
natify(FOUR) # вернёт 4

Списки определяются с помощью лямбда-исчислений немного сложнее, но объём кода тоже минимален — единичные строки! Таким образом, с помощью одних лишь функций мы определили фундаментальный программистский набор.

Далее математики будет немного больше.

Поделиться статьей ...Share on Facebook0Share on Google+0Tweet about this on TwitterShare on LinkedIn0Share on VKPrint this page

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *