In Scala, the higher order operations on collections always return the best possible type in the context. For example, in case of BitSet, if you map ints to ints you get a BitSet, but if you map ints to strings, you get a general Set. Similarly, if you map a Map with a function that yields a pair, then you get a Map in return. Else you get a simple Iterable. Both the static type and the runtime representation of map's result depend on the result type of the function that's passed to it.
scala> Map(2 -> 'a', 6 -> 'b') map { case (k, v) => (k + 1, v.toString) }
res0: scala.collection.immutable.Map[Int,java.lang.String] = Map(3 -> a, 7 -> b)
scala> Map(2 -> 'a', 6 -> 'b') map { _._1 }
res1: scala.collection.immutable.Iterable[Int] = List(2, 6)
scala> import collection.immutable.BitSet
import collection.immutable.BitSet
scala> BitSet(2, 44, 93).map(1 +)
res3: scala.collection.immutable.BitSet = BitSet(3, 45, 94)
scala> BitSet(2, 44, 93).map(_ + "hola")
res4: scala.collection.immutable.Set[String] = Set(2hola, 44hola, 93hola)
Is it possible to implement the same functionality in Haskell's type system? If yes, how? A Haskell translation of the examples in above code snippet would be much appreciated. :-)
I don't think your first example is very Haskell-y, as you're overloading the same name to do two very different things. In Haskell, when you map a function over some container, you expect to get the same container type back. In fact, this is so common in Haskell that there is a type class, Functor which encapsulates this pattern.
All forms of overloading in Haskell boil down to using type classes, and while you could use those to achieve something similar, it would be very contrived and not very useful over just using plain functions that do just the one thing you want.
Prelude> import qualified Data.Map as M
Prelude Data.Map> let m = M.fromList [(2, 'a'), (6, 'b')]
Prelude Data.Map> M.map show $ M.mapKeys (+1) m
fromList [(3,"'a'"),(7,"'b'")]
Prelude Data.Map> M.keys m
[2,6]
I think your second example is more relevant to Haskell, as it's more about picking the most efficient implementation of a data structure based on the contained type, and I suspect this shouldn't be too difficult to do using type families, but I'm not too familiar with those, so I'll let someone else try to answer that part.