CODEWITHSUNDEEP
haskelltuplesord
J.Swersey
J.Swersey

Reputation: 171

Ordering non-numeric tuples by total value (distance?) in Haskell

EDIT: I just realized that this won't solve the problem at all, except for lists with every entry in the set (i.e. getting a comparative value for (a,e) and (b,d) won't help me at all if the list doesn't contain e, but does contain f). Derp. That said, the question of distance comparisons for ordered but non-numeric sets in Haskell is still IMO interesting, so...

I have to write a function 

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

which returns all pairs (xi, xj) from a list where xi < xj and i < j.

That's pretty straightforward with list comprehensions. Now, I need it sorted, and I need it sorted by the "order" of the tuples. That is, the combined order - (a,z) needs to come a long way after (b,c). For integers, this is easy - add xi to xj and use that for the comparison.

However, this is over Ord, so this function has to take obnoxious things like chars, and in Haskell, all I know how to get is GT, LT, or EQ - not how much GT. Is there a way to get Haskell to say

Z is 25 Greater Than A

or something like that? Or any other ideas on how to sort this?

(The actual task involves fulfilling the predicate that for any list xs that is a prefix of another list ys, pairs xs is a prefix of pairs ys. I'm simply under the impression that sorting the list after producing it is probably the way to go. EDIT2: solved it by iterating the list backwards, for those wondering.)

Upvotes: 1

Views: 145

Answers (1)

leftaroundabout
leftaroundabout

Reputation: 120711

Such an ordering can not exist. Not just in Haskell, but anywhere – it's mathematically impossible!

By strict-ordering tuples, you're basically creating a mapping between a two-dimensional domain and a one-dimensional one. This needs to be bijective to preserve the order axioms. Then you talk about distance, that is in this case a topological property and always works analogous to the problem of mapping the real line ℝ to the 2D-plane ℝ2.
Such bijections exist, but it's never possible that both the mapping and its inverse are continuous (which would be necessary to preserve distances in any consistent sense).

So what you want is not achievable.

Upvotes: 3

Related Questions