Мне кажется, что это домашнее задание. Обдумайте, почему вам это сложно. Вы можете посмотреть, как ML и различные Лиспы пытаются решить эту проблему. Вы также можете посмотреть исходный код одного из интерпретаторов / компиляторов других языков, некоторые из них написаны с учётом учебы.

Думаю, Ваш вопрос очень и очень интересный. Если Вы также имели в виду, что хотите знать теоретические корни Вашего вопроса, тогда, я думаю, мы можем абстрагироваться от Haskell и исследовать Ваш вопрос в более общих концепциях алгоритмов. Что касается Haskell, я думаю, важны два следующих факта:

• Функции - это первоклассные граждане в Haskell
• Haskell является полным по Тьюрингу

, но я еще не обсуждал (насколько сильны языки имеет значение именно здесь)

Возможность для конкретных случаев, но беспроигрышная теорема для исчерпывающей

Я думаю, что в корне две теоремы информатики дают ответ. Если мы хотим абстрагироваться от технических деталей, мы можем исследовать Ваш вопрос в лямбда-исчислении (или в комбинаторной логике). Можно ли в них определить равенство? Таким образом, Давайте сначала ограничимся областью лямбда-исчисления или комбинаторной логики.

Следует отметить, что оба этих подхода к алгоритму очень минималистичны. В них нет `` предопределенных '' типов данных, ни чисел, ни логических значений, ни списков. Но Вы можете имитировать их все умными способами .

• Вместо логических значений Вы можете использовать функции проекции (селектора) ( Булевы числа Черча ).
• Вместо C -unions (или наследование классов C ++), вы можете использовать продолжения. Точнее говоря, это анализ случая, который Вы можете реализовать кратким и простым способом.
• Вы можете имитировать натуральные числа с помощью функций, которые повторяют композицию функций ( Число Черча ).
• Вы можете реализовать списки и деревья с помощью сложных алгебраических методов (катаморфизмы).

Таким образом, Вы можете имитировать все значимые типы данных даже в таких минималистичных «функциональных языках», как лямбда-исчисление и комбинаторная логика. Вы можете использовать лямбда-функции (или комбинаторы) в умной сцене, имитирующей нужный вам тип данных.

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

• Теорема Бема предусматривает: для любых двух ранее данных разных выражений (которые останавливают и не замораживают компьютер), Всегда можно написать подходящую функцию тестирования, которая решает правильно, являются ли два заданных выражения семантически одинаковыми (Csörnyei 2007: 132, = Th 7.2.2). В большинстве практических случаев (списки, деревья, логические значения, числа) теорема Бема предусматривает, что всегда можно записать подходящую конкретную функцию равенства. См. Пример списков в Tromp 1999 : Sec 2.
• Теорема о неразрешимости Скотта-Карри исключает возможность написания любой функции общего равенства, имеющей смысл для каждой возможной сцены (Csörnyei 2007: 140, = Th 7.4.1).

Теорема go

После того, как вы "внедрили" тип данных, вы можете написать для него соответствующую ему функцию равенства. Для большинства практических случаев (списки, числа, выборки для анализа случаев) не существует мистического "типа данных". для которого не хватало бы соответствующей функции равенства. Этот положительный ответ дается теоремой Бема.

Вы можете написать функцию числового равенства Чёрча, которая принимает два числа Чёрча и отвечает, равны ли они. Вы можете написать другую лямбда-функцию / комбинатор, которая принимает два (Черча) -булева и отвечает, равны они или нет. Более того, вы можете реализовать списки в чистом лямбда-исчислении / CL (предлагаемый способ - использовать понятие катаморфизмов), а затем вы можете определить функцию, которая отвечает на равенство для списков логических значений. Вы можете написать другую функцию, которая отвечает на равенство списков чисел Чёрча. Вы также можете реализовать деревья, и после этого вы можете написать функцию, которая отвечает на равенство для деревьев (для логических значений, а другая - для чисел Чёрча).

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

Непроходимая теорема

Но нет способа определить единую полностью автоматическую функцию равенства, работающую для всех возможных «типов данных». Если вы «реализуете» конкретный заданный тип данных в лямбда-исчислении, вам обычно приходится планировать его конкретную функцию равенства для этой сцены.

Более того, нет способа определить лямбда-функцию, которая принимала бы два лямбда-члена и ответьте, будут ли два лямбда-члена вести себя одинаково при сокращении. Даже больше, нет способа определить лямбда-функцию, которая принимала бы представление ( цитату ) двух лямбда-терминов и ответила бы, будут ли два исходных лямбда-члена вести себя одинаково при уменьшении (Csörnyei 2007: 141, Conseq 7.4.3). Этот беспроигрышный ответ дается теоремой о неразрешимости Скотта-Карри (Csörnyei 2007: 140, Th 7.4.1).

В других подходах к алгоритму

