LINUX.ORG.RU

[Haskell] How to use Eq for functions?

 


0

1

Пусть у меня есть следующий тип данных:

data SomeDataType
    = SomeDataType { name :: String,
                     func :: String -> String }

Мне необходимо сравнивать экземпляры этого типа. Добавляю deriving(Eq). Получаю:

example.hs:4:14:
    No instance for (Eq (String -> String))
      arising from the 'deriving' clause of a data type declaration
                   at example.hs:4:14-15
    Possible fix:
      add an instance declaration for (Eq (String -> String))
      or use a standalone 'deriving instance' declaration instead,
         so you can specify the instance context yourself
    When deriving the instance for (Eq SomeDataType)

Это можно вылечить, указав что следует сравнивать только поля:

instance Eq SomeDataType where
    x == y = (name x) == (name y)

Works. Но всё-таки это не дело.

Собственно, как в Haskell проверить на равенство функции?

Ответ на: комментарий от Waterlaz

ммм... что значит алгоритмические представления? Это неразрешимая задача.

Я имею в виду структурное представление в реализации, т.е. объект который представляет функцию (или что бы то ни было) - будь то AST, flow-graph, SSA или CPS, или IR2 компонент с машинным уже кодом. Если сравнивать по AST и IR2 компонент не очень хорошо, то остальные представления можно стравнить. Вот, но в императивных языках обычно достаточно идентификации по положению (адресу), при этом функции которые делают одно и тоже могут быть не равны, но зато нет попыток решать эту самую неразрешимую (по Райсу) задачу.

quasimoto ★★★★
()
Ответ на: комментарий от Waterlaz

Ну так не интересно, а если область значения - РТД, он будет 8 лет думать?)

quasimoto ★★★★
()
Ответ на: комментарий от Waterlaz

но использовать это в высокоуровневой программе - не простительно.

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

quasimoto ★★★★
()
Ответ на: комментарий от Waterlaz

Потому что общая практика программирования на языке не требует такого?

quasimoto ★★★★
()
Ответ на: комментарий от Waterlaz

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

gzh
()
Ответ на: комментарий от gzh

Хотя бы потому что для этого необходимо (дважды) решить проблему остановки.

Ну вот, а мужики то и не знали - сравнивают функции на равенство и всё тут :)

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

От f(x)=sin(x) в математическом смысле до того чем это является в любом языке программирования - пропасть. Может вы ещё интегральный синус на равенство сравните (особенно в элементе из области определения равном нулю, очень нужно)?

А вот приближения к функциям - пожалуста. Т.е. представление (и кавычки не нужны - однозначное же понятие). Представление это структура, причём конечная структура (в этом и вся фишка того, чем являются функции в современном программировании - они конечны), любые конечные структуры можно сравнить за конечное время. Какие ещё проблемы останова? Я же написал до этого - о математическом смысле можно забыть - он присутствует в некоторых языках постольку по скольку, как моделируемая (не полная) сущность. Ну и при изучении основ этого программирования и его моделей.

При этом, если придерживаться некоторой дисциплины обращения с этими представлениями (а ничего другого нет), их и сравнивать не нужно - так мы приходим к сравнению по указателям/именам/уникальным-id которые только и имеют смысл.

Вы приводите в качестве довода поведения макрософтного компилятора (вордовский pdf) - лучше посмотрите как к этому подходят в языках с латентной типизацией, там всё проще (ну а в hasell всё строже).

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

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

>Представление это структура, причём конечная структура (в этом и вся фишка того, чем являются функции в современном программировании - они конечны)

Вне зависимости от этого, задача сравнения алгоритмически не разрешима.

Waterlaz ★★★★★
()
Ответ на: комментарий от quasimoto

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

Я бы даже сказал, что для того, что-бы писать хорошие программы, «думать о определениях вредно». (взял в кавычки потому, что не знаю, как это выразить словами, но надеюсь на понимание =)

Waterlaz ★★★★★
()
Ответ на: комментарий от quasimoto

Мой посыл был всего лишь в том, что знание представления функции ничего, по сути, не дает. Да, ЕСЛИ представления одинаковы, то функции точно равны. В точности как неравенство хешей, см. выше. Проблема как раз в том, что они, представления функции, очень уж легко становятся разными. «Дисциплина» тут не при чем. Насколько я понимаю, Waterlaz пишет о том же. Хоть я и не являюсь практикующим «для production» разработчиком на Haskell, IMHO очень хорошо что хотя бы в Haskell нет этого «компромисса», провоцирующего на неправильные решения.

Про «языки с латентной типизацией» не понял. В данном вопросе, как мне представляется, типизация вообще не при чем, это мешающий параметр. Тем более не понял про вородовский pdf.

gzh
()
Ответ на: комментарий от quasimoto

> Хотя бы потому что для этого необходимо (дважды) решить проблему остановки.

Ну вот, а мужики то и не знали - сравнивают функции на равенство и всё тут :)

Да, здесь я погорячился.

gzh
()
Ответ на: комментарий от Waterlaz

Вне зависимости от этого, задача сравнения алгоритмически не разрешима

Задача сравнения чего? Функций в математическом смысле в алгоритмическом представлении - да, теорема Райса и всё такое, но это задача сравнения того, чего нет в программировании :) Нет там функций в математическом смысле, есть только модельные представления. Что объекты типа

typedef struct {
  Symbol       name;
  Module       module;
  Id           id;
  Address      address;
  Environment* environment;
  Variable*    variables;
  ...
} FunctionalObject;

или

data SSAElement = SSAElement Opcode Argument Argument
type SSABlock   = [SSAElement]
или
data Term = Symbol
          | Abstraction Symbol Term
          | Application Term Term

-- or

