Нумерал Чёрча — это функция высшего порядка, применяющая один свой аргумент (произвольную функцию) N раз подряд к другому своему аргументу:
zero f x = x
one f x = f x
two f x = f (f x)
Это позволяет очень изящно определить полукольцо над натуральными числами с нулём.
(inc n) f x = n f (f x) -- тут я пишу скобки в объявлении, чтобы сделать карринг более наглядным и подчеркнуть суть:
(plus n m) f x = n f (m f x) -- (inc n), (plus n m), (mult n m) - это нумералы, т.к. они принимают аргументы f и x
(mult n m) f x = n (m f) x -- а (m f) - функция одного аргумента - тут без карринга пришлось бы тащить лямбды
Но вот с обратными операциями возникают понятные сложности.
| | немножко писанины |
| | Обычно декремент делается на сдвиге
(dec n) f x = unwrap (n (patch f) (wrap x))
где
wrap x = make-pair undefined x
(patch f) ab = make-pair (get-second ab) (f (get-second ab))
unwrap ab = get-first ab
где, в свою очередь, работа с парой - это тоже функции высшего порядка
(make-pair a b) q = q a b
get-first ab = ab drop-second
get-second ab = ab drop-first
drop-first a b = b
drop-second a b = a
после чего вычитание
(minus1 n) f x = (dec n) f x
(minus2 n) f x = (dec (dec n)) f x
(minus3 n) f x = (dec (dec (dec n))) f x
(minus n m) f x = (m pred n) f x -- m раз применяем декремент к нумералу n
Важный момент: нумералы — по-прежнему изоморфны неотрицательным числам, поэтому декремент нуля не определён.
Обычно там делают идемпотентную заглушку:
wrap x = make-pair x x
что приводит к
(dec zero) f x = unwrap (zero (patch f) (wrap x))
= get-first (zero (patch f) (make-pair x x))
= get-first (make-pair x x)
= x
(dec zero) f x = x = zero f x
|
| | |
Предлагаю размять голову — написать минималистичную реализацию отрицательных нумералов. Что для этого понадобится изменить в дизайне?
Перекуём баги на фичи!
