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 }

A Map is just like a function, so it should be easy to make it a modified version of a Reader monad. In your example, it looks like you are reimplementing ListT (Writer k) v. — Ruifeng Xie
@Krantz Could you write out the instances you're referring to? I can't see how a Map is just like a function, at least not without changes to the notion of a function like imposing bounds on the domain and partializing the codomain. Regarding ListT, which definition of ListT are you referring to? — Asad Saeeduddin
@duplode type Map k v = k -> Maybe v which is ReaderT k Maybe v, so semantically there is a legit monad instance. Probably not very useful, though - return produces an infinite map, and join diagonalises a 2D map. Not really an API which most bread-and-butter Data.Map users will be clamouring for! — Benjamin Hodgson
@BenjaminHodgson You're right, I let myself get carried away with a flawed analogy. Half of this instance even exists as the Bind instance for Map in semigroupoids. — duplode
ContT r (Map k) surprisingly is a monad, and can do something kind of similar to what you're talking about here. — Jeremy List

Daniel Wagner Daniel Wagner · Accepted Answer · 2020-06-24T19:25:13

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

Do maps with list keys form a monad?

1 Answers