data Term = Symbol
          -- * primitives:
          ...
          -- * majors:
          | Abstraction Symbol Term
          | Application Term   Term

нельзя сравнить? Как раз равенство структурных РТД объектов это рекурсивное распространение квантора общности равенства во все поля - в любом случае можно сравнивать.

Кстати, последнее представление в формальном смысле самое выгодное - например, для нумералов Чёрча выполняются аксиомы равенства (на то они и нумералы), следовательно в таком представлении любые арифметические функции алгоритмически сравнимы (это при том, что высказывания в самой аксиоматике Пеано алгоритмически неразрешимы), также алгоритмически сравнимы функции в булевом смысле и в смысле геометрии Евклида (которая вообще алгоритмически разрешима). Хотя тут стоит вопрос о необходимости и достаточности - два равных представления всегда моделируют равные функции (достаточность), но непонятно - существует ли два неравных представления одной и той же функции (необходимость).

«думать о определениях вредно». (взял в кавычки потому, что не знаю, как это выразить словами, но надеюсь на понимание =)

Смутно, смутно :) Если определение создаёт чёрный ящик с поведением - пусть он будет в одном экземпляре, а дальше уже начинается декомпозиция. При этом сравнивать оказывается просто нечего - f обозначает один ящик, а g - другой, разве что сравнить что f == f, но это и так понятно. Как-то так понял :)

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

quasimoto ★★★★
()
Ответ на: комментарий от gzh

Да, ЕСЛИ представления одинаковы, то функции точно равны. В точности как неравенство хешей, см. выше.

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

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

Вы вообще внимательно читаете? Доказать что? Что если «алгоритмические представления» двух функций одинаковы, то и сами функции одинаковы? Это по определению «алгоритмического представления». И «необходимости и достаточность» ЧЕГО вы утверждаете? С чем Вы спорите, какой тезис Вас не устраивает?

gzh
()
Ответ на: комментарий от quasimoto

Ну ужас. Еще раз давайте, с другой стороны. Если это РАВЕНСТВО, то АЛГОРИТМ может сказать так: если операция сравнения на двух функциях f и g дает false, то существует такой элемент x, что f(x) не равно g(x), не так ли? И, если алгоритм сделает такое предположение, то он ошибется, если будет использовать вместо истинного равенства функций - «равенство алгоритмических представлений». Вы с этим согласны? Если да, все хорошо, я именно это и утверждал, не более и не менее. Если нет - то тоже как бы говорить не о чем.

gzh
()
Ответ на: комментарий от gzh

Вы вообще внимательно читаете?

Я? Ну я же не спрашиваю - «о чём это мы тут говорим?» :) Т.е. это вы - либо не все сообщения относящиеся к топику читаете, либо читаете не внимательно, либо их не понимаете (тогда тут моя вина - недостаточно ясно говорю).

Ну ужас. Еще раз давайте, с другой стороны.

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

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

Нет (sic!), не спешите уходить :) Я утверждаю что есть представление для которого равенство состоит в отношениях необходимости и достаточности с математическим равенством - для всех классов функций, которые используются в программировании (и могут быть представлены в этом представлении). Т.е. говорю:

* Существует такое представление, что:

* «равенство представлений» <=> (тогда и только тогда) «математическое равенство функций»

* «неравенство представлений» <=> (тогда и только тогда) «математическое неравенство функций»

* Для функций принадлежащих непустому (неформально - достаточно широкому, годному для практического программирования) множеству классов функций.

Собственно, даю подсказку: если говорить фомально/математически, то математическая форма это тоже представление, причём конечное. И лямбда исчисление изначально ведь просто представление математических функций от логики. Только его немного допилить/расширить сабжевыми законами - и будет oll korrect.

Если нет - то тоже как бы говорить не о чем.

Почему? А вы не хотите доказать отсутсвие такого представления? Знаете, мне просто - доказать наличие это: 1) построить его, 2) доказать необходимость и достаточность для нужных классов функций. А вот доказывать отсутсвие - это фиговое дело, как с теоремой Ферма. «Не бережёте вы себя ...» (с) :)

quasimoto ★★★★
()
Ответ на: комментарий от gzh

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

Вот си - язык в котором типизация довольно туманная, фактически любой тип это просто мера raw-memory, просто обвёртка и эта raw-memory единственный базовый тип. Так что функции различаются по позиции в этой памяти. А в более абстрактных языках с латентной типизацией (динамических) уже принят подход разделения объектов по типам, и сравнение производится между функциональными объектами (технически, обычно, это просто структуры в смысле си).

Но такое сравнение никому не понравилось - в haskell, к примеру, есть теория типов, причём формальная - нужно соответствовать. Вот и пошёл разговор на тему - есть ли такое представление, а я и говорю, что есть. Утверждаю, что это представление - обычные лямбда-термы в структурном смысле + набор примитивов, а конкретно лямбда-термы после:

read, normalize_fclass_1, normalize_fclass_2, ...

read               :: String -> LCTerm
normalize_fclass_* :: LCTerm -> LCTerm

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

quasimoto ★★★★
()
Ответ на: комментарий от quasimoto

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

gzh
()
Ответ на: комментарий от quasimoto

В принципе, даже в случае арифметики - а как вы собираетесь бороться с тождественными выражениями? Потому что если не собираетесь, все опять лишено смысла. А если собираетесь, то как?

gzh
()
Ответ на: комментарий от gzh

Но вот в отношении нормализации рекурсивных функций у меня большие сомнения. Вы полагаете, это реально?

Я думаю, что достаточно комбинаторов и разных морфизмов для РТД - с ними всё однозначно.

К примеру, факториал:

n! = prod(i, i = 1 .. n) => (|1, (*)|) [1..n]

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

а как вы собираетесь бороться с тождественными выражениями?

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

quasimoto ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.