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