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

它不是单子。我们可以调整你的反例Sum；关键属性是 that 3 <> -3 = 0 = 0 <> 0，它为0映射到 in的值引入了一个选择点m >>= k。我们可以选择，例如，"" <> "a" = "a" <> ""设置相同的选择。所以：

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

然后我观察：

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

每个非平凡幺半群都有这样的选择点。幺半群的结合性表示：

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

所以，你有麻烦了，如果有任何a和b针对a /= a <> b。

（如果你选择平凡的幺半群，它就是一个 monad：具体来说，它是 (monad-isomorphic to) Maybe。）