Ищет Черч-кодирование (лямбда-исчисление) для определения < , >,! =

Question

я должен создать некоторые функции лямбды для>, < и! =

Я не имею представления о том, как, может кто-нибудь помочь Я пожалуйста ? PS: Мы только начали с Lambda Calculus, поэтому, пожалуйста, не принимайте никаких предшествующих знаний.

Благодарим вас в ожидании!

Edit - То, что я имел в виду Arithmetic in Lambda Calculus

Edit 2 - Более точно: Ищете Черч-кодирования (лямбда-исчисление) для определения < , > , !=

---

Примечание редактора: Я думаю, что это то, что ОП пытается задать:

Я пытаясь осуществить следующие операции в бестиповом лямбда-исчислении с использованием кодировки Церкви:

1. Больше чем (GT или >).
2. Мало (LT или <).
3. Не равен (NE или !=).

Я уже знаю, как реализовать следующее:

1. Boolean верно (TRUE или λx.λy.x).
2. Boolean false (FALSE или λx.λy.y).
3. Логические и (AND или λp.λq.p q p).
4. Логический или (OR или λp.λq.p p q).
5. Логический не (NOT или λp.λa.λb.p b a).

Как бы вы написать функции GT, LT и NE в бестиповом лямбда-исчислении?

Answer 1

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

Я думаю, что я помню реализацию натуральных чисел. Ряд п представлена ​​как функция принимает функцию ф и значение х, и применяя Fп раз на х.

zero = λf . λx . x 
succ = λn . λf . λx . n f (f x) 

Answer 2

Использование "An Introduction To Functional Programming Through Lambda Calculus" Грег Michaelson

Начиная с

Раздел 4.8.3. Сравнение

Существует множество способов определения равенства между числами. Один подход должен заметить, что разница между двумя равными числами равна ноль. Однако, если мы вычтем число из меньшего числа, мы также получим , получим нуль, поэтому нам нужно найти абсолютную разницу между ними; разница независимо от порядка сравнения. Чтобы найти абсолютную разницы между двумя числами с, добавить разницу между первым и второй к разности между вторым и первым:

Защита abs_diff х = добавить (к югу х) (суб ух)

Если они оба одинаковы, то абсолютные разности будут равны нулю , потому что результат взятия каждого из другого будет равен нулю. Если сначала больше второго, тогда абсолютная разница будет первой минус вторая, потому что вторая минус первая будет ноль. Аналогично, если вторая больше первой, тогда разница будет второй минус первая, потому что первый минус второй будет равен нулю.

Таким образом, мы можем определить:

Защиту равна х у = iszero (abs_diff х у)

Мы также можем использовать вычитание для определения арифметических неравенств. Для Например, числа больше, чем другой, если вычесть второй из первых дает ненулевой результат:

Защита больше х = нет (iszero (суб х))

Меньше определяются в решениях секции упражнений в спину.

Защиту меньше х у = больше у й

Теперь, используя книгу в ссылке просто найти все подчиненный функции и вы будете иметь =,>, <. Хотя книга не определяет! = Это должно быть очевидно.

EDIT

За комментарием по WillNess

4.8.2. Вычитание

Чтобы найти разницу между двумя числами, найдите разницу между числами после уменьшения обоих.Разница между числом и нулем номер:

прн к югу х =
если iszero у
то х
еще к югу (пред х) (пред у)

Обратите внимание "Now using the book in the link just find all of the subordinate functions".

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

Answer 3

В статье Википедии о кодировании церкви есть раздел predicates, который охватывает EQ и LEQ