On Thu, May 26, 2011 at 8:47 AM, Daniel Fischer < daniel.is.fischer@googlemail.com> wrote:
On Thursday 26 May 2011 02:23:06, Federico Mastellone wrote:
Hi,
I created a Data.MultiMap module based on Data.Map and Data.Set like this:
data MultiMap k v = MultiMap (Map k (Set v))
and a Data.IntMultiMap module based on Data.IntMap and data.IntSet like this:
data IntMultiMap = IntMultiMap (IntMap IntSet)
Both of these would better be newtypes instead of data, I think. Using data incurs some run-time overhead (the newtype doesn't exist at run- time, only during compile-time [type checking phase], so it's a strictly controlled type alias in practice, making it easier [or possible at all] to apply optimisations available for the underlying type) due to the extra indirections via the constructor and introduces the new value (MultiMap _|_), which complicates strictness analysis and optimisations in general.
Thanks for the tip, I use newtype where I can but I thought it would be simpler here to explain my problem using data. Anyway, now I know better why I should use newtype instead.
For example the functions to add a value I wrote are:
For MultiMap: addValue :: k -> v -> MultiMap k v -> MultiMap k v addValue k v (MultiMap m) = MultiMap $ Map.insertWith (\new old -> Set.insert v old) k (Set.singleton v) m
For IntMultiMap: addValue :: Int -> Int -> IntMultiMap -> IntMultiMap addValue k v (IntMultiMap m) = IntMultiMap $ IntMap.insertWith (\new old -> IntSet.insert v old) k (IntSet.singleton v) m
Both modules look almost the same, with the same documentation, same behavior, same function names but with different type signatures.
Well, we have the same situation with Map/IntMap and Set/IntSet, so
Yes, both pairs, (Set, InSet), and (Map, IntMap), have the exact same problem as my MultiMap module. But I think that as your solution involves using non-standard extensions we could not solve this problem in GHC's libraries. Am I OK?
Is there a way to make this simpler?
Not a really good one (at least, none I know).
The same thing happens to the modules that are using MultiMap and IntMultiMap, I have to write two versions of each.
You can reduce the code duplication at the use sites with a type class,
{-# LANGUAGE TypeFamilies #-}
Is this a mostly experimental extension or I can use it safely? Is it used around the GHC packages?
class MultiMapClass m where type Key m type Value m empty :: m singleton :: Key m -> Value m -> m addValue :: Key m -> Value m -> m -> m ...
instance (Ord k, Ord v) => MultiMapClass (MultiMap k v) where type Key (MultiMap k v) = k type Value (MultiMap k v) = v empty = MultiMap Map.empty ...
instance MultiMapClass IntMultiMap where type Key IntMultiMap = Int type Value IntMultiMap = Int empty = IntMultiMap IntMap.empty ...
I'm going to read about this extension, try it and comment about it here.
Thanks!
Thank you very much for your complete response, really helpful! -- Federico Mastellone Computer Science Engineer - ITBA ".. there are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult." Tony Hoare, 1980 ACM Turing Award Lecture.