Упорядочивание нечисловых кортежей по общему значению (расстоянию?) В Haskell

РЕДАКТИРОВАТЬ: я только что понял, что это не решит проблему вообще, за исключением списков с каждой записью в наборе (то есть получение сравнительного значения для (a,e) а также (b,d) не поможет мне вообще, если список не содержит е, но содержит е). Derp. Тем не менее, вопрос сравнения расстояний для упорядоченных, но не числовых множеств в Haskell по-прежнему интересен для IMO, так что...

Я должен написать функцию

pairs :: Ord a => [a] -> [(a,a)]

который возвращает все пары (xi, xj) из списка, где xi j и i

Это довольно просто с пониманием списка. Теперь мне нужно отсортировать, и мне нужно отсортировать по "порядку" кортежей. То есть объединенный порядок - (a,z) должен пройти долгий путь после (b,c). Для целых чисел это легко - добавьте xi к xj и используйте это для сравнения.

Тем не менее, это закончилось Ord, так что эта функция должна принимать такие неприятные вещи, как символы, а в Хаскеле все, что я знаю, как получить GT, LT, или же EQ - не сколько GT, Есть ли способ заставить Haskell сказать

Z на 25 больше чем A

или что-то типа того? Или какие-нибудь другие идеи о том, как это отсортировать?

(Фактическая задача включает в себя выполнение предиката, что для любого списка xs это префикс другого списка ys, pairs xs это префикс pairs ys, У меня просто сложилось впечатление, что сортировка списка после его составления - это, вероятно, правильный путь. РЕДАКТИРОВАТЬ 2: решил, повторяя список в обратном порядке, для тех, кто интересуется.)

1 ответ

Такого порядка не может быть. Не только в Хаскеле, но и везде - это математически невозможно!

Строго упорядочивая кортежи, вы в основном создаете отображение между двумерным доменом и одномерным. Это должно быть биективным, чтобы сохранить аксиомы порядка. Затем вы говорите о расстоянии, которое в данном случае является топологическим свойством и всегда работает аналогично задаче отображения реальной линии ℝ в 2D-плоскость ℝ2.
Такие биекции существуют, но никогда не возможно, чтобы и отображение, и его обратное были непрерывными (что было бы необходимо для сохранения расстояний в любом непротиворечивом смысле).

Так что то, что вы хотите, не достижимо.

Другие вопросы по тегам