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

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

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

Спасибо в ожидании!

Изменить. Я имел в виду Арифметику в лямбда-исчислении

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

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

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

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

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

  1. Логическое значение true (TRUE или λx.λy.x).
  2. Логическое значение 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 в нетипизированном лямбда-исчислении?


functional-programming lisp scheme church-encoding lambda-calculus
person Blnpwr    schedule 11.12.2013    source источник
comment
Что означает создать лямбда-функцию для ›? Лямбда, которая просто обертывает оператор? Какой в ​​этом смысл?   -  person Sebastian Redl    schedule 11.12.2013
comment
@SebastianRedl: OP, похоже (извините, если я ошибаюсь) не очень привык к haskell и может не знать, что ‹, › и /= - это обычные функции.   -  person Kritzefitz    schedule 11.12.2013
comment
Так что, в принципе, он может просто захотеть секцию (<), которую можно использовать как обычную функцию.   -  person Sebastian Redl    schedule 11.12.2013
comment
Мы не знаем, чего он хочет.   -  person augustss    schedule 11.12.2013
comment
лямбда для ›: (\a b -> a > b). Можете ли вы создать два других сейчас?   -  person Will Ness    schedule 11.12.2013
comment
Мех, он сильно изменил значение, даже не зная об этом, и задание на 90% было посвящено разделам.   -  person Bartek Banachewicz    schedule 11.12.2013
comment
О, позвольте мне объяснить это на примере функции И, записанной как Lambda: lambdax x. лямбда у. xy F ( F = lambda x. lambda y . y) Мы не в Haskell, это просто для формальных целей   -  person Blnpwr    schedule 11.12.2013
comment
Для тех, кто еще не знает, о чем мой вопрос: simple.wikipedia.org/wiki/Lambda_calculus Ключевое слово: ЛЯМБДА-ИСЧИСЛЕНИЕ   -  person Blnpwr    schedule 11.12.2013
comment
@ user2938633 О, мы знаем, что такое лямбда, большое спасибо. Но какого черта ты спрашиваешь?   -  person Bartek Banachewicz    schedule 11.12.2013
comment
Хорошо, посмотрите на мою функцию и, написанную на лямбда-исчислении. Теперь я не ищу И еще я ищу ›. Я хочу написать лямбда-исчисление для › так же, как я написал И как лямбда-исчисление   -  person Blnpwr    schedule 11.12.2013
comment
Хорошо, давайте начнем с этого вопроса: как бы вы определили оператор и ^ в лямбда-исчислении без использования Haskell?   -  person Blnpwr    schedule 11.12.2013
comment
Похоже, что ОП имеет в виду en.wikipedia.org/wiki/   -  person Chris Taylor    schedule 11.12.2013
comment
Точно, большое спасибо, Крис Тейлор.   -  person Blnpwr    schedule 11.12.2013
comment
a › b == (a-b) › 0. Это помогает?   -  person Will Ness    schedule 11.12.2013
comment
К сожалению, нет, я должен писать в арифметическом стиле, пожалуйста, проверьте мою ссылку, размещенную в вопросе (будет ссылка на Википедию)   -  person Blnpwr    schedule 11.12.2013
comment
вы прочитали этот связанный раздел до конца? Есть ли функция PRED? Что он говорит о функции SUB и возвращаемом ею значении в случае m > n и в других случаях? Есть ли в следующем разделе функция ISZERO?   -  person Will Ness    schedule 11.12.2013
comment
@user2938633 user2938633 Итак, вам нужна церковная кодировка операторов <, > и !=. Я предлагаю вам изменить свой вопрос, чтобы уточнить это. Кроме того, не уверен, почему вы пометили этот вопрос как Haskell, поскольку здесь нет ничего специфичного для Haskell.   -  person Pedro Rodrigues    schedule 11.12.2013
comment
У него нет функции pre. Мне просто нужно определить операторы ‹ › и != с церковным кодированием (лямбда-исчисление)   -  person Blnpwr    schedule 11.12.2013
comment
Пожалуйста, посмотрите на отредактированный вопрос. Это очищает все.   -  person Blnpwr    schedule 11.12.2013

Ответы (3)


arrow_upward
2
arrow_downward

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

Кажется, я помню реализацию натуральных чисел. Число n представлено как функция, принимающая функцию f и значение x и применяющая f n раз на x.

zero = λf . λx . x
succ = λn . λf . λx . n f (f x)
person md2perpe    schedule 11.12.2013

arrow_upward
4
arrow_downward

Используя "Введение в функциональное программирование с помощью лямбда-исчисления" Грег Майклсон

Начиная с

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

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

def abs_diff x y = добавить (sub x y) (sub y x)

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

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

def равно x y = iszero (abs_diff x y)

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

def больше x y = not (iszero (sub x y))

Меньше определено в разделе решений к упражнениям сзади.

Def меньше x y = больше y x

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

РЕДАКТИРОВАТЬ

По комментарию УиллНесс

4.8.2. вычитание

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

rec sub x y =
если равно нулю y
then x
else sub (pred x) (pred y)

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

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

person Guy Coder    schedule 11.12.2013
comment
да, но что такое sub? ОП говорит, что у них даже нет функции pred. Спасибо за ссылку. :) - person Will Ness; 12.12.2013

arrow_upward
1
arrow_downward

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

person dansalmo    schedule 13.12.2013