[Haskell-cafe] Modulo-foo equivalence classes in Haskell?
Chris Kuklewicz
haskell at list.mightyreason.com
Thu Feb 1 07:31:22 EST 2007
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
More information about the Haskell-Cafe
mailing list