Прогнило что-то в датском королевстве
В новой версии (2.3.0-preview1) руби что-то пошло не так. Разработчики MRI поддержали фичу сравнения хэшей по отношению включения при помощи операторов сравнения. Никого не смутило, что это частично упорядоченное множество. Ок, сравнения классов в языке уже живут очень давно. Но для них хотя бы есть специальный результат сравнения несравнимых
( Read more... )
там явно указано, что для соритровок и многих других подобных алгоритмов (бинарный поиск, например) требуется strict weak ordering.
Мало того, в стандартной библиотеке есть stable_sort, который кроме прочего дает однозначный результат, даже если объекты которые, вроде как, равны не совпадают.
Как ты думаешь для кого подобные вещи пишутся?;)
В смысле слабого порядка всё логично: все несравнимые хеши необходимо считать равными:). Это пофиксит и проблемы с твоим примером и с сортировками. Т.е. само по себе введение таких сравнений не страшно.
Другое дело, что существующее определение == не совпадает с соотношением эквивалентности задаваемым <=, что полностью рушит подобную картину. И это уже гораздо более серьёзная проблема.
Вообще введение в базовую библиотеку класса с несогласованными операторами сравнения действительно дурно пахнет.
Там такое раньше было?
Я не знаю на сколько серьезно обсуждаются изменение в ruby, но в c++ подобную «фичу» завернули бы.
Скорее всего и здесь по трезвому размышлению от неё придется отказаться.
В обсуждении(по ссылке) лучше упирай именно на последний аргумент: определения операторов ==, > и < не согласованы.
А то у тебя получаются не совсем корректные утвержденя.
Пример: из !(a<=b || b<=a ) вообше говоря, не следует !(a==b || a
Reply
Кстати, я проглядел этот эпик фейл в реализации:
{a: 1, b: 2} <= {a: 1, b: 3}
{a: 1, b: 3} <= {a: 1, b: 2}
Реализация, которая сломала ключевой юзкейс фичи - использование в тестировании. Правда пугает.
А что ты имеешь ввиду, когда говоришь про согласованность <= и ==?
К вопросу про некорректность. Разве a<=b не эквивалентно a < b || a == b? Или это всего лишь !(b < a) ?
Раньше в руби всё делалось оператором <=>, который возвращал положительное, отрицательное или нулевое значение, а остальные операторы опирались на него. Для несравнимых элементов он возвращал nil - и встроенные методы типа sort кидали эксепшн. Неидеально, но кое-как жить можно.
Сейчас у хэшей вообще не стали делать метод <=> (и sort кидает эксепшн "метод не найден"), а доопределили четыре метода сравнения.
Reply
a < b это strict weak ordering.
т.к.
! a < a
x < y → !y < x
x < y && y < z → x < z
!(x < y) && !(y < x) является отношением эквивалентности (назовем его ~). (транзитивно, симметрично и рефлексивно)
Это отношение порядка вполне имеет право на жизнь и никаких проблем с ним нет.
Дальше начинаются проблемы: отношение == не соответствует заданому выше отношению эквивалентности ~.
Отношение ≤ строится через него, как x ≤ y ⇔ x == y || x < y.
Если бы отношение == совпадало с отношением эквивалентности определяемым
отношением < , проблем бы не было. Вообше никаких. Но наше отношение эквивалентности ==
на самом деле более узкое чем требуется.
Отсюда и возникают проблемы с (x==y) || (x < y) || (x > y).
Ситуация когда x≤y и x≥y нарушаются одновременно, в общем-то
не очень красивая, это как раз случай частичного порядка не являюшегося слабым. Она противоречит сказанному выше,
однако это тоже можно разрешить. В стандарте с++ это разрешается следующим образом:
соотношение эквивалентности строящееся на ≤ будет таким:
x~y ⇔ x≤y && y≤x || !x≤y && !y≤x .
Таким образом мы получаем соотношение эквивалентности ~ которое, вместе с отношением ≤,
дает нам построить strict weak ordering < как x < y⇔ x≤y && !x~y.
Заметим что x < y ||x~y не эквивалентно x ≤ y. Тем не менее
(x~y)||(x < y)||(x > y) является тавтологией.
Т.е. чисто с формальной точки зрения
может быть ситуация в которой может быть !x≤y && !y≤x,
но (x==y)||(x < y)||(x > y) всегда верно. Именно это я имел ввиду под некорректностью.
Я не хочу сказать, что так нужно делать, но так можно делать
и некоторые делают.
Несогласованностью я называю ситуацию, когда ~ не совпадает с ==.
Это ведет как раз к проблемам с условиями, несравнимые остаются неохваченными.
Другой выход ты описывал, это оператор <=> который умеет разрешать четыре
разных случая. C ним тоже можно сделать чтобы работало корректно.
Отдельным вопросом стоит, насколько для хешей вообще вероятно попадание в код типа
if a == b
…
elif a < b
…
elif a > b
…
Я бы писал так
if a < b
…
elif a > b
…
else
Тут вообще не факт что ошибка проявится;)
, особенно если последняя ветка почти ничего не делает.
-------------------------------------------------------------------------
Я, кстати, такое уже видел. В python есть класс set с такими же отношениями сравнения
и эквивалентности. Честно говоря, там это существенных проблем не вызывает,
даже сортировки на них работают.
С питоном, вероятно все дело в этом:
Starting with Python 2.2, sorts are guaranteed to be stable. That means that when multiple records have the same key, their original order is preserved.
Возможно оттуда идея и пришла. Но питон не лучший пример для подражания.
Там реализована масса неодназначных идей.
По поводу безопасности, я не верю в безопасность языков с динамической типизацией,
при условии что пользователь сам формирует поступающие данные. Это просто нереально.
Так что тут ничего не меняется.
На самом деле учитывая что сравнивать хеши раньше было нельзя, я не ожидаю большого числа проблем.
Сделают стандартный sort стабильным, а со сравнениями, просто люди проверят лишний раз какую им хрень
подсунули.
Reply
Leave a comment