[Haskell] How to use Eq for functions?

А как вы вообще планируете проверять на равенство функции? Дайте определение равных функций.

> А как вы вообще планируете проверять на равенство функции? Дайте определение равных функций.

Если этому полю соответствует одно и тоже определение функции, и если частично применённые аргументы совпадают.

Хотя да, это неполно. Если бы функция определялась лямбдой — где её определение?

Ок, тема закрыта. Сравнивать функции нельзя.

http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A...

мда... в CL и Scheme с этим проще, почему в Хаскелле нельзя так сделать?

в CL и Scheme с этим проще, почему в Хаскелле нельзя так сделать?

Потому что в Haskell функция это скорее математическое понятие, а в CL, например, это нечто что по прежнему можно сравнить по указателю (иначе говоря, это нечто что имеет своё положение в образе).

Хотя с точки зрения имплементации это можно сделать и в Haskell, но, видимо, это противоречит практике программирования - не принято.

По теме: вообще instance какого нибудь стандартного класса для своего типа достаточно часто можно видеть, не намного реже deriving.

> мда... в CL и Scheme с этим проще, почему в Хаскелле нельзя так сделать?

Очевидно из-за частичного применения.

ну причем тут это, quasimoto дело говорит

Если этому полю соответствует одно и тоже определение функции, и если частично применённые аргументы совпадают.

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

Если бы функция определялась лямбдой — где её определение?

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

Частично применение есть и в лиспах, но оно никак не мешает функции equal.

Частично применение есть и в лиспах, но оно никак не мешает функции equal.

С криком «ЩИТО?» полез в ракетку и немного офигел:

> (define (f x) (λ (y) '()))
> (equal? f f)
#t
> (equal? (f 1) (f 1))
#t

Но:

> (equal? (f 1) (f 2))
#t

Немного подумав:

> (define (g x) (λ (y) x))
> (equal? (g 1) (g 1))
#f

SBCL:

* (defun f (x) (lambda (y) nil))
F

* (equal (f 1) (f 1))
T

* (equal (f 1) (f 2))
T

* (defun g (x) (lambda (y) x))
G

* (equal (g 1) (g 1))
NIL

Т.е. equal лажает.

> Если бы функция определялась лямбдой — где её определение?

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

В этом и гадость. Сравнением адреса не обойтись.

Вообще-то это не то частичное применение :) Но это уже другая тема (как правильно его делать чтобы был замес с каррированием и point-free).

За Racket не скажу. А вот SBCL не врёт. В вашем случае в замыкании не используется параметр замыкания x поэтому возвращается один и тот же объект. А вот если:

CL-USER> (defun f (x) (lambda (y) (+ x y)))
F
CL-USER> (equal (f 1) (f 2))
NIL
CL-USER> (equal (f 1) (f 1))
NIL

Уже зависит - каждый раз происходит алокация нового замыкания (как возвращенной функции) и они уникальны - не равны друг другу.

Т.е. встречный вопрос - а какого поведения вы ожидаете для частичных функций?

Т.е.

(defun f (x) (lambda (y) nil))

f ссылается на представление #<FUNCTION (LAMBDA (Y)) {...}>, это, натурально, функция в памяти, без всяких хитростей: (f 1) (f 2) - ссылаются на один и тот же объект.

(defun f (x) (lambda (y) (+ x y)))

f ссылается #<CLOSURE (LAMBDA (Y)) {B9E6FC5}> (разница - там LAMBDA тут CLOSURE), это хитрый объект - он производит FUNCTION при своем вызове. (f 1) произведет одну, следующий (f 1) другую, (f 2) - третью. При этом они ещё и сборщиком потом собираются. А в первом варианте сборщик не собирает функцию.

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

> Вообще-то это не то частичное применение :)

Я не представляю его в лиспах иначе. Как иначе?

Т.е. встречный вопрос - а какого поведения вы ожидаете для частичных функций?

Да такого и ожидаю, мне смутило (equal? (f 1) (f 2)) => #t

В этом и гадость. Сравнением адреса не обойтись.

Это не гадость, это то что не даёт программа отжирать по гигабайтам памяти на пустом месте %)

Да такого и ожидаю, мне смутило (equal? (f 1) (f 2)) => #t

Если возвращаемая лямбда не зависит от внешнего параметра - так и будет. Если зависит - это уже замыкание. Т.е. по вашему (f 1) == (f 2), но при этом ((f 1) 1) => 2, а ((f 2) 1) => 3 - функции равны, но ведут они себя по-разному на одинаковом аргументе :)

Как там

a = b & b = c => a = c

(f 1) = x & (f 2) = x => (f 1) = (f 2) ( = x ) (x 1) = 2 & (x 1) = 3 => 2 = 3

Я не представляю его в лиспах иначе. Как иначе?

Не эмулировать с помощью вложенных лямбд а сделать честно функциональный объект с разделением free-variables и bound-varibles - как оно в лямбда-исчислении.

Просто автоматическое каррирование конфликтует с практикой использования &optional, &key и т.д. - либо то либо другое (либо дикая смесь), в CL (да и в Scheme) можно прибавит каррирование, вот чего хочется от Haskell - это возможности сказать, мол, нефиг тут каррировать :) Хотя это тоже решается - аргументом-списком, содержащим аргументы и optinal/rest/key спецификаторы.

> (f 1) = x & (f 2) = x => (f 1) = (f 2) ( = x ) (x 1) = 2 & (x 1) = 3 => 2 = 3

Что это?

> вот чего хочется от Haskell - это возможности сказать, мол, нефиг тут каррировать :) Хотя это тоже решается - аргументом-списком, содержащим аргументы и optinal/rest/key спецификаторы.

Можешь привести пример? Что это вообще за спецификаторы, первый раз слышу.

Что это?

Как бэ шутка ;) Т.е. мы говорим о равенстве, которому не удовлетворяют замыкания - получается 2 = 3 и раздоказательство от противного.

Т.е. по вашему (f 1) == (f 2), но при этом ((f 1) 1) => 2, а ((f 2) 1) => 3 - функции равны, но ведут они себя по-разному на одинаковом аргументе :)

если (f 1) = x и (f 2) = x то (f 1) = (f 2) = x

если (x 1) = 2 и (x 1) = 3 => 2 = 3

короче, возвращаемые замыкания ни разу не равны. Это принципиальная вещь (и источник принципиальных тормозов в реализациях многих языков).

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

Что это вообще за спецификаторы, первый раз слышу.

Например python optional named arguments, ruby optional named arguments

Ну и в Common Lisp необязательные/остаточные/именованные параметры (и другие более специфичные - &body, &aux, &enveronment, &whole,,) можно комбинировать в разных сочетаниях - почему автоматическое каррирование и не очень подходит.

> Например

Да это понятно, только где они в Haskell?

вот чего хочется от Haskell - это возможности сказать, мол, нефиг тут каррировать :) Хотя это тоже решается...

Проще всего так:

-- |
-- Data type with named fields (something like a keywords).
--
data Man = Man { name   :: String,
                 status :: String }


instance Show Man where
  show (Man name status) = "This is " ++ name ++ " they " ++ status

-- |
-- Default builder, default parameters.
--
every'man = Man "Bloom" "attractive"

-- |
-- Optional one, using structure syntax.
--
not'so'every = every'man { status = "not so attractive" }

{-|
  print every'man
  > This is Bloom they attractive

  print not'so'every
  > This is Bloom they not so attractive
 -}

Т.к. хаскель очень чуток к типам для каждого сложного типа нужно проводить эту линию каждый раз отдельно. Более общего способа я не видел, для этого нужно сделать аналог CL-вского lambda-list в виде АТД и превращать его в код (т.е. это уже уровень Template Haskell), плюс возможны заморочки с типами (т.е. Data.Typeable) - хотя скорее всего это не нужно, так как вся остальная картина попортится (либо попортит плюшки этих самых /// в их классическом виде).

А насчёт «нефиг тут каррировать» всё вообще просто:

foo :: (A, B, C) -> D

никак не покаррируешь :)

Жесть.

> Фигня какая-то.

никакой фигни, в первом случае сравниваемые функции одинаковы (точнее это фактически одна и та же функция: \y -> nil), во втором g создаёт новое замыкание на каждый свой вызов, соответственно и функции разные.

За Racket не скажу. А вот SBCL не врёт. В вашем случае в замыкании не используется параметр замыкания x поэтому возвращается один и тот же объект.

ага, это как, может помните, mv вроде задавал вопрос, почему

(defvar xs '((0 0 0) (1 1 1) (2 2 2)))
(defvar ys '((0 0 0) (1 1 1) (2 2 2)))

(eq xs ys) ; => T

Проверять функции на равенство друг другу? Боюсь что для компьютера единственный способ сделать это правильно - это сравнить значения двух функций на всей области определения. Любой другой способ будет ошибочно считать некоторые функции различными в то время как они в действительности равны.

Заставьте компьютер сравнить функции f(x)=sin(x) и g(x)=sin(x+2*pi). Если отвлечься от того, что на вещественнозначной арифметике могут возникать ошибки (неважно, можно придумать пример на интегральном типе), - эти функции равны. Но не очень ясно, как компьютер об этом может догадаться. Вне зависимости от того, используете вы Haskell или CL.

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

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

Вне зависимости от того, используете вы Haskell или CL.

как работает eq в CL и Scheme для функций тут уже писали. было бы неплохо, если бы в Хаскелле было хотя бы такое сравнение.

«бессмысленно для процедур с сайд-эффектами» - cпасибо, кэп. Речь шла про Haskell и, соответственно, рассматриваем чистые функции.

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

> Речь шла про Haskell и, соответственно, рассматриваем чистые функции.

таки незачем было CL упоминать тогда:

Вне зависимости от того, используете вы Haskell или CL.

Вот это вот «хотя бы такое сравнение» - зачем это нужно?

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

Неправильно ведь будет работать. Как сравнение хешей, только наоборот. Неравенство хешей гарантирует неравество значений, на которых они были вычислены, равенство хешей не гарантирует ничего. Ваше «равенство» функций да, гарантирует что функции действительно равны, но НЕ «равенство» функций не означает ровно ничего. Таким образом, семантика этой операции отличается от семантики истинного равенства. Код, который полагается на естественные свойства класса Eq в Haskell, работал бы неправильно, если в этом языке было сравнение функций на «равенство» в предлагаемом Вами смысле.

всё будет работать именно так как предполагается, неравенство функций будет означать, что это не идентичные объекты, несмотря на возможное совпадение областей значений

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

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

Заставьте компьютер сравнить функции f(x)=sin(x) и g(x)=sin(x+2*pi).

Даже f(x)=sin(x) и g(x)=sin(x) не равны друг другу как алгоритмические объекты.

Неразрешимая в общем случае. Для конечных областей определения - вполне разрешимая.

Да, вот, к слову, про f(x)=sin(x) и g(x)=sin(x). Давайте посмотрим на простой пример на С++.

#include <cmath>
#include <iostream>

inline double f(double x){ return sin(x); }
inline double g(double x){ return sin(x); }

int main()
{
        std::cout << (&f == &g) << std::endl;
        return 0;
}

Эксперимент состоит в следующем: собираем и запускаем под gcc:

$ g++ fptr.cpp -o fptr -O3 && ./fptr
0

Да, «алгоритмические объекты» «неравны». А теперь удивитесь: собираем и запускаем под Microsoft C++ 14.00:

C:\temp>cl /nologo /EHsc fptr.cpp && fptr.exe
fptr.cpp
1

Дело, конечно, в inline.

Вопрос - еще раз - в том, зачем может понадобиться это сравнение? Оно по-разному работает в разных компиляторах (и в одном и том же компиляторе при разных настройках). Какой правильно реализованный алгоритм может использовать это сравнение? Что-то мне кажется что полезность этого сравнения - примерно такая же, как у сравнения адресов переменных на стеке. Результат работы любого алгоритма обязан быть инвариантен по отношению к таким вещам, - иначе алгоритм неправильный.

Неразрешимая в общем случае. Для конечных областей определения - вполне разрешимая.

Brute force? :) Дело в том, что в ФЯ большинство функий имеют счётные области - bignums, РТД.

Можно, например так:

class Countable a where
    listValues :: [a]
    

instance (Countable a, Eq b) => (Eq (a -> b)) where
    f1 == f2 = and $ map (\x -> f1 x == f2 x) listValues 

instance Countable Bool where
    listValues = [True, False]

f x y = not ((not x) || (not y))

main = do
    print (f == (&&))
    print ((&&) == (||))
    print ((||) == f)

Замечу, хоть это и очевидно, что автоматически работает и для функций многих аргументов. В примере f :: Bool -> Bool -> Bool

Хотя бы и brute force. Это неважно, мой первый пост был к тому что все равно в общем случае ничего не выйдет.

Какой правильно реализованный алгоритм может использовать это сравнение?

Любой в любом языке где додумались сделать обощённое сравнение, в том числе для того что играет роль функций - equal в CL, equal? в Scheme, сравнение указателей в Си.

А насчёт Microsoft C++ 14.00 - это его поведение относительно ссылок на инлайновые функции... Я ему не верю :)

В си этот самый алгоритмический объект очень прост:

structure function
  address :: word

И сравнение:

method equal (f :: function) (g :: function)
  equal f.address g.address

Аналогично equal работает со всеми структурными типами - сводит их к сравнению с простыми. В haskell для этого просто достаточно написать deriving(Eq). И в GHC функции - подобные структуры и у них есть поле adrress, так что equal для них имеет смысл (а может даже и определён где-нибудь в сорсах).

>foo :: (A, B, C) -> D

Или хуже:

foo :: A -> B -> C -> D

uncurry3 foo :: (A, B, C) -> D

:D

Это неважно, мой первый пост был к тому что все равно в общем случае ничего не выйдет.

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

Я бы не называл равенство «полей adress» равенством функций. Тем более, что это наложит просто тонну ограничений на процесс компиляции. Да и просто не красиво.

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

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

Вот, а сравнение «алгоритмических представлений» особого смысла не имеет, т.к. само «алгоритмическое представление» - это как адрес переменной на стеке, зависит от реализации.

А как их ещё сравнить именно в Haskell? В общем виде.

Если адресс, то понятно - функция лежит на левой верхней полке, если a и b там лежат, то a == b, если они лежат в разных местах то a /= b (т.е. в образе/бинареом модуле и т.д.). Но это конечно лисповщина и императиыщина :)

это как адрес переменной на стеке, зависит от реализации.

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

Функция f:X->Y равна функции g:X->Y <=def> \any x \in X: f(x) = f(y)

Все! Можешь потребовать у разработчиков ghc выдать тебе функцию-путеводитель в недра компилятора для сравнения внутреннего представления, но использовать это в высокоуровневой программе - не простительно.