### Modulo-foo equivalence classes?

01Feb07

Just posted this to `haskell-cafe`. I’ve probably done a horrible job at expressing myself, but gah, let’s not hoard ideas.

Watching the questions go by in #haskell, a still fuzzy but possibly pregnant idea popped up in my mind. Someone needed a nubBy function that returned an unique list modulo an arbitrary function foo. Well, in this case it wasn't arbitrary; he had a list of transposable matrices and wanted an unique list of matrices that couldn't be transposed into each other.

I'm thinking there are many cases of fooBy functions that have to be constantly rewritten, and also a lot of ugly code by having to constantly add the modulo clauses (like in modular arithmetic).

I'm inexperienced with type classes -- I've only done the simplest types and /some/ fundeps -- so I'm wondering what would be the clearest, most general way of having a Modulo-foo Eq class that could be parameterized with a function. The "transposable matrix" example shows how this could be useful for (some limited form) of data compression, but it could make some other forms of "algebraically modular" (this is not a proper term, it's me trying to get thoughts across) business rules, of which modular arithmetic is a special case.

Uh, I've probably not expressed myself well enough; I hope I have a shot at trying to explain myself better if questions come up.

#### 2 Responses to “Modulo-foo equivalence classes?”

1. 1 Matthew

You might be interested in the description of quotient or congruence types here:

http://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ttfp.pdf

They require a undecideable dependent type system, sadly, but would be rather useful for things like this.

2. 2 Matthew

I can’t see a way to do this directly with type-classes though. You can parameterize them with a type, but not a function, right?

I guess you could always just do something like this:

data MatrixModuloTransposition = ModuloTransposition Matrix
instance Eq MatrixModuloTransposition where
MatrixModuloTransposition p == MatrixModuloTransposition p = p == q || p == (transpose q)

• ## Dr. Syntaxfree

Dr. Syntaxfree has no PhD and shouldn't call himself a "doctor", but does so for amusement value anyway. An unemployed (ok, graduate student) econopundit by day, he's been progressively obsessed about Haskell to the point he often can't fathom not working on it. A jack-of-many-trades, he has an unusual CS background in that he knows no imperative programming at all, he hopes to be both helpful to those less knowledgeable than him and illustrative to the really smart people trying to understand the mentality of a common man trying to tackle functional programming.