Now I have a new problem, it's getting really difficult to program
generically and to create highly parameterized libraries.
So far so good with type families, but when I want to return a generic Set
for the getValues function and provide a default implementation for
getValuesCount function I don't know how to do it, I don't even know if it
is possible.
newtype MultiMap k v = MultiMap (Map.Map k (Set.Set v))
newtype IntMultiMap = IntMultiMap (IntMap.IntMap IntSet.IntSet)
class MultiMapClass m where
type Key m
type Value m
empty :: m
addValue :: Key m -> Value m -> m -> m
getValues :: Key m -> m -> Set (Value m)
getValueCount :: Key m -> m -> Int
getValueCount k m = Set.size $ getValues k 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
addValue k v m = ..........
getValues k (MultiMap map) = map Map.! k
instance MultiMapClass IntMultiMap where
type Key IntMultiMap = Int
type Value IntMultiMap = Int
empty = IntMultiMap IntMap.empty
addValue k v m = ..........
getValues k (IntMultiMap map) = map IntMap.! k
On Thu, May 26, 2011 at 1:47 PM, Federico Mastellone
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.
-- 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.