Я думаю, что два приведенных выше ответа не являются ограничивается лямбда-исчислением и комбинаторной логикой. Аналогичная возможность и ограничение применяется к некоторым другим концепциям алгоритмов. Например, не существует рекурсивной функции, которая взяла бы числа Гёделя двух унарных функций и решила бы, будут ли эти закодированные функции вести себя одинаково с точки зрения расширения (Monk 1976: 84, = Cor 5.18). Это следствие Риса » Теорема (Monk 1976: 84, = Th 5.17). Мне кажется, теорема Райса формально очень похожа на теорему о неразрешимости Скотта-Карри, но я еще не рассматривал ее.

Всеобъемлющее равенство в очень ограниченном смысле

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

• Я бы уменьшил оба рассматриваемых комбинаторных логических термина до их нормальных форм,
• и посмотрел, соответствуют ли они идентичны терминам .

Если так, то их нередуцированные исходные формы также должны быть эквивалентны семантически.

Но это работает только с серьезными ограничениями, хотя этот метод хорошо работает для нескольких практических целей. Мы можем выполнять операции с числами, списками, деревьями и т. Д., и проверяем, получаем ли мы ожидаемый результат. В моем quine (написанном на чистой комбинаторной логике) используется эта ограниченная концепция равенства, и этого достаточно, несмотря на то, что для этого quine требуются очень сложные конструкции (деревья терминов, реализованные в самой комбинаторной логике).

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

Ограничения можно увидеть также из того факта, что эта ограниченная концепция равенства может работать только для комбинаторов, имеющих нормальные формы. В качестве контрпримера: ограниченная концепция равенства не может проверить, I Ω = Ω , хотя мы хорошо знаем, что эти два члена могут быть взаимно преобразованы друг в друга.

Я должен все же рассмотреть, как существование этого ограниченного понятия равенства связано с отрицательными результатами, заявленными теоремой о неразрешимости Скотта-Карри и теоремой Райса. Обе теоремы имеют дело с частичными функциями, но я пока не знаю, какое это имеет значение.

Расширяемость

Но есть и другие ограничения концепции ограниченного равенства. Он не может иметь дело с концепцией протяженности. Например, он не замечает, что S K каким-либо образом связан с K I , несмотря на то, что S K ведет себя так же, как K I , когда они применяются как минимум к двум аргументам:

Последний пример требует более подробного объяснения. Мы знаем, что S K и K I не идентичны как термины: S K ≢ K I . Но если мы применим оба, соответственно, к любым двум аргументам X и Y , мы увидим связь:

• S K X Y ⊳ K Y ( X Y ) ⊳ Y
• K I X Y ⊳ I Y ⊳ Y

и, конечно, Y ≡ Y , для любого Y .

Конечно, мы не можем «попробовать» такую ​​взаимосвязь для каждого возможного экземпляра аргумента X и Y , потому что может быть бесконечно много таких экземпляров CL-термина, которые нужно заменить в эти метапеременные. Но мы не должны зацикливаться на проблеме бесконечности. Если мы дополним наш объектный язык (комбинаторную логику) (свободными) переменными:

• K - это терм
• S - терм
• Любая (свободная) переменная - это терм (новая строка, это модификация!)
• Если оба X и Y являются членами, то также ( X Y ) будет term
• Термины не могут быть получены никаким другим способом

, и мы определяем правила редукции соответствующим образом, надлежащим образом, тогда мы можем сформулировать экстенсиональное определение равенства «конечным» способом, не полагаясь на метапеременные с бесконечными возможными

Таким образом, если в терминах комбинаторной логики разрешены свободные переменные (объектный язык дополняется его собственными объектными переменными), то расширяемость может быть реализована в некоторой степени. Я еще не думал об этом. Что касается приведенного выше примера, мы можем использовать обозначение

S K = ₂ K I

(Curry & Feys & Craig 1958: 162 , = 5 C 5), на основании того факта, что S K x y и K I x y можно доказать, что они равны (уже без обращения к протяженности). Здесь x и y не являются метапеременными для бесконечно большого числа возможных экземпляров CL-членов в схемах уравнений, но являются первоклассными гражданами самого объектного языка. Таким образом, это уравнение больше не является схемой уравнений, а представляет собой одно-единственное уравнение.

Что касается теоретического исследования, мы можем понимать = как «объединение» = _n экземпляров для всех n .

В качестве альтернативы, равенство можно определить так, чтобы его индуктивное определение также учитывало протяженность. Мы добавляем еще одно правило вывода, имеющее отношение к экстенсиональности (Csörnyei 2007: 158):

• ...
• ...
• Если E , F являются комбинаторами , x является (объектной) переменной, а x не содержится ни в E , ни в F , то из ] E x = F x мы можем вывести E = F

Ограничение на отсутствие содержания важно, как показывает следующий контрпример: K x ​​≠ I , несмотря на то, что он K x x = I x . «Роли» двух (кстати, идентичных) переменных полностью различаются.

Каковы эти оставшиеся правила умозаключений? Вот они перечислены (Csörnyei 2007: 157):

Схемы аксиом преобразования:

• « K E F = E » выводится ( Схема K-аксиомы )
• « S F G H = F H ( G H ) '' выводима ( схема S-аксиомы )

Схемы аксиом равенства и правила вывода

• « E = E '' выводимо ( Схема аксиомы рефлексивности )
• Если " E = F " выводимо, то " ] F = E "также выводимо ( правило вывода симметрии )
• Если" E = F " выводимо, и " F = G " тоже выводимо, тогда также можно выводить " E = G » ( Правило транзитивности )
• Если « E = F » выводимо, то « E G = F ] G "также выводимо ( Правило Лейбница I )
• Если" E = F "выводимо, то" G E = G F "также выводится ( правило Лейбница II )

---

Ссылки

• Csörnyei, Zoltán (2007): Лямбда-калькулус. Функциональная программа alapjai. Будапешт: Typotex. ISBN-978-963-9664-46-3.
• Карри, Хаскелл Б. и Фейс, Роберт и Крейг, Уильям (1958). Комбинаторная логика . Vol. I . Амстердам: Издательство Северной Голландии.
• Мадоре, Дэвид (2003). Язык программирования без лямбда. Unlambda: кошмары вашего функционального языка программирования сбываются .
• Монк, Дж. Дональд (1976). Математическая логика . Тексты для выпускников по математике. Нью-Йорк • Гейдельберг • Берлин: Springer-Verlag.
• Тромп, Джон (1999). Двоичное лямбда-исчисление и комбинаторная логика . Можно загрузить в формате PDF и Postscript с авторской площадки для лямбда-исчисления и комбинаторной логики Джона .

Приложение

Теорема Бема

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

Утверждение

• Пусть E и F - это два разных замкнутых члена лямбда-исчисления,
• , и пусть оба они имеют нормальные формы.

Тогда, как утверждает теорема, есть подходящий способ проверки равенства с применением их к подходящей серии аргументов. . Другими словами: существует натуральное число n и серия замкнутых лямбда-членов G ₁ , G ₂ , ] G ₃ , ... G _n таким образом, что их применение к этой серии аргументов сводится к false и true соответственно:

• E G ₁ G ₂ G ₃ ... G _n ⊳ ложь
• F G ₁ G ₂ G ₃ ... G _n ⊳ верно

где true и false - два хорошо известных, простых, легко управляемых и различимых лямбда-члена:

• true ≡ λ x и . x
• ложь ≡ λ x y . y

Приложение

Как можно использовать эту теорему для реализации практических типов данных в чистом лямбда-исчислении? Неявное применение этой теоремы иллюстрируется способом определения связного списка в комбинаторной логике ( Tromp 1999 : Sec 2).

G _n ⊳ ложь

F G ₁ G ₂ G ₃ ... G _n ⊳ true

, где true и false - два хорошо известных, прирученных, легко управляемых и различимых лямбда-члены:

• истина ≡ λ x y . x
• ложь ≡ λ x y . y

Приложение

Как эту теорему можно использовать для реализации практических типов данных в чистом лямбда-исчислении? Неявное применение этой теоремы иллюстрируется тем, как связанный список может быть определен в комбинаторной логике ( Tromp 1999 : Sec 2).

G _n ⊳ ложь

F G ₁ G ₂ G ₃ ... G _n ⊳ true

, где true и false - два хорошо известных, прирученных, легко управляемых и различимых лямбда-члены:

• истина ≡ λ x y . x
• ложь ≡ λ x y . y

Приложение

Как можно использовать эту теорему для реализации практических типов данных в чистом лямбда-исчислении? Неявное применение этой теоремы иллюстрируется способом определения связного списка в комбинаторной логике ( Tromp 1999 : Sec 2).

G _n ⊳ true

, где true и false - два хорошо известных, прирученных, легко управляемых и различимых лямбда-члены:

• истина ≡ λ x y . x
• ложь ≡ λ x y . y

Приложение

Как эту теорему можно использовать для реализации практических типов данных в чистом лямбда-исчислении? Неявное применение этой теоремы иллюстрируется тем, как связанный список может быть определен в комбинаторной логике ( Tromp 1999 : Sec 2).

G _n ⊳ true

, где true и false - два хорошо известных, прирученных, легко управляемых и различимых лямбда-члены:

• истина ≡ λ x y . x
• ложь ≡ λ x y . y

Приложение

Как эту теорему можно использовать для реализации практических типов данных в чистом лямбда-исчислении? Неявное применение этой теоремы иллюстрируется тем, как связанный список может быть определен в комбинаторной логике ( Tromp 1999 : Sec 2).

y

Приложение

Как эту теорему можно использовать для реализации практических типов данных в чистом лямбда-исчислении? Неявное применение этой теоремы иллюстрируется тем, как связанный список может быть определен в комбинаторной логике ( Tromp 1999 : Sec 2).

y

Приложение

Как эту теорему можно использовать для реализации практических типов данных в чистом лямбда-исчислении? Неявное применение этой теоремы иллюстрируется тем, как связанный список может быть определен в комбинаторной логике ( Tromp 1999 : Sec 2).

(==) является частью класса типа Eq . Для каждого типа предоставляется отдельная реализация, в которой используется Eq . Поэтому, чтобы найти реализацию, вы обычно должны посмотреть, где определен ваш тип.