[Haskell-cafe] Modulo-foo equivalence classes in Haskell?

[Chris Kuklewicz]

Diego Navarro wrote:
> 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 have seen situations that I needed nub/nubBy.  But nubBy is O(n^2) and so I
tend to avoid it if I can.  If you can sort or sortBy then you can use (norep .
sort) or the "*By" versions.

-- | after sort or sortBy the use of nub/nubBy can be replaced by norep/norepBy
norep :: (Eq a) => [a]->[a]
norep [] = []
norep x@[_] = x
norep (a:bs@(c:cs)) | a==c = norep (a:cs)
                    | otherwise = a:norep bs

-- | after sort or sortBy the use of nub/nubBy can be replaced by norep/norepBy
norepBy :: (a -> a -> Bool) -> [a] -> [a]
norepBy _ [] = []
norepBy _ x@[_] = x
norepBy eqF (a:bs@(c:cs)) | a `eqF` c = norepBy eqF (a:cs)


> 
> 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.

You have a type X and it already has an Eq instance.  But you want to (nubBy
foo) a list [X].  You could use a newtype:

newtype Y = Y { unY :: X }

instance Eq Y where (==) = foo

nub' :: [X] -> [X]
nub' = map unY . sort . map Y

> 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.
> 

But I may have misunderstood what you want.  Here is a solution to a related
problem:

http://portal.acm.org/citation.cfm?id=1017481&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618