No Monad Instance for `Data.Map`, but Scala's Map?

Question

Using :i Map, I don't see a Monad instance for it.

ghci> import Data.Map
ghci> :i Map
type role Map nominal representational
data Map k a
  = containers-0.5.5.1:Data.Map.Base.Bin {-# UNPACK #-} !containers-0.5.5.1:Data.Map.Base.Size
                                         !k
                                         a
                                         !(Map k a)
                                         !(Map k a)
  | containers-0.5.5.1:Data.Map.Base.Tip
    -- Defined in ‘containers-0.5.5.1:Data.Map.Base’
instance (Eq k, Eq a) => Eq (Map k a)
  -- Defined in ‘containers-0.5.5.1:Data.Map.Base’
instance Functor (Map k)
  -- Defined in ‘containers-0.5.5.1:Data.Map.Base’
instance (Ord k, Ord v) => Ord (Map k v)
  -- Defined in ‘containers-0.5.5.1:Data.Map.Base’
instance (Ord k, Read k, Read e) => Read (Map k e)
  -- Defined in ‘containers-0.5.5.1:Data.Map.Base’
instance (Show k, Show a) => Show (Map k a)
  -- Defined in ‘containers-0.5.5.1:Data.Map.Base

However, I see that Scala's Map implements flatMap.

I do not know if Map if obeys the Monad Laws.

If my observation on Data.Map is correct, then why isn't there an instance Monad (Map) in Haskell?

I looked at this answer, but it looks like it uses Monad Transformers.

Answer 1

It's hard to reason what Scala's flatMap is supposed to do:

trait Map[A, B+] extends Iterable[(A, B)] {
  def flatMap[B](f: (A) ⇒ GenTraversableOnce[B]): Map[B]
}

It takes a key, value pair of map (because flatMap comes from Iterable, where A is (A,B)):

scala> val m = Map("one" -> 1, "two" -> 2)
m: scala.collection.immutable.Map[String,Int] = Map(one -> 1, two -> 2)

scala> m.flatMap (p => p match { case (_, v) => List(v, v + 3) })
res1: scala.collection.immutable.Iterable[Int] = List(1, 4, 2, 5)

This isn't monadic bind, it's more closer to Foldable's foldMap

λ > import Data.Map
λ > import Data.Monoid
λ > import Data.Foldable
λ > let m = fromList [("one", 1), ("two", 2)]
λ > (\v -> [v, v + 3]) `foldMap` m
[1,4,2,5]

---

Map is lawful Ord k => Apply (Map k v) and Ord k => Bind (Map k v):

-- | A Map is not 'Applicative', but it is an instance of 'Apply'
instance Ord k => Apply (Map k) where
  (<.>) = Map.intersectionWith id
  (<. ) = Map.intersectionWith const
  ( .>) = Map.intersectionWith (const id)

-- | A 'Map' is not a 'Monad', but it is an instance of 'Bind'
instance Ord k => Bind (Map k) where
  m >>- f = Map.mapMaybeWithKey (\k -> Map.lookup k . f) m

Which is a bit like ZipList instance could be, zipping elements by key. Note: ZipList isn't Bind (only Apply) because you cannot remove elements from between the range.

And you cannot make it Applicative or Monad, because there are no way to make lawful pure / return, which should have a value at all keys. Or it might be possible if some Finite type class is constraining k (because Map is strict in it's spine, so you cannot create infinite maps).

---

EDIT: pointed out in the comments. If we think properly, the above tries to make a concrete (inspectable) representation of MaybeT (Reader k) v = k -> Maybe v with Map k v. But we fail, as we cannot represent pure x = const x. But we can try to do that by explicitly representing that case:

module MMap (main) where

import Data.Map (Map)
import qualified Data.Map as Map
import Test.QuickCheck
import Test.QuickCheck.Function

import Control.Applicative
import Control.Monad

-- [[ MMap k v ]] ≅ k -> Maybe v 
data MMap k v = MConstant v
              | MPartial (Map k v)
  deriving (Eq, Ord, Show)

-- Morphism
lookup :: Ord k => k -> MMap k v -> Maybe v
lookup _ (MConstant x) = Just x
lookup k (MPartial m)  = Map.lookup k m

instance Functor (MMap k) where
  fmap f (MConstant v) = MConstant (f v)
  fmap f (MPartial m)  = MPartial (fmap f m)

instance Ord k => Applicative (MMap k) where
  pure = MConstant
  (MConstant f) <*> (MConstant x) = MConstant (f x)
  (MConstant f) <*> (MPartial x)  = MPartial (fmap f x)
  (MPartial f)  <*> (MConstant x) = MPartial (fmap ($x) f)
  (MPartial f)  <*> (MPartial x)  = MPartial (Map.intersectionWith ($) f x)

instance Ord k => Monad (MMap k) where
  return = MConstant
  (MConstant x) >>= f = f x
  (MPartial m) >>= f  = MPartial $ Map.mapMaybeWithKey (\k -> MMap.lookup k . f) m

instance (Ord k, Arbitrary k, Arbitrary v) => Arbitrary (MMap k v) where
  arbitrary = oneof [ MConstant <$> arbitrary 
                    , MPartial . Map.fromList <$> arbitrary
                    ]

prop1 :: Int -> Fun Int (MMap Int Int) -> Property
prop1 x (Fun _ f) = (return x >>= f) === f x

prop2 :: MMap Int Int -> Property
prop2 x = (x >>= return) === x

prop3 :: MMap Int Int -> Fun Int (MMap Int Int) -> Fun Int (MMap Int Int) -> Property
prop3 m (Fun _ f) (Fun _ g) = ((m >>= f) >>= g) === (m >>= (\x -> f x >>= g))

main :: IO ()
main = do
  quickCheck prop1
  quickCheck prop2
  quickCheck prop3

It indeed works! Yet this a bit fishy definition, as we cannot define semantically correct Eq instance:

m1 = MConstant 'a'
m2 = MPartial (Map.fromList [(True, 'a'), (False, 'a')])

The m1 are m2 are semantically equivalent (lookup k has same results), but structurally different. And we can't know when MPartial have all key-values defined.

---

Spine refers to, uh, data structure spine. For example list defined as

data List a = Nil | Cons a (List a)

ins't strict in the spine, but

data SList a = SNil | SCons a !(SList a)

is.

You can define infinite List, but SLists:

λ Prelude > let l = Cons 'a' l
λ Prelude > let sl = SCons 'a' sl
λ Prelude > l `seq` ()
()
λ Prelude > sl `seq` () -- goes into infinite loop

As Map is also strict in it's spine

data Map k a  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
              | Tip

we cannot construct infinite Map, even we had means to get all values of k type. But we can construct infinite ordinary Haskell list: [] to make pure for Applicative ZipList.