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 [EMAIL PROTECTED] = 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 _ [EMAIL PROTECTED] = 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe