Can this functionality be implemented with Haskell's type system?

Question

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. :-)

Answer 1

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.

Answer 2

I very much agree with hammar, but here's a way to do it, sort of:

{-# LANGUAGE MultiParamTypeClasses, TypeFamilies, FlexibleInstances #-}

import Prelude hiding (map)

import qualified Data.Map as M
import qualified Data.IntSet as I
import qualified Data.Set as S

type family Elem c :: *
type instance Elem (M.Map k v) = (k, v)
type instance Elem I.IntSet = Int
type instance Elem (S.Set a) = a

class Map c o where
  type Result c o :: *
  map :: (Elem c -> o) -> c -> Result c o

instance Map I.IntSet Int where
  type Result I.IntSet Int = I.IntSet
  map = I.map

instance Map I.IntSet String where
  type Result I.IntSet String = S.Set String
  map f = S.fromList . fmap f . I.toList

instance (Ord k, Ord k1) => Map (M.Map k v) (k1, v1) where
  type Result (M.Map k v) (k1, v1) = M.Map k1 v1
  map f = M.fromList . fmap f . M.toList

instance (Ord k) => Map (M.Map k v) Int where
  type Result (M.Map k v) Int = [Int]
  map f = fmap f . M.toList

Here it is in action:

*Main> map fst (M.fromList [(2::Int, 'a'), (6, 'b')])
[2,6]
*Main> map (\(k, v) -> (k + 1, show v)) (M.fromList [(2, 'a'), (6, 'b')])
fromList [(3,"'a'"),(7,"'b'")]
*Main> :t it
it :: M.Map Integer [Char]

Ideally you'd want to do this:

instance (Ord k) => Map (M.Map k v) a where
  type Result (M.Map k v) a = [a]
  map f = fmap f . M.toList

But that instance conflicts with the one for pairs. So there's no good way to give an instance for every other type.