Do maps with list keys form a monad?

Question

Consider the following type constructor:

newtype Mapnad k v = Mapnad { runMapnad :: Map [k] v }

Since Ord k => Ord [k] (lexicographical order), we can reuse the functor instance for maps for this type in an obvious way:

deriving instance Ord k => Functor (Mapnad k)

Furthermore, it seems as though Ord k => Monad (Mapnad k), according to the following scheme:

-- For readability
type (×) = (,)
infixr ×

toList'   :: Ord k => Mapnad k v -> [[k] × v]
fromList' :: Ord k => [[k] × v] -> Mapnad k v

return' :: Ord k => a -> Mapnad k a
return' = fromList' . return . return

join' :: Ord k => Mapnad k (Mapnad k v) -> Mapnad k v
join' =
  fmap toList'        -- Mapnad k [[k] × v]
  >>> toList'         -- [[k] × [[k] × v]]
  >>> (=<<) sequenceA -- [[k] × [k] × v]
  >>> fmap join       -- [[k] × v]
  >>> fromList'       -- Mapnad k v

-- Note: we are using the writer monad for tuples above

instance Ord k => Applicative (Mapnad k)
  where
  pure = return
  (<*>) = ap

instance Ord k => Monad (Mapnad k)
  where
  return = return'
  ma >>= amb = join' $ fmap amb ma

Is this a legal monad instance? QuickCheck seems to suggest so, but it'd be good to know for sure one way or the other.

---

Bonus question: Assuming this is indeed a monad, are there any monoids k besides the free [a] monoid for which Map k is a monad? There are certainly counterexamples: i.e. monoids k for which Map k is not a monad. For instance, with the same monad instance for Map (Sum Int), QuickCheck finds a counterexample to the associativity law.

-- m >>= (\x -> k x >>= h) == m >>= k >>= h
m :: { 0 -> 0; 3 -> 7 }
k :: \x -> if (odd x) then { -3 -> 1 } else { 0 -> 0 }
h :: \x -> if (odd x) then { }         else { 0 -> 0 }

Answer 1

It is not a monad. We can adapt your counterexample for Sum; the key property is that 3 <> -3 = 0 = 0 <> 0, which introduces a choice point for the value that 0 maps to in m >>= k. We can choose, e.g., "" <> "a" = "a" <> "" to set up the same choice. So:

m = { "" -> 0; "a" -> 7 }
k x = if odd x then { "" -> 1 } else { "a" -> 0 }
h x = if odd x then { }         else { ""  -> 0 }

Then I observe:

m >>= k >>= h           = { }
m >>= (\x -> k x >>= h) = { "a" -> 0 }

Every non-trivial monoid has such choice points. The associativity property of monoids says:

a <> (b <> c) = (a <> b) <> c

So you are in trouble if there are any a and b for which a /= a <> b.

(It is a monad if you choose the trivial monoid: specifically, it is (monad-isomorphic to) Maybe.)