Implementing a key-sensitive monad bind for key-value Map

Question

Based on the List monad I set out to define Monad instances for the Map type from Data.Map, to perform chained unions and folds on Maps like lists, but with the efficient sorting and merging of Maps:

{-# LANGUAGE FlexibleInstances #-}

import qualified Data.Map as M

instance Monad (M.Map Integer) where
  return = M.singleton 0
  f >>= g = M.foldr (\a -> M.union (g a)) M.empty f

This compiles fine but I would like g to be sensitive to the key of each value that it operates on. That would allow the output of g to have staggered keys for richer unioning behaviour. This is fictional Haskell and doesn't typecheck but it would be nice to have:

type PairMap (a,b) = Map a b

instance Monad PairMap where
  return :: (k,a) -> PairMap (k,a)
  return (k,a) = M.singleton k a
  (>>=) :: PairMap (k,a) -> ((k,a) -> PairMap (k',a')) -> PairMap (k',a'))
  f >>= g = M.foldrWithKey (\(k,a) -> M.union (g k a)) M.empty f

If you replace PairMap (a,b) with [(a,b)] you get exactly the List monad back again. But GHC doesn't allow me to cheat and turn the two parameters of Map into one pair. The best I could manage was something like this: (I had to add the Ord c constraint to typecheck with unions)

class PairMonad m where
  return2 :: a -> b -> m a b
  (>>==) :: (Ord c) => m a b -> (a -> b -> m c d) -> m c d

instance PairMonad M.Map where
  return2 = M.singleton
  f >>== g = M.foldrWithKey (\k a -> M.union (g k a)) M.empty f

I hope you can see how similar this is to the PairMap dream, so it should be possible to do this more elegantly with established monadic magic or other concepts related to monads. I don't need it to be a monad as long as I can achieve that "key-sensitive bind."

Last Resort

If there's no way to do this elegantly then I'll resort to collapsing each Map to a key-value list [(a,b)] and use the List monad.
One might suggest including the key into the value to help g compute on the key, but I see that as contaminating the value with extraneous information.

Could you give an example of how g k a would differ from g a? Technically I believe that if g could look at the keys it would violate the monad laws. However, there may be another data structure or formulation which can accomplish what you want to do. — ErikR
– ErikR, Commented Jun 10, 2016 at 14:37
for example if they keys k were integers and a's were lists then I might want g k [True,False,True] == M.fromList [((k,1),True),((k,2),False),((k,3),True)] such that the Map resulting from the bind has pairs of integers as keys which are sorted in lexicographic order, remembering the prior Map structure. I wouldn't be able to achieve this in g a which can't compute on the key of a. I just want to know if there's an existing solution to this, it doesn't have to be a monad. — Herng Yi
– Herng Yi, Commented Jun 11, 2016 at 4:26

Jules · Accepted Answer · 2016-06-10 19:53:14Z

Even if it had valid Haskell syntax, your PairMap "monad" isn't actually a monad, because it forces the result type of the bind operation to be a pair, which prevents the ability to use it in contexts where a pair is not required (e.g. the sequence function couldn't accept it, because it returns m t a where m is the monad type and t is a traversable type, i.e. the result is not a pair so can't work with it). I don't have a proof right now, but intuitively speaking, this must be true for any attempt to turn Map into a monad other than by using constant keys as any such attempt can only work by adding additional structural requirements that would prevent your "monad" from working with existing users of the Monad typeclass.

You're actually looking at a generalisation of Monads that does not fit into the existing class's restrictions. It is possible that you may be able to make it coexist with existing generalisations of Monads; the one that jumps to mind is Control.Arrow.Arrow, which already has an understanding built into the typeclass of using it to operate on pairs, so is potentially a much better fit to what you're trying to achieve.

Herng Yi · Accepted Answer · 2016-06-11 11:31:10Z

Looking up Arrows on Jules' suggestion brought me to the Category typeclass, which allowed me to engineer what I wanted below:

import qualified Control.Category as C
import qualified Data.Map as M

newtype KeyValMorphism k a b = KeyVal ((k, a) -> M.Map k b)

instance (Ord k) => C.Category (KeyValMorphism k) where
  id = KeyVal (uncurry M.singleton)
  KeyVal g . KeyVal f = KeyVal (M.foldrWithKey (\k a -> M.union (g (k,a))) M.empty . f)

I'm slightly dissatisfied with this because:

The newtype wrapper which prevents me from using raw functions (k,a) -> M.Map k b, but for type checking reasons I think this is the best that can be done.
The type k of the keys needs to be fixed throughout the computations, which fits my application and seems a reasonable sacrifice for the simplicity of this instance declaration.

Stack Exchange Network

Implementing a key-sensitive monad bind for key-value Map

2 Answers 2

Your Answer

Hot Network Questions

Implementing a key-sensitive monad bind for key-value Map

